# Primitive element modulo prime p

Let $p$ be an odd prime and consider the set $\mathbb{Z}_p$ of integers modulo the prime $p$. An element $g$ in $\mathbb{Z}_p$ is called a primitive element module the prime $p$ if the element $g$ has multiplicative order $p - 1$ modulo the prime $p$. If $g$ is a primitive element then every non-zero element $h$ in $\mathbb{Z}_p$ can be written as a power of $g$; i.e., every non-zero $h$ can be written in the form $h = g^e$ for some non-negative integer $e$.

Whether for each odd prime $p$ there is always such a primitive element? How many are there in total? How do you get them all given one of them, and does on find?

I am finding it hard to understand this questions, So if anyone can help me with explanation about this question with example.

• Does this help en.wikipedia.org/wiki/Primitive_root_modulo_n ?
– lhf
Apr 27 '14 at 20:24
• I did look that up before posting it here. It helps to a limit. I definitely don't understand h = g^e part of the question. Apr 27 '14 at 20:29

Let $F$ be a field. The primitive $n$th roots in $F$ are the elements $a\in F$ such that $a^n=1$ and $a^k\ne 1$ for $1\le k<n$.

Claim. For each $n$ there exists a polynomial $\Phi_n(X)\in F[X]$ that has as roots precisely the primitive $n$th roots of $F$.

Proof: The case $n=1$ is easy, as the only primitive first root is $1$. We let $\Phi_1(X)=X-1$. Assume by induction that we already have $\Phi_k$ for all $k<n$. If $d\mid n$ then $\Phi_d\mid X^n-1$ because $a^d=1$ implies $a^n=1$. In fact, sonce $\Phi_d$ and $\Phi_e$ have no roots in common for $d\ne e$, we conclude that $\prod_{d\mid n\atop d<n}\Phi_d(X)$ divides $X^n-1$. Let $$\tag1 \Phi_n(X)=\frac{X^n-1}{\prod_{d\mid n\atop d<n}\Phi_d(X)}.$$ By construction $\Phi_n(a)=0$ iff $a^n=1$ but $a^d\ne 1$ for all $d\mid n$. $_\square$

Proposition. If $X^n-1$ has $n$ distinct roots in $F$, then $\deg\Phi_d(X)=\phi(d)$ for all $d\mid n$.

Proof: Recall from elementary number theory that $\sum_{d\mid n}\phi(d)=n$. Hence if we define $f$ recursively by $f(1)=1$ and $f(k)=k-\sum_{d\mid k\atop d<k}f(d)$, then $f(k)=\phi(k)$ for all $k$. By $(1)$, the recursion for $f$ is also the recursion for the degrees of $\Phi_k$, at least for $k\mid n$. The conclusion follows. $\_square$

Corollary. If $X^n-1$ has $n$ distinct roots in $F$, then $F$ has $\phi(n)$ primitive $n$th roots. $_\square$

Now note that $\mathbb Z_p$ is a field and by Fermat $X^{p-1}-1$ has $p-1$ roots in this field. We conclude that there are $\phi(p-1)>0$ primitive roots. If $a$ is one primitive root, then all other nonzero elemenst of $\mathbb Z_p$ are powers $a^k$, $1\le k\le p-1$. If $\gcd(k,p-1)>1$ten clearly $a^k$ is not primitive, hence at most the $\phi(p-1)$ elements $a^k$ where $\gcd(k,p-1)=1$ are primitive. On the other hand, there are exactly $\phi(p-1)$ primitive roots, hence each $a^k$ with $\gcd(k,p-1)=1$ indeed is a primitive root.

To prove the existence of a primitive root, we need the following theorem:

Let $f$ be an integer polynomial of degree $n \pmod p$. Then $f \equiv 0 \pmod p$ has at most n solutions.

Now consider the multiplicative group $\{1, 2, \cdots, p-1 \}$ modulo prime $p$. If $h$ denotes the maximum order of any element, then it follows that $x^h \equiv 1 \pmod p$ for every element in the group. But by the theorem listed above, the congruence has $p-1$ solutions so we must have $h \ge p-1$. Hence $h = p-1$ by F(Little)T and we are done.

Now it can be shown that there are $\phi(p-1)$ primitive roots. This obviously makes sense since we would have to raise then to $p-1$ power since raising them to any other power less than $p-1$ would not suffice.

To answer your question about which $n \in \mathbb{N}$ this can occur for, this is a theorem proved by Gauss, with earlier contributions from Euler, Legendre and Lagrange; it is called the primitive root theorem:

The natural number $n > 1$ has a primitive root if and only if $n \in \{2, 4, p^a, 2p^a\}$ where $p$ is an odd prime. (Mollin, Fundamental Number Theory, pg. 151).