## Saturday, February 25, 2006

### Power Hungry. Topic: NT/Sequences and Series. Level: Olympiad.

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$.