[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 pCan 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!

Advertisements
This entry was posted in Grade 12, Intl/Regional and tagged , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s