Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

3.7 Primitive Roots

Consider the powers of $3 (mod 7) :$ $3 (mod 7) :$

3^{1} \equiv 3, 3^{2} \equiv 2, 3^{3} \equiv 6, 3^{4} \equiv 4, 3^{5} \equiv 5, 3^{6} \equiv 1.

$3^{1} \equiv 3, 3^{2} \equiv 2, 3^{3} \equiv 6, 3^{4} \equiv 4, 3^{5} \equiv 5, 3^{6} \equiv 1.$

Note that we obtain all the nonzero congruence classes mod 7 as powers of 3. This means that 3 is a primitive root mod 7 (the term multiplicative generator might be better but is not as common). Similarly, every nonzero congruence class mod 13 is a power of 2, so 2 is a primitive root mod 13. However, $3^{3} \equiv 1 (mod 13),$ $3^{3} \equiv 1 (mod 13),$ so the powers of 3 mod 13 repeat much more frequently:

3^{1} \equiv 3, 3^{2} \equiv 9, 3^{3} \equiv 1, 3^{4} \equiv 3, 3^{5} \equiv 9, 3^{6} \equiv 1, \dots,

$3^{1} \equiv 3, 3^{2} \equiv 9, 3^{3} \equiv 1, 3^{4} \equiv 3, 3^{5} \equiv 9, 3^{6} \equiv 1, \dots,$

so only 1, 3, 9 are powers of 3. Therefore, 3 is not a primitive root mod 13. The primitive roots mod 13 are 2, 6, 7, 11.

In general, when $p$ $p$ is a prime, a primitive root mod $p$ $p$ is a number whose powers yield every nonzero class mod $p .$ $p .$ It can be shown that there are $ϕ (p - 1)$ $ϕ (p - 1)$ primitive roots mod $p .$ $p .$ In particular, there is always at least one. In practice, it is not difficult to find one, at least if the factorization of $p - 1$ $p - 1$ is known. See Exercise 54.

The following summarizes the main facts we need about primitive roots.

Proposition

Let $α$ $α$ be a primitive root for the prime $p .$ $p .$

Let $n$ $n$ be an integer. Then $α^{n} \equiv 1 (mod p)$ $α^{n} \equiv 1 (mod p)$ if and only if $n \equiv 0 (mod p - 1) .$ $n \equiv 0 (mod p - 1) .$
If $j$ $j$ and $k$ $k$ are integers, then $α^{j} \equiv α^{k} (mod p)$ $α^{j} \equiv α^{k} (mod p)$ if and only if $j \equiv k (mod p - 1) .$ $j \equiv k (mod p - 1) .$
A number $β$ $β$ is a primitive root mod $p$ $p$ if and only if $p - 1$ $p - 1$ is the smallest positive integer $k$ $k$ such that $β^{k} \equiv 1 (mod p) .$ $β^{k} \equiv 1 (mod p) .$

Proof. If $n \equiv 0 (mod p - 1),$ $n \equiv 0 (mod p - 1),$ then $n = (p - 1) m$ $n = (p - 1) m$ for some $m .$ $m .$ Therefore,

\begin{matrix} α^{n} \equiv {(α^{m})}^{p - 1} \equiv 1 & (mod p) \end{matrix}

$\begin{matrix} α^{n} \equiv {(α^{m})}^{p - 1} \equiv 1 & (mod p) \end{matrix}$

by Fermat’s theorem. Conversely, suppose $α^{n} \equiv 1 (mod p) .$ $α^{n} \equiv 1 (mod p) .$ We want to show that $p - 1$ $p - 1$ divides $n,$ $n,$ so we divide $p - 1$ $p - 1$ into $n$ $n$ and try to show that the remainder is 0. Write

\begin{matrix} n = (p - 1) q + r, & with 0 \leq r < p - 1 \end{matrix}

$\begin{matrix} n = (p - 1) q + r, & with 0 \leq r < p - 1 \end{matrix}$

(this is just division with quotient $q$ $q$ and remainder $r$ $r$ ). We have

\begin{matrix} 1 \equiv α^{n} \equiv {(α^{q})}^{p - 1} α^{r} \equiv 1 \cdot α^{r} \equiv α^{r} & (mod p) . \end{matrix}

$\begin{matrix} 1 \equiv α^{n} \equiv {(α^{q})}^{p - 1} α^{r} \equiv 1 \cdot α^{r} \equiv α^{r} & (mod p) . \end{matrix}$

Suppose $r > 0.$ $r > 0.$ If we consider the powers $α, α^{2}, \dots$ $α, α^{2}, \dots$ of $α (mod p),$ $α (mod p),$ then we get back to 1 after $r$ $r$ steps. Then

α^{r + 1} \equiv α, α^{r + 2} \equiv α^{2}, \dots

$α^{r + 1} \equiv α, α^{r + 2} \equiv α^{2}, \dots$

so the powers of $α (mod p)$ $α (mod p)$ yield only the $r$ $r$ numbers $α, α^{2}, \dots, 1 .$ $α, α^{2}, \dots, 1 .$ Since $r < p - 1,$ $r < p - 1,$ not every number mod $p$ $p$ can be a power of $α .$ $α .$ This contradicts the assumption that $α$ $α$ is a primitive root.

The only possibility that remains is that $r = 0 .$ $r = 0 .$ This means that $n = (p - 1) q,$ $n = (p - 1) q,$ so $p - 1$ $p - 1$ divides $n .$ $n .$ This proves part (1).

For part (2), assume that $j \geq k$ $j \geq k$ (if not, switch $j$ $j$ and $k$ $k$ ). Suppose that $α^{j} \equiv α^{k} (mod p) .$ $α^{j} \equiv α^{k} (mod p) .$ Dividing both sides by $α^{k}$ $α^{k}$ yields $α^{j - k} \equiv 1 (mod p) .$ $α^{j - k} \equiv 1 (mod p) .$ By part (1), $j - k \equiv 0 (mod p - 1),$ $j - k \equiv 0 (mod p - 1),$ so $j \equiv k (mod p - 1) .$ $j \equiv k (mod p - 1) .$ Conversely, if $j \equiv k (mod p - 1),$ $j \equiv k (mod p - 1),$ then $j - k \equiv 0 (mod p - 1),$ $j - k \equiv 0 (mod p - 1),$ so $α^{j - k} \equiv 1 (mod p),$ $α^{j - k} \equiv 1 (mod p),$ again by part (1). Multiplying by $α^{k}$ $α^{k}$ yields the result.

For part (3), if $β$ $β$ is a primitive root, then part (1) says that any integer $k$ $k$ with $β^{k} \equiv 1 mod p$ $β^{k} \equiv 1 mod p$ must be a multiple of $p - 1,$ $p - 1,$ so $k = p - 1$ $k = p - 1$ is the smallest. Conversely, suppose $k = p - 1$ $k = p - 1$ is the smallest. Look at the numbers $1, β, β^{2}, \dots, β^{p - 2} (mod p) .$ $1, β, β^{2}, \dots, β^{p - 2} (mod p) .$ If two are congruent mod $p,$ $p,$ say $β^{i} \equiv β^{j}$ $β^{i} \equiv β^{j}$ with $0 \leq i < j \leq p - 2,$ $0 \leq i < j \leq p - 2,$ then $β^{j - i} \equiv 1 (mod p)$ $β^{j - i} \equiv 1 (mod p)$ (note: $β^{p - 1} \equiv 1 (mod p)$ $β^{p - 1} \equiv 1 (mod p)$ implies that $β \equiv 0 (mod p),$ $β \equiv 0 (mod p),$ so we can divide by $β$ $β$ ). Since $0 < j - i < p - 1,$ $0 < j - i < p - 1,$ this contradicts the assumption that $k = p - 1$ $k = p - 1$ is smallest. Therefore, the numbers $1, β, β^{2}, \dots, β^{p - 2}$ $1, β, β^{2}, \dots, β^{p - 2}$ must be distinct mod $p .$ $p .$ Since there are $p - 1$ $p - 1$ numbers on this list and there are $p - 1$ $p - 1$ numbers $1, 2, 3, \dots, p - 1$ $1, 2, 3, \dots, p - 1$ mod $p,$ $p,$ the two lists must be the same, up to order. Therefore, each number on the list $1, 2, 3, \dots, p - 1$ $1, 2, 3, \dots, p - 1$ is congruent to a power of $β,$ $β,$ so $β$ $β$ is a primitive root mod $p .$ $p .$

Warning: $α$ $α$ is a primitive root mod $p$ $p$ if and only if $p - 1$ $p - 1$ is the smallest positive $n$ $n$ such that $α^{n} \equiv 1 (mod p) .$ $α^{n} \equiv 1 (mod p) .$ If you want to prove that $α$ $α$ is a primitive root, it does not suffice to prove that $α^{p - 1} \equiv 1 (mod p) .$ $α^{p - 1} \equiv 1 (mod p) .$ After all, Fermat’s theorem says that every $α$ $α$ satisfies this, as long as $α \equiv 0 (\mod p) .$ $α \equiv 0 (\mod p) .$ To prove that $α$ $α$ is a primitive root, you must show that $p - 1$ $p - 1$ is the smallest positive exponent $k$ $k$ such that $α^{k} \equiv 1 .$ $α^{k} \equiv 1 .$

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 3.7 Primitive Roots

Create new playlist

Sign In

Sign Up

Table of Contents for
3.7 Primitive Roots