Let's take a primitive root $g$ for a prime $p$. Then if $j$ and $k$ are integers, then $g^{k}\equiv g^{j} \quad mod \,p$ only if $k \equiv > j \quad mod \, p-1$
Is it possible to understand intuitively why ?
Let's take a primitive root $g$ for a prime $p$. Then if $j$ and $k$ are integers, then $g^{k}\equiv g^{j} \quad mod \,p$ only if $k \equiv > j \quad mod \, p-1$
Is it possible to understand intuitively why ?
Copyright © 2021 JogjaFile Inc.
Because if $g^k\equiv g^j$ (mod $p$) then $g^{k-j}\equiv 1$(mod $p$). Since $g$ is a primitive root we know that $g^i\equiv 1$(mod $p$) if and only if $i$ is divisible by $\varphi(p)=p-1$. This simply follows from the definition of a primitive root. Hence we must have $k-j\equiv 0$(mod $p-1$).