Problem: (2005 IMO - #4) Determine all positive integers relatively prime to all the terms of the infinite sequence
$ a_n=2^n+3^n+6^n -1,\ n\geq 1 $.
Solution: We claim that the only such integer is $ 1 $. Consider any prime $ p > 3 $ and the term $ a_{p-2} $. We have
$ a_{p-2} = 2^{p-2}+3^{p-2}+6^{p-2}-1 = \frac{2^{p-1}}{2}+\frac{3^{p-1}}{3}+\frac{6^{p-1}}{6}-1 $,
which, by taking a common denominator and factoring, becomes
$ a_{p-2} = \frac{(2^{p-1}+2)(3^{p-1}+3)-12}{6} $.
But by Fermat's Little Theorem, we have $ 2^{p-1} \equiv 3^{p-1} \equiv 1 \pmod{p} $, so
$ a_{p-2} \equiv \frac{(1+2)(1+3)-12}{6} \equiv 0 \pmod{p} $.
So we have shown that $ p|a_{p-2} $ for all primes $ p > 3 $. Noting that $ a_2 = 48 $, which is divisible by both $ 2 $ and $ 3 $, we have that every positive integer divisible by a prime is not relatively prime to all terms in the sequence (since at least one term is divisible by every prime). Hence the only possible number is $ 1 $, as claimed. QED.
--------------------
Comment: The quickest way to find this solution was seeing that $ \frac{1}{2}+\frac{1}{3}+\frac{1}{6}-1 = 0 $. And since multiplicative inverses always exist modulo a prime, the term $ a_{p-2} $ is divisible by $ p $.
No comments:
Post a Comment