# If p is an odd prime, prove that $a^{2p-1} \equiv a \pmod{ 2p}$

Let $m = 2p$

If p is an odd prime, prove that $a^{2p - 1} \equiv a \pmod {2p} \iff a^{m - 1} \equiv a \pmod m$.

I have no idea on how to start. I was trying to find a form such that

$a^{m - 2} \equiv 1 \pmod m$. But I got stuck. Can someone give me a hint here?

• Can you give the complete list of the even primes? It is a short one. – Martigan Feb 13 '15 at 10:00
• @Martigan: It is widely used in math books and articles. – mesel Feb 13 '15 at 10:03
• @Martigan, only 2 – JOX Feb 13 '15 at 10:04
• Your title speaks of $a^{2p}\equiv a$ but your question of $a^{2p-1}\equiv a$. – drhab Feb 13 '15 at 10:40
• Oh thanks, I made a mistake – JOX Feb 13 '15 at 10:44

## 3 Answers

Hint: $$\phi(2p)=\phi(p)$$ for all odd primes where $\phi$ is the Euler-phi function.

Edit:
$$a^{\phi(2p)}\equiv a^{\phi(p)}\equiv a^{p-1}\equiv1 \ mod \ 2p$$

Hence $a^p\equiv a$ and $a^{p-1}\equiv 1 \implies a^{2p-1}\equiv a \ mod \ 2p$.

• I was trying to use Fermat's theorem but I got confused because a and m are not always relatively prime. – JOX Feb 13 '15 at 10:11
• @JOX: Are you familiar with the theorem $$a^{\phi(n)}\equiv 1 \ mod \ n$$. – mesel Feb 13 '15 at 10:15
• @mesel yes I am familiar with it, I can determine that $a^{p-1}\equiv 1 \mod p$ but from there I can't advance. – JOX Feb 13 '15 at 10:45

By the chinese remainder theorem, congruence modulo $2p$ is uniquely determined by modulo $p$ and modulo $2$ together (this is true for any odd number $p$).

By Fermat's small theorem, we have $a^{2p-1} = a^p\cdot a^{p-1} \equiv a\cdot 1 =a\pmod p$. This is true for any prime $p$. Also, we must have $a^{2p-1} \equiv a\pmod 2$, since that's true for any natural exponent. Therefore, we have $$a^{2p-1} \equiv \begin{cases}a \pmod p\\ a \pmod 2\end{cases}$$ which gives the desired $a^{2p-1} \equiv a \pmod {2p}$.

Fermat: $p\mid a^{p}-a$ so $p\mid\left(a^{p-1}+1\right)\left(a^{p}-a\right)=a^{2p-1}-a$.

Next to that $2\mid a\iff2\mid a^{2p-1}$ so that $2\mid a^{2p-1}-a$.

So $2$ and $p$ are two distinct ($p$ is odd, so $p\neq2$) primes both dividing $a^{2p-1}-a$.

Conclusion: $$2p\mid a^{2p-1}-a$$