**2016 PAMO 3.** For any positive integer , we define the integer as

Find the greatest common divisor of the integers .

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

- .
- . Hence, must be a factor of .
- . 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 , 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 ‘s factorisation?** Since , must have the form

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

Indeed, it is the case. For any prime , consider . For any positive integer ,

Hence, while . It thus follows that .

Let’s think about the factor 2 for a moment. **Is it obvious that for every , we have ?** Well, yes! That’s because if is even, the term is divisible by 2; if it’s odd, then the term is divisible by 2. Hence, we have .

**Again, can we replicate this argument for the other possible primes in ?** Yes! Let be a prime in . For any ,

*Case 1:* . Then obviously .

*Case 2:* . If there exists some such that , then obviously .

Let’s assume now that are all not divisible by . **Can any 2 of them be the same mod p?**

No, because if, say, with , it means that , which is impossible.

**But notice now that none of them can have the same remainder as as well!** Because, if, say, which , it means that , which is false by assumption.

Hence, there will always be some term in that is divisible by , i.e. .

In conclusion, . **Done!**

### Like this:

Like Loading...

*Related*