# 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$? 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? 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$. May 8 '15 at 5:22
• This is IMO 2005 Problem 4. May 8 '15 at 15:35

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? 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? 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}
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 1, "equation": 0, "x-ck12": 0, "texerror": 0}