I keep coming across proofs that seem to use the following derivation, but I'm unsure where it comes from. What theorem shows that this is a correct step to take?
$ g^{x} = g^y$ mod $p$ $\iff$ $x = y$ mod $p - 1$. Especially the $p-1$ part confuses me, obviously. I don't see why that should not be mod $p$.
I have reason to believe it has something to do with the Euler totient, but that could be wrong.
EDIT: I should add: $g$ is a primitive root.
If $g$ is a primitive root modulo $p,ord_pg=p-1$
If $g^x\equiv g^y\pmod p\iff g^{x-y}\equiv1\pmod p\iff ord_pg\mid (x-y)$ (Proof below)
$\implies (p-1)\mid (x-y)$
This can be generalized to any composite $m>4$ having primitive root.So, $m$ must be of the form $p^e,2p^e$ where $p$ is an odd prime.
Now, $\phi(p^e)=p^{e-1}(p-1), \phi(2p^e)=phi(2)\phi(p^e)=p^{e-1}(p-1)$
In either cases if $g$ is a primitive root modulo $m,ord_pg=\phi(m)=p^{e-1}(p-1)$
If $g^x\equiv g^y\pmod m\iff g^{x-y}\equiv1\pmod m\iff ord_mg\mid (x-y)$ $\implies p^{e-1}(p-1)\mid (x-y)$
[
Proof :
Let $ord_ma=d$ and $a^n\equiv1\pmod m$ and $n=q\cdot d+r$ where $0\le r<d$
So, $a^{q\cdot d+r}\equiv1\pmod m\implies a^r\cdot (a^d)^q\equiv1\implies a^r\equiv1\pmod m$
But $d$ is the smallest positive integer such that $a^d\equiv1\pmod m$
$\implies r=0\implies n=q\cdot d$ i.e., $d\mid n$
]