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!