2
$\begingroup$

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?

$\endgroup$
3
  • 4
    $\begingroup$ Now look at a few values of $n $, and show that these products have 24 as their gcd. $\endgroup$ Commented Mar 15, 2018 at 20:20
  • $\begingroup$ For example $n=1,3,5$ $\endgroup$
    – Henry
    Commented Mar 15, 2018 at 20:21
  • $\begingroup$ Concerning your edit: checking a few gcd's is not "brute force" at all. $\endgroup$ Commented Mar 15, 2018 at 20:28

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

Good start!

When $n=0$ you get $19\cdot 18\cdot 17 \cdot 16,$ so the answer must divide this. Look for examples that allow you to discard some of the factors. For example, when $n=4$ you get $23\cdot 22\cdot 21 \cdot 20,$ so we can forget about $17$ and $19,$ and we're down to $18 \cdot 16$. Look at some more examples to whittle it down to $24$.

$\endgroup$
0
1
$\begingroup$

This can be treated as a case of product of four consecutive natural numbers since it is $~ \forall ~ n \in \mathbb{N}$: Suppose four consecutive natural numbers are: $2k-1$, $2k$, $2k+1$, and $2k+2$ where $k$ is some natural number $\ge 1$. Thus product of them will be: $$(2k-1)(2k)(2k+1)(2k+2)=4k(2k-1)(2k+1)(k+1)=4k(4k^2-1)(k+1)$$ For apply it for all $n$, $k=1$ and then $$4k(4k^2-1)(k+1)=4(4-1)(1+1)=24$$

$\endgroup$
1
  • $\begingroup$ @Abcd: I kept it to reflect my mistake, but I'd delete it now. Nonetheless, I posted different answer. Thank you for your kindness. :-) $\endgroup$ Commented Mar 15, 2018 at 21:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .