Find the greatest common divisor of the integers $P(1),P(2),P(3),…,P(2016)$.

contest-mathelementary-number-theory

For any positive integer $n$, we define $P(n)$ by: $$P(n)=n(n+1)(2n+1)(3n+1)…(16n+1).$$
Find the greatest common divisor of the integers $P(1),P(2),P(3),…,P(2016)$.

If you could prove that only specific primes consistently appear in each $P(n)$ then you would be done, but im not sure how to do that, solutions would be appreciated

Taken from the 2016 Pan African Math Olympiad

http://pamo-official.org/problemes/PAMO_2016_Problems_En.pdf

Best Answer

We want the $\gcd$ of all the different products $$ 1\cdot (1\cdot 2\cdot 3\cdot 4\cdots 16\cdot 17)\\ 2\cdot (1\cdot 3\cdot 5\cdot 7\cdots 31\cdot 33)\\ 3\cdot (1\cdot 4\cdot 7\cdot 10\cdots 46\cdot 49)\\ \vdots\\ 2016\cdot (1\cdot 2017\cdot 4033\cdot 6049\cdots 30\,241\cdot 32\,257) $$ (I added a factor $1$ to make sure that we had $17$ factors in each parenthesis. This makes $17$ not a special case, which makes the proof easier.)

For each prime $p\leq 17$, consider $P(p)$. It has $p$ as the first factor, and then seventeen factors that are coprime to $p$. So $p\mid P(p)$, but $p^2\nmid P(p)$. Similarily, for any $n$ with $p\mid n$, we have $p\mid P(n)$ as $n$ is a factor of $P(n)$.

For any other $n$, $P(n)$ has $p$ as a factor because the part of the product above that I have put into brackets is an arithmetic progression of length $17\geq p$, with common difference coprime to $p$, and at least one of the terms must therefore be divisible by $p$. So the $\gcd$ contains $p$ as a factor, but not $p^2$.

As for any prime factors above $17$, none of them appear in $P(1)$, so they do not divide the $\gcd$.

We conclude that the $\gcd$ of all the above products is $$ 17\# = 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17 = 510\,510 $$

Related Question