# Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$.

So the problem states: Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$.

I was thinking about trying to prove this using the corollary to Fermat's Little Theorem, that for every prime $p$, $a^{n-1}\equiv 1 \pmod {p}$, but I can't think about how to go about doing that.

Any help would be greatly appreciated!

• Is it any use that $2^n+3^n+6^n-1 = (2^n+1)(3^n+1)-2$? – marty cohen May 8 '15 at 4:59
• I'm kind of confused about what you mean. Yeah, it can be factored like that, but how would I use that in Fermat's Little Theorem? – mataxu May 8 '15 at 5:02
• I didn't know. However, the answers below, which use n=p-2, allow the factorization to continue $(2^{p-2}+1)(3^{p-2}+1)-2 = (1/2+1)(1/3+1)-2=(3/2)(4/3)-2=2-2=0$. – marty cohen May 8 '15 at 5:22
• This is IMO 2005 Problem 4. – user26486 May 8 '15 at 15:35

## 3 Answers

Observe that for $p>3$ we have $$6(2^{p-2}+3^{p-2}+6^{p-2}-1)\equiv 3+2+1-6\equiv 0\pmod p$$

• Ohh that's pretty cool. So then knowing that this is true for all $p > 3$, if we can show that the case for $p=2$, the only prime not proven by this, then we've completed the proof? – mataxu May 8 '15 at 5:15
• You just need to prove $p=2,p=3$ which in the case $p=2$ take $n=0$ and in the case $p=3$ take $n=2$. – k1.M May 8 '15 at 5:18

The key hint is that rationally $\frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 1$. You need to do something analogous mod $p$. Since you need $n>0$, Fermat's little theorem will indeed be useful.

• Ok, I'm gonna try to think through this a little bit: So we know that $2^{n}+3^{n}+6^{n} \equiv 1$ mod $p$. Should my next step be to find some $a$ that satisfies FLT, or am I on the wrong track? – mataxu May 8 '15 at 5:07

From FLT, $a^{p-2} \equiv a^{-1}$. Choosing $n = p-2$,

\begin{align} 2^n + 3^n + 6^n - 1& \equiv 2^{-1} + 3^{-1} + 6^{-1} - 1\\ & \equiv 6^{-1} \cdot 6 \cdot (2^{-1} + 3^{-1} + 6^{-1}) - 1\\ & \equiv 6^{-1} \cdot (3 + 2 + 1) - 1\\ & \equiv 6^{-1} \cdot 6 - 1\\ & \equiv 1 - 1 \equiv 0\\ \end{align}