Playing with numbers

Number Theory Level 3

The largest integer that divides $(n+16)(n+17)(n+18)(n+19)$ for all $n \in \mathbb{N}$ is:

12 24 120 6

1 solution

Yash Jain
Mar 30, 2017

If your answer is 120, then one counter example is when $n=40$ ,

$(n+16)(n+17)(n+18)(n+19) \\= 56 \times 57 \times 58 \times 59 \\= (8 \times 7) \times (3 \times 19) \times (2 \times 29) \times 59 \\= (24 \times 2) \times (7 \times 19 \times 29 \times 59)$

It is clearly not divisible by 120.

More generally, the product of n consecutive numbers is divisible by n!(n factorial).

A Former Brilliant Member - 4 years, 2 months ago

Yes. But can you prove it?

Yash Jain - 4 years, 2 months ago

Yes. We will prove it by induction.

Let's assume that the product of $n$ consecutive numbers is divisible by $n!$ .

Let the product of $n$ consecutive integers be $f(x)=x(x+1)\ldots(x+n-1)$ .

For $x=1$ we have $f(1)=n!$ which is true for our assumption.

So, if we need to prove that $n!$ divides $f(x+1)$ .

$f(x+1)=(x+1)(x+2)\ldots(x+n)$

$=[(x+1)(x+2)\ldots(x+n-1)] \times x + [(x+1)(x+2)\ldots(x+n-1)] \times n$

According to induction assumption, $[(x+1)(x+2)\ldots(x+n-1)] \times x$ is $f(x)$ which is divisible by $n!$ .

Also, $[(x+1)(x+2)\ldots(x+n-1)] \times n$ is the product of $n$ and $(n-1)$ consecutive integers which is also divisible by $n \times (n-1)! = n!$ according to induction assumption.

So $f(x+1)$ is the sum of two terms that are divisible by $n!$ so it is also divisible by $n!$ .

Proved

A Former Brilliant Member - 4 years, 2 months ago

@A Former Brilliant Member – There's some confusion. You used your assumption to prove your assumption!

Yash Jain - 4 years, 2 months ago

@Yash Jain – That's actually how the induction - introduction works

A Former Brilliant Member - 4 years, 2 months ago

Playing with numbers

1 solution

0 pending reports