primitive_root

introduction

%%visits: 2 An element in mod modm that has the same order as |Z_m^×|. They have special properties like generating the group etc. ## intuition

Proof of lemma 4.10.

Let p be a prime. For d|p − 1 let W_d = {[a]_p ∈ ℤ_p^x : o([a]_p) = d} Then |W_d| ≤ ϕ(d)

Proof

Facts (proof of fact is non-examinable) Theorem 3.8 1. Let f(x) be a polynomial such as f(x) = a_nxⁿ + a_n − 1x^n − 1 + a_n − 2x^n − 2 + … + +a₁x + a₀, then f(x) ≅ 0 mod p. has at most n = deg(f) solutions in ℤ_p

2. Let G be a finite group and g ∈ G s.t o(g) = d then $j \in \mathbb{N}, o(g^{j}) = \frac{d}{gcd(j,d)}$

If $W_d = {} $ then 0 = |W_d| < ϕ(d)

Let [a]_p ∈ W_d. Observe, that since o([a]_p) = d, then a, a², a³…a^d are distinct (mod p). Consider, f(x) = x^d − 1 For each j = 1, 2, …, d, f(a^j) = (a^d)^j − 1 ≡ 1 − 1 ≡ 0 mod p. By fact 1, f(x) has at most d roots mod p.

Suppose [b]_p ∈ W_d then f(b) = 0 Hence [b]_p = [a]_p^j for some j = 1, …, d , where $d = o([b]_p) = o([a]_p^{j}) = \frac{d}{gcd(j,d}$ (by fact 2)

then gcd(j, d) = 1 Hence, [b]_p = [a]_p^j and 1 ≤ j ≤ d , gcd(j, d) = 1 And |{1 ≤ j ≤ d : gcd(j, d) = 1} = ϕ(d) hence proved.

Theorem 4.11

Not every element generates ℤ_p^×, for example, ℤ₅^× is something is generated by 2 but then it is impossible by 4 also. Note in 4.11, that it is generated by ϕ(p − 1) elements, which is never the order of the group.

rigour

primitive roo := Let m be a positive integer. If a is an integer co-prime to m such that the order of a modulo m equals ϕ(m) (i.e. o([a]_m) = ϕ(m), we say that a is a primitive root modulo m (The order is the ϕ function) ## exam clinic When trying to find roots, the primitive_root_test, and a calculator are very handy. But when using a calculator, be careful of rounding errors. Take a look at this question from the keats page.

{{file:../figures/screenshot_20211104_144651.png}}

Trying 27⁸ in the calculator (Casio fx-83GT Plus) gives 2.824295365 × 10¹¹, now the usual take away by 1 and divide by 31 gives 9110630209, so you may think this is the order, but by the primitive_root_test/ Lagranges_theorem this is impossible. But doing this in python, which has more access to memory, aka it can store more numbers gives.

{{file:../figures/screenshot_20211104_145111.png}}

examples and non-examples

resources

tags :math:

backlinks

• index_of_files.pd