The largest integer that divides $(n+19)(n+18)(n+17)(n+16) ~ \forall ~ n \in \mathbb{N}? $ is?
It struck me that we should write this as:
$\dbinom{n+19}{4}\times 4!$
which is always divisible by $4!$. Now I am confused as to how do I take it from here? Because the question asks for largest positive integer.
Edit:
Is there no alternative to brute force method i.e. checking for few values then assuming the event would never occur?
Answer
Let $f(n) = (n + 16)(n + 17)(n + 18)(n + 19)$.
Then we have that
$$
\gcd(f(1), f(4), f(5)) = \gcd(17 \cdot 18 \cdot 19 \cdot 20, 20 \cdot 21 \cdot 22 \cdot 23, 21 \cdot 22 \cdot 23 \cdot 24) = \gcd(2^3 \cdot 3^2 \cdot 5 \cdot 17 \cdot 19, 2^3 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 23, 2^4 \cdot 3^2
\cdot 7 \cdot 11 \cdot 23) = 2^3 \cdot 3 = 24.
$$
Thus any number that divides $f(n)$ for all $n$ can be at most $24$. You've already shown that $24$ works, so $24$ is the largest such number.
Edit: Why did I consider $n = 1$, $n = 4$, and $n = 5$ in particular?
I took $n = 1$ because it is the smallest value that $n$ is allowed to be, and I'd prefer to work with fairly small numbers.
We now continue with the conjecture that the answer should be $24$. The number $f(1)$ has $17$ and $19$ as factors, so to rule out that these factors will divide $f(n)$ for all $n$, we need to find a $n$ such that $f(n)$ is not divisible by $17$ or $19$. If $n$ is less than $4$, then we can see that one of the numebrs that we are multiplying by to get $f(n)$ is going to be $19$, (since the smallest of the four numbers is $n + 16$, we need $n + 16 > 19$), we see that any $n$ such that $f(n)$ is not divisible by $19$ must be at least $5$. In accordance with our preference for using small numbers, we consider the value of $f(5)$. The other reason that we would like to use a number that is at least $5$ is that otherwise $20$ will divide $f(n)$, and we want to rule out the possibility of $5$ dividing $f(n)$ for all $n$.
The problem we now have is that both $f(1)$ and $f(5)$ are divisible by $9$, so we need to find an $n$ such that $f(n)$ is divisible by $3$, but not by $9$. Now if $(n + 16)$ is divisible by $3$, then so is $(n + 19)$, and so to avoid having a factor of $9$, we need to consider an $n$ such that $(n + 16)$ is not divisible by $3$. This rules out $n = 2$. It turns out that $n = 3$ works, but I overlooked this for some reason and went with $n = 4$ instead.
No comments:
Post a Comment