Given prime $p, 0 < m < p$ and $ed \equiv 1 \pmod{p-1}$, prove $ m^{ed} \equiv m \pmod{p}$.
I get that this is hinting at a proof very similar to that of RSA, and that I have to consider when $\gcd(m,p)=1$ and when it doesn't. I also know that I need to use Euler's theorem and CRT. I just can't get past the $p-1$ passing itself into the mod from Euler's theorem. How should this proof look?
No comments:
Post a Comment