0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Does this help en.wikipedia.org/wiki/Primitive_root_modulo_n ? $\endgroup$
    – lhf
    Apr 27 '14 at 20:24
  • $\begingroup$ 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. $\endgroup$ Apr 27 '14 at 20:29
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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