13
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ Is it any use that $2^n+3^n+6^n-1 = (2^n+1)(3^n+1)-2$? $\endgroup$ – marty cohen May 8 '15 at 4:59
  • 2
    $\begingroup$ 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? $\endgroup$ – mataxu May 8 '15 at 5:02
  • $\begingroup$ 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$. $\endgroup$ – marty cohen May 8 '15 at 5:22
  • $\begingroup$ This is IMO 2005 Problem 4. $\endgroup$ – user26486 May 8 '15 at 15:35
19
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – mataxu May 8 '15 at 5:15
  • 1
    $\begingroup$ 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$. $\endgroup$ – k1.M May 8 '15 at 5:18
9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – mataxu May 8 '15 at 5:07
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.