0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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)$ $\endgroup$ – ganeshie8 Mar 1 '15 at 13:27
1
$\begingroup$

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} = [1]$, we have $[g]^{i-j} = [1]$. That is: $$g^{i-j} \equiv 1 \pmod{n}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.