Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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}\equiv 1 \pmod {2p}$$
Hence $a^p\equiv a$ and $a^{p-1}\equiv 1 \Rightarrow a^{2p-1}\equiv a \pmod {2p}$.
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$$
