1
$\begingroup$

If $p$ is an odd prime, then $2^{p-1} \equiv p+1 \bmod 2p $.

I can't seem to apply Fermat's Little Theorem with this one. Can anyone give me a hint on how to prove this.

$\endgroup$
3
$\begingroup$

You can use the Chinese remainder theorem in this case, since $2$ and $p$ are relatively prime. You clearly have $2^{p-1} \equiv 0$ mod $2$ and $2^{p-1} \equiv 1$ mod $p$, by Fermat's little theorem. Now, using the CRT, you can find the class of $2^{p-1}$ mod $2p$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Or from $$2^{p-1}\equiv 0 \pmod{2} \Rightarrow 2^{p-1}\equiv p+1 \pmod{2}$$ since $p+1$ is even. And $$2^{p-1}\equiv 1 \pmod{p} \Rightarrow 2^{p-1}\equiv p+1 \pmod{p}$$ Or $$2 \mid (2^{p-1}-(p+1))$$ $$p \mid (2^{p-1}-(p+1))$$ and $\gcd(2,p)=1$, thus $$2p \mid (2^{p-1}-(p+1)) \Rightarrow 2^{p-1}\equiv p+1 \pmod{2p}$$

| cite | improve this answer | |
$\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.