## [Soln] 2016 Pan-African Math Olympiad Problem 3

2016 PAMO 3. For any positive integer $n$, we define the integer $P(n)$ as

$P(n) = n(n+1)(2n+1)(3n+1) \dots (16n + 1).$

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

Let $G$ be the greatest common divisor that we seek. Let’s put together some relatively obvious facts:

1. $G \leq P(1) \leq P(2) \leq \dots \leq P(2016)$.
2. $P(1) = 1 \cdot 2 \cdot 3 \dots \cdot 17 = 17!$. Hence, $G$ must be a factor of $17!$.
3. $P(2) = 2 \cdot 3 \cdot 5 \dots \cdot 33$. Notice that only the first term in the product expansion is even, while the rest are odd. Hence, if we think about the prime factorisation of $G$, the power of 2 in its prime factorisation is at most 1.

The last fact above should set us thinking: can we replicate this argument for the other primes in $G$‘s factorisation? Since $G \mid 17!$, $G$ must have the form

$G = 2^a 3^b 5^c 7^d 11^e 13^f 17^g$

where the exponents are non-negative integers. Fact 3 shows that $a \leq 1$. Could it be that the rest of the exponents are also $leq 1$?

Indeed, it is the case. For any prime $p \in \{ 2, 3, 5, 7, 11, 13, 17\}$, consider $P(p)$. For any positive integer $i$,

$ip + 1 \equiv 1 \mod p \not\equiv 0 \mod p.$

Hence, $p \mid P(p)$ while $p^2 \nmid P(p)$. It thus follows that $0 \leq a, b, c, d, e, f, g \leq 1$.

Let’s think about the factor 2 for a moment. Is it obvious that for every $1 \leq n \leq 2016$, we have $2 \mid P(n)$? Well, yes! That’s because if $n$ is even, the $n$ term is divisible by 2; if it’s odd, then the $n+1$ term is divisible by 2. Hence, we have $a = 1$.

Again, can we replicate this argument for the other possible primes in $G$? Yes! Let $p$ be a prime in $\{ 2, 3, 5, 7, 11, 13, 17 \}$. For any $1 \leq n \leq 2016$,

Case 1: $n \equiv 0 \mod p$. Then obviously $p \mid P(n)$.

Case 2: $n \not\equiv 0 \mod p$. If there exists some $i \in \{ 1, 2, p-1\}$ such that $in + 1 \equiv 0 \mod p$, then obviously $p \mid P(n)$.

Let’s assume now that $n+1, 2n+1, \dots (p-1)n + 1$ are all not divisible by $p$Can any 2 of them be the same mod p?

No, because if, say, $in + 1 \equiv jn + 1 \mod p$ with $1 \leq i < j \leq p-1$, it means that $(i-j)n \equiv 0 \mod p$, which is impossible.

But notice now that none of them can have the same remainder as $n \mod p$ as well! Because, if, say, $in + 1 \equiv n \mod p$ which $1 \leq i \leq p-1$, it means that $(i-1)n + 1 \equiv 0 \mod p$, which is false by assumption.

Hence, there will always be some term in $n + 1, 2n + 1, \dots 16n+1$ that is divisible by $p$, i.e. $p \mid P(n)$.

In conclusion, $G = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 = \mathbf{510510}$. Done!