Lemma of the Primitive Root theorem

27 Views Asked by At

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 ?

1

There are 1 best solutions below

0
On

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$).