Primitive Roots

Order

Suppose that

n \in ℕ_{1}

and

a \in cop (n)

, then we define

o (a, n) : = \min ({k \in ℕ_{1} : a^{k} \equiv 1 (\mod n)})

Order Exists iff There is a Power that Yields 1

As per title.

Suppose that

o_{n} (a)

exists, then we have at least one power that yields one. On the other hand if we have some power that yields one, then the set

{k \in ℕ_{1} : (a^{k} % n) = 1}

is non-empty so that the min exists.

Order Exists iff Coprime

We have that

a \in cop (n)

iff

o (a, n)

exists

If $a \in cop (n)$ then by euler's theorem we know that $a^{ϕ (n)} \equiv 1 (\mod n)$ therefore the order exists.

On the other hand if the oreder exists, then we have some $a^{k} \equiv 1 (\mod n)$ , now recall that $a x \equiv 1 (\mod n)$ has a solution if and only if $a \in cop (n)$ , but note we have a solution, becuase if $k = 1$ then $x = 1$ works, otherwise if $k \geq 2$ then $x = a^{k - 1}$ works therefore we have a solution in any case so that $a \in cop (n)$ as needed.

Primitive Roots are a Subset of Coprimes

pr (n) \subseteq cop (n)

a \in pr (n)

then

a

has an order, but

a

has an order iff

a \in cop (n)

, note that not everything that has an order is a primitive root.

Every Prime number has a Primitive Root

For any

p \in ℙ

pr (p) \neq \emptyset

Suppose for the sake of contradiction that it had no primitive roots therefore for any $a \in [1, \dots, p - 1]$ that $d : = o (a, p) < ϕ (p) = p - 1$ , but at the same time we know that $d | p - 1$ .

Now focusing on $a$ for a moment, we see that for any $k \in [1, \dots d]$ we have $o (a^{k}, n) = \frac{d}{\gcd (d, k) = d} ⟺ \gcd (d, k) = 1$ so there are at least $p h i (d)$ elements (using powers of $a$ ) that have order $d$ , and noting that since $a, a^{2}, \dots, a^{d}$ are distinct mod p, then so are these elements.

By lagranges theorem, the polynomial $x^{d} - 1$ has at most $d$ roots modulo $p$

Connection Between Primitive Roots of

p^{k}

and 2

p^{k}

Let

p \in ℙ_{3}

k \in ℕ_{1}

and

a \in pr (p^{k})

a \in pr (2 p^{k}) ⟺ a \in ℤ_{odd}

Suppose that $a \in pr (2 p^{k})$ then $a \in cop (2 p^{k})$ , therefore $a$ cannot be even, so that it must be odd.

Now suppose that $a \in ℤ_{odd}$ but for the sake of contradiction that $a \notin pr (2 p^{k})$ therefore $m : = o (a, 2 p^{k}) < ϕ (2 p^{k}) = ϕ (p^{k})$ and $a^{m} \equiv 1 (\mod 2 p^{k})$ then we have $a^{m} \equiv 1 (\mod p^{k})$ , but $a \in pr (p^{k})$ therefore $o (a, p^{k}) = ϕ (p^{k})$ but we have that $m < ϕ (p^{k})$ which is impossible because the order is the smallest power the yields one, but we've found a smaller one.

Order of a Primitive Root mod the next Power

Let

p \in ℙ

and

k \in ℕ_{1}

and suppose that

a \in pr (p^{k})

then

o_{p^{k + 1}} (a) \in {ϕ (p^{k}), ϕ (p^{k + 1})}

When a Primitive Remains a Primitive Root mod the next Power

Suppose

a \in pr (p^{k})

and

o_{p^{k + 1}} (a) \neq o_{p^{k}} (a)

then

a \in pr (p^{k + 1})

Every Power of an odd Prime has a Primitive Root

Let

p \in ℙ_{3}

be an odd prime, then

p^{k}

has a primitive root for every

k \in ℕ_{1}

Classification of the Existence of Primitive Roots

Let

n \in ℕ_{2}

, then

pr (n) \neq \emptyset

iff

n \in 2, 4, p^{k}, 2 p^{k}

where

p \in ℙ_{3}

and

k \in ℕ_{1}

A Number to the Phi n over Two is Congruent to 1 When it is not a Primitive Root

Let

n \in ℕ_{3}

such that

pr (n) = \emptyset

, and

c \in cop (n)

, then we have

c^{\frac{ϕ (n)}{2}} \equiv 1 (\mod n)

Since $pr (n) = \emptyset$ then $n \notin {2, 4, p^{k}, 2 p^{k}}$ for some $p \in ℙ_{3}$ and $k \in ℕ_{1}$ .

We will deal with the case when $n = 2^{k}$ for $k \in ℕ_{3}$ , we know that $c^{ϕ} (n) \equiv 1 (\mod n)$ and that $ϕ (n) = ϕ (2^{k}) = 2^{k - 1}$ and therefore $o_{n} (c) = 2^{j}$ for some $j \in [1, \dots, k - 1]$ , clearly we see $c \notin \emptyset = pr (n)$ and so we know that $j \neq k - 1$ because in that case we would have that $o_{n} (c) = ϕ (2^{k - 1})$ which implies that $pr (n) \neq \emptyset$ which is a contradiction. This proves that $o_{n} (c) = 2^{j} | 2^{k + 1} = \frac{ϕ (n)}{2}$ and therefore we have that $c^{\frac{ϕ (n)}{2}} \equiv 1 (\mod n)$ .