# Modular arithmetic: mod p-1 after exponentiation?

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$

]

-