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?
On
It's a special case of this mod exponent reduction law (crucial to master for problems like this)
Lemma $\ \bmod n\!:\,\ \color{#c00}{a^{\large k}\equiv 1}\,\Rightarrow\,a^{\large j}\equiv a^{\large j\bmod\color{#c00} k}$
Proof $\ $ Dividing $\ j\div k\,\Rightarrow\, j = r + k\,q\ $ for $\ r = j\bmod k = $ remainder, and $\,q = $ quotient,
hence $\bmod n\!:\,\ a^{\large j}\equiv a^{\large r+kq}\equiv a^{\large r}(\color{#c00}{a^{\large k}})^{\large q}\equiv a^{\large r}\color{#c00}1^{\large q}\equiv a^{\large r}$
Thus $\bmod p\!:\,\ \color{#c00}{m^{\large p-1}\equiv 1}\,\Rightarrow\, m^{\large ed}\equiv m^{\large ed\bmod\color{#c00}{p-1}}\equiv m^{\large 1}$
First consider gcd(m,p). p is prime and p > m.
Conclude gcd(m,p) = 1.
By Euler's Theorem $ m^{\phi(p)} \equiv 1 \mod p, ed \equiv 1 \mod \phi(p), ed \equiv 1 +k\phi(p),k$ is a constant integer and then $(m^{e})^d = m^{ed} \equiv m^{1+k\phi(p)}\\ \\ m^{ed} \equiv m *m^{k\phi(p)}\\m^{ed} \equiv m *1\mod p\\m^{ed} \equiv m \mod p$