# $g^i\equiv g^j (mod p)$ implies $g^{i-j}\equiv 1 (mod p)$

How do I prove this? I feel like its obvious but can't think how to do it for reason. p is a prime by the way.

Is it also true that $g^i\equiv g^j (mod p^2)$ implies $g^{i-j}\equiv 1 (mod p^2)$?

Thanks

• Thats true only when $\gcd(g,p)=1$. The result follows from below property of congruences: $$ca\equiv cb\pmod{n}\implies a\equiv b\pmod{n/d}$$ where $d=\gcd(c,n)$ – ganeshie8 Mar 1 '15 at 13:27

## 1 Answer

This is obvious, if you express it as statement about groups.

Let $[g]\in (\mathbb{Z}/n\mathbb{Z})^\times$. Recall, that $(\mathbb{Z}/n\mathbb{Z})^\times$ is the subgroup of invertible elements of $(\mathbb{Z}/n\mathbb{Z},\cdot)$, and that a $[g]\in \mathbb{Z}/n\mathbb{Z}$ is invertible if and only if $\gcd(g,n)=1$.

Then, if $\gcd(g,n)=1$ and $g^i \equiv g^j \pmod{n}$, then we have $[g]^i = [g]^j$ (in ($\mathbb{Z}/n\mathbb{Z})^\times$). Since $[g]^i \cdot ([g]^j)^{-1} = [g]^i\cdot [g]^{-j} = [g]^{i-j}$ and $[g]^j\cdot ([g]^j)^{-1} = $, we have $[g]^{i-j} = $. That is: $$g^{i-j} \equiv 1 \pmod{n}$$