CH4 Primitive roots

Question 1

EULERS THM recall

Answer 1

if gcd(a, n) = 1,
(coprime)

then aᵠ⁽ⁿ⁾ ≡ 1 (mod n).

for what values of k we have a^k ≡ 1 (mod n).

There may well be a smaller k such that ak ≡ 1 (mod n) (recall Exercise 2.2.5).

Question 2

ϕ(n) can be the maximal power when n

Answer 2

is
a power of an odd prime and a few other cases.

Some of you may recognise that this happens precisely when (Z/nZ)× is a cyclic group

Question 3

Definition 4.1.1
(Order)

Answer 3

Let a and n be coprime.

The order of a modulo n is the least d > 0 such that

(smallest positive integer d)

aᵈ ≡ 1 (mod n).

(how many powers to take to get to 1)

Question 4

lagranges thm and order of an element

Answer 4

The order of an element always divides the sizes of group (Z/nZ)× . The size of this group is precisely ᵠ⁽ⁿ⁾

consequence of Lagranges thm in group theory

Question 5

a=7 n =52

The order of 7 modulo 52?

Answer 5

The order of 7 modulo 52

(we could take all the powers up to and check)

We only need to consider
ϕ(52)=ϕ(4)ϕ(13)
= 2 x 12
=24

(or found by 52(1-1/2)(1-(1/13))
As the order of 7 divides 24 as 7^24 ≡ 1 (mod 52)).

So I only consider the powers of 7 that are divisors of 24:
1,2,4,8,3,6,8,12,24

7¹=7 (not the order of 7)
7²=49 ≡49≡-3 (mod 52)
7⁴= (49)²≡(-3)²=9 (mod 52)
7⁸=9²=81≡29 (mod 52)
7³= 7².7 = ≡(-3).7 =-21 ≡31 (mod 52)
7⁶=(7²)³≡(-3)³= -27 ≡25 (mod 52)
7¹²≡25²≡1 (mod 52)
7²⁴=

so d=12 is the order of 7 mod 52

Question 6

E.g ϕ(12)

Answer 6

Example: For
n=12, only 1,5, 7, 11 are coprime with 12 so φ(12)=4
.

The prime factor decomposition 12
=2^2×3^1

formula
φ(12)=((2-1) x 2²⁻¹ ) x ((3-1) x 3¹⁻¹
)
= 2 x2 =4

φ(12)=
12(1- 1/2)(1- 1/3) = 12 x (1/2) x (2/3) = 4

Question 7

How to calculate phi(n) if n is prime?

Answer 7

if n is a prime number, then
φ(n)=n−1

Question 8

What are Euler’s totient properties?

Answer 8

The Euler indicator is an essential function of modular arithmetic:

— A positive integer p is a prime number IFF φ(p)=p−1
— The value φ(n)
is even for all n>2
— φ(ab)=φ(a)φ(b)dφ(d) with d the GCD of a and b
— If a and b are coprimes (relatively primes), then φ(a×b)=φ(a)×φ(b)
— If a divides b then φ(a)∣φ(b)
— If a is even, φ(2a)=2φ(a)
— If a is odd, φ(2a)=φ(a)

The sequence of values of Phi(n) is 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, etc.

Question 9

Exercise 4.1.2. Suppose that n is coprime with 10 and that 10 has order d modulo n.
Show that the decimal expansion of 1/n
has period of length d.

Answer 9

In Exercise 2.2.5, we have used that the length of the period of 1/p is the
least d such that 10^d ≡ 1 (mod p). Let us repeat why, in a slightly different way:
recall that 10k
n has the decimal expansion of 1n
shifted to the left by k places. If we
divide 10k by n and write 10k = qkn + rk, with 0 ≤ rk < n, then
10^k / n= q_k + (r_k/n)

Since q_k is an integer and 0 ≤ r_k /n < 1, the first k digits of 1/n are the digits of the
integer q_k (shifted back by k places), and the remaining digits are the digits of r_k/n
(also shifted to the right by k places).

By construction, r_k is the remainder of 10^k by n, thus the least integer e such that the digits repeat themselves is the least e > 0 such that r_{k+e} = r_k, that is to say 10^{k+e} ≡ 10^k (mod n). This is the least e > 0 such that 10^e ≡ 1 (mod n), so e = d, as desired.

Question 10

order d what can it be?

Answer 10

By Euler’s Theorem, d is at most ϕ(n), and in fact it divides ϕ(n) as we observed
in Exercise 2.2.5. Alternatively, Lagrange’s theorem says that d divides the size of
(Z/nZ)×, thus it divides ϕ(n).

Question 11

Proposition 4.1.4.

Answer 11

Let a and n be coprime
gcd(a,n)=1
and let d be the order of a modulo n.
Then (for any power of a s.t)
aᵐ ≡ 1 (mod n)
IFF
d | m;

more generally,
(if we have two powers of a giving the same value)
aᶦ ≡ aʲ (mod n)
IFF
i ≡ j (mod d).

Question 12

PROOF prop 1.4.1

Let a and n be coprime
gcd(a,n)=1
and let d be the order of a modulo n.
Then (for any power of a s.t)
aᵐ ≡ 1 (mod n)
IFF
d | m;

more generally,
(if we have two powers of a giving the same value)
aᶦ ≡ aʲ (mod n)
IFF
i ≡ j (mod d).

Answer 12

Suppose aᶦ ≡ aʲ (mod n).
WLOG i >j
(because a is coprime with m, we can divide by aʲ and still have coprime as gcd(a,n)=1)
aᶦ⁻ʲ≡ 1 (mod n)

Write
(i − j) = qd + r where 0 ≤ r < d.
(above by the division algorithm)

Then
(aᵈ)^q. aʳ
aᶦ⁻ʲ ≡ aʳ (mod n).

as aᵈ≡ 1 by defn of order
as aᶦ⁻ʲ≡ 1 (mod n)
by defn of order has to be the least possible powerso d |(i-j) so r=0

Since d is the order of a, we
find that aᶦ⁻ʲ≡ 1 if and only if r = 0, thus if and only if (i − j) ≡ 0 (mod d).

Question 15

Example 4.1.5. If we know the order of 7 is 12 mod 52 what else?

Answer 15

The powers 7^1, 7^5, 7^7, 7^11 all have order 12 modulo 52

From the proposition
powers of 7 s.t the power is

7^12 is 1
multiplying 7^11 by 7 =7^12 ≡1

this is the multiplicative inverse of 7, multiplicative inverses preserve order

7 order 12 then

7^11 also has order 12

5+7=12 so when you multiply together they show they have same order as are inverses as =1
it happens they have the same order as 5,7 are coprime with 12

Question 16

Suppose we have a,b coprime with n
and product
ab ≡1 mod n

then orders

Answer 16

gcd(a,n)=gcd(b,n)=1

order of a and b will be the same:

let d= order of a mod n
then
a^d ≡1 mod n

(ab)^d= a^d.b^d ≡1. b^d mod n
as ab ≡1
(ab)^d ≡1
thus
b^d ≡ 1 mod n

showing multiplicative inverses preserve order

Question 17

extra

Answer 17

Extra. Computing the order of a modulo n is called Discrete Logarithm Problem. It is one of the several open problems in computational number theory and cryptography: as of today, no efficient algorithm is known (meaning that the number of steps required grows faster than any power of the number of binary digits of a). Solving the discrete logarithm problem efficiently would break certain cryptographic schemes.

Question 18

Definition 4.1.6 (Primitive root)

Answer 18

An integer a is a primitive root modulo n or primitive root of n

if a is coprime to n and

it has order ϕ(n) modulo n.

(ie it is an element of the biggest possible order it could be;
the group (Z/nz)x is cyclic ;
if a is a primitive root if you take all of the powers of a up until phi(n) you generate all elements mod n)

In group theoretic terms, a is a primitive root of n when a generates the group (Z/nZ)×.
Thus primitive roots exist only when that group is cyclic.

by FlittleThm -euler a^(ph(n)) is always congruent to 1 mod n

Question 19

Example 4.1.7. There are no primitive roots modulo 8.

dont always exist

Answer 19

n=8
coprime elements 1,3,5,7
orders of these
2:
1^1 ≡ 3^2 ≡ 5^2 ≡ 7^2 ≡ 1 (mod 8)
even though
ϕ(8) = 8(1 − 1/2)= 4.

none has order 4

shows x^2-1≡0 mod 8 has 4 roots

Question 20

primitive roots for n=2

Answer 20

one element coprime 1

phi(n)=1 trivial

1 prmitive root mod 2

Question 21

primitive roots for n=3

Answer 21

order of 1 mod 3: order 1 phi(3)=2
so 1 is not a primitive root
(1 is only a primitive root in one case

order of 2 mod 3 is 2
2^2≡ 1 mod 3

1,2 coprime elements
phi(3)=2
2^2 ≡1 mod 3

2 is primitive root mod 3

Question 22

primitive roots for n=4

Answer 22

coprime 1,3

3^2=9 ≡ 1 mod 4
phi(4)= 4(1-1/2)=2

so 3 is a primitive root

Question 23

n=5 a =2

Answer 23

2^1=2 mod 5
2^2=4 mod 5
2^3 = 8≡ 3 mod 5
2^4= 16 ≡ 1 mod 5

so the order of 2 mod 5 is 4,
primitive root is 2 mod 5

4,1,3, 2 actually these numbers are all those below 5 that are coprime to 5
General pattern: once we know the order we can find with no repeats, links to future lemma

Question 24

what values of n give primitive roots

Find for which n there are primitive roots
(twice)

Answer 24

primes
powers of primes

2 x powers of primes

and nothing else

Finding a primitive root is all about the solutions of the equation x^{ϕ(n)} − 1 ≡ 0
(mod n).

Question 25

Theorem 4.2.1 (Lagrange)

Answer 25

Let p be a prime and f (x) be a polynomial of degree d with integer coefficients and leading coefficient not divisible by p (x^d).

Then the equation f (x) ≡ 0 (mod p)

has at most d pairwise incongruent solutions modulo p.

(In other words, in any complete set of residues modulo p there are at most d solutions.)

Question 26

PROOF OF
Let p be a prime and f (x) be a polynomial of degree d with integer coefficients and leading coefficient not divisible by p (x^d).

Then the equation f (x) ≡ 0 (mod p)

has at most d pairwise incongruent solutions modulo p.

(In other words, in any complete set of residues modulo p there are at most d solutions.)

Answer 26

Proceed by induction on d

base:
d=1
write f(x)=ax+b.
Suppose that we have 2 sols x and x’:
f (x) ≡ f (x′) ≡ 0 (mod p). Then ax + b ≡ ax′ + b, so ax ≡ ax′, so x ≡ x′ given that
p ∤ a. Thus, there is at most one solution modulo p.

Induction hypothesis:
assume the conclusion for a given degree d, and take f (x) of degree d + 1. (We will show it has at most d+1 solutions)

If f (x) ≡ 0 mod p has no solutions, we are done.

Otherwise, suppose that f (c) ≡ 0 for some integer c. Use polynomial division: we have

f (x) = (x − c)q(x) + r for some polynomial
q(x) and some r ∈ Z.
(actually r(x) but as deg(r(x)) < deg (x-c)=1 deg must be 0)

deg(q(x))= deg(f(x))-1=d thus we use induction hypothesis on q
Now q(x) must have degree d and its leading coefficient is the same as that of f (x), and in particular it is not divisible by p.

Moreover, f (c) = r ≡ 0.
It follows that f (x) ≡ 0 if and only if (x − c)q(x) ≡ 0, thus if and only if x ≡ c or
q(x) ≡ 0 because p is prime. By inductive hypothesis, q(x) ≡ 0 has at most d solutions
modulo p, so f (x) ≡ 0 has at most d + 1 solutions modulo p.

Question 27

Example 4.2.2. This fails miserably for non-primes:

Answer 27

Example 4.2.2. This fails miserably for non-primes: for instance, we have seen that
x2 − 1 ≡ 0 (mod 8) has solutions 1, 3, 5, 7 modulo 8, which are definitely more than 2.

Question 28

Corollary 4.2.3. If p is prime and d | (p − 1), then the equation x^d − 1 ≡ 0 (mod p) has

Answer 28

Corollary 4.2.3. If p is prime and d | (p − 1), then the equation
x^d − 1 ≡ 0 (mod p)
has exactly d solutions up to congruence modulo p.

(due to thm has at most d solutions, we show exactly d incongruent sols)

Question 29

PROOF of corollary

Corollary 4.2.3. If p is prime and d | (p − 1), then the equation
x^d − 1 ≡ 0 (mod p)
has exactly d solutions up to congruence modulo p.

Answer 29

Recall that x^{p−1} − 1 ≡ 0 (mod p) has exactly p − 1 solutions modulo p:1, 2, . . . , p − 1

Because d|(p-1) we can take
p-1=kd for some integer k

Then
x^{p-1}-1 = x^{kd} − 1
= (x^{d} − 1)· (x^{d(k−1)}+ x^{d(k−2)}+ · · · +x^d + 1).

factorisation comes from the geometric sum
By FLittleT: any number coprime to p satisfies
a^{p-1} ≡1 mod p.
So this LHS has exactly p-1 solutions.
Take any # s.t we get 0 mod p, thus the product of the two factors must be 0 mod p, this means p divides either factor (we took any # s,t for every choice of integer coprime to p)

Now by lagranges,
second factor this has at most d(k-1) solutions
so the d remaining sols must be for the first factor

notes:

Since p is prime, whenever x^{p−1} − 1≡ 0, one of the two factors on the r.h.s. must be
congruent to 0 as well.

By Theorem 4.2.1, the second factor has at most d(k − 1) solutions modulo p, so the
first factor must have at least p − 1 − d(k − 1) = d solutions. By Theorem 4.2.1 again, it
cannot have more than d, so x^{d} − 1 ≡ 0 has exactly d solutions modulo p

Question 30

recall formula

Answer 30

sum_{d|n} phi(d) = n

Question 31

Lemma 4.3.1. If p is prime and a has order d modulo p, then

(and a coprime to p)

Answer 31

If p is prime and a has order d modulo p, then

(1) The powers a, a², . . . , aᵈ are a complete set of incongruent solutions to the equation
xᵈ − 1 ≡ 0 (mod p), and

(2) The powers aᵏ
with 1 ≤ k ≤ d
and
gcd(k, d) = 1
are a complete set of incongruent elements of order d modulo p.

Then these are all primitive ___ of elements of order d mod p

1 says:(number of sols at most d prev thm, lemma says all are sols and they are also distinct so exactly d sols)

2: look at ones where the power k is coprime to d, the order is 4 say and exponents coprime to 4 are 1 and 3 lemma says both 2^1 and 2^4 are order 4. 2^2 doesnt have order 4 as the order is 2 and gcd isnt 1 so lemma cant be applied?

Question 32

PROOF OF
If p is prime and a has order d modulo p, then

(1) The powers a, a², . . . , aᵈ are a complete set of incongruent solutions to the equation
xᵈ − 1 ≡ 0 (mod p), and

(2) The powers aᵏ
with 1 ≤ k ≤ d
and
gcd(k, d) = 1
are a complete set of incongruent elements of order d modulo p.

Answer 32

(1) By Proposition 4.1.4,
aᶦ≡ aʲ (mod p)
IFF i ≡ j (mod p).
Therefore, the powers a, a², . . . , aᵈ are pairwise incongruent modulo p.

Moreover, since
(aᵏ)ᵈ= (aᵈ)ᵏ ≡ 1,
they are all solutions to xᵈ − 1 ≡ 0. mod p
By Theorem 4.2.1, every other solution is congruent to aᵏ for some k.

(2) (we need to prove they have order d and not less and that they generate all the elements that have order d mod p )

If b has order d mod p,
by the defn of order b^d -1≡0 mod p
and by the previous step (powers of a give d sols and lagrange says at most d sols mod p so i get all sols in this way) ,
b ≡ aᵏ for some k.
if c=gcd(b,d)
Moreover, we must have
gcd(k, d) = 1:
if c is a common divisor,
bᵈ/ᶜ
≡ (aᵏ)ᵈ/ᶜ= (aᵈ)ᵏ/ᶜ ≡ 1, mod p
thus c = 1
because b has order d.
(c is a common divisor of k and b )

(showing every power of a has order d)
Conversely, take k s.t gcd(k, d) = 1, then aᵏ has order d. Indeed, by Proposition 4.1.4
(aᵏ)ᵉ≡ 1 implies that d | ke, thus d | e, so the order of aᵏ is at least d, and so it is exactly d by the previous point.

explaining((aᵏ)ᵉ≡ a^0 mod p IFF exponents are also ke≡ 0 mod p); k and d are coprime so d|e so order is a multiple of d)

Question 33

prev thm corollary

Answer 33

doesnt tell us how to find primitive roots just says lots of them

Question 34

Corollary 4.3.2.

if we have primitive roots then we can find…

Answer 34

If p is prime, (and there is a primitive root)
then there are
ϕ(p − 1) primitive roots modulo p.
In particular, p has a primitive root.

• comes from all powers of this primitive root with exponents coprime to p-1 also being primitive roots,
  once you have a primitive root of something has order p-1 mod p,
  *p prime means p actually has exactly this many

Question 35

PROOF OF
If p is prime, then there are ϕ(p − 1) primitive roots modulo p.
In particular, p has a primitive root.

Answer 35

(we actually use this proof..)
(if you take a number mod p then a^p -1≡ 1 its order will be a divisor of p-1 )

Let ψ(d) be the number of integers among
1, 2, . . . , p − 1 that have order d modulo p.
consider
First Σ_{d|(p-1} ψ(d)
Every element in {1,..p-1} has order that divides p-1 mod p by Flittlethm, so every has order d.
p − 1 =Σ_{d} ψ(d).
(We could have used By Corollary 4.2.3,)

(If we have one element of order d we will have ϕ(d) of them as we can take all the powers, d distinct elements and ϕ(d are primitive roots )

Moreover, ψ(d) ̸= 0 implies that ψ(d) = ϕ(d) by Lemma 4.3.1,
and also that d | ϕ(p) =(p − 1) (by Proposition 4.1.4 or directly from Lagrange’s theorem on finite groups).

It follows that
p − 1 = Σ_{d|(p−1)} ψ(d)
≤ Σ_{d|(p−1)} ϕ(d) (because is either 0 or ϕ(d) )
= p − 1

where the last equality comes from Theorem 3.3.1. It follows that ψ(d) = ϕ(d) for all
d | (p − 1).

((ψ(d)) non zero for all d dividing m,
In particular, there are ψ(p − 1) = ϕ(p − 1) elements of order p − 1, thus ϕ(p − 1)
primitive roots modulo p.

(as ψ(p − 1) counts how many elements have order p-1, those are primitive roots mod p, and those are exactly ϕ(p − 1) many, always positive non zero

Question 36

Example 4.3.3. If p = 11, then 2 is a primitive root.
(ensure you see this)

Answer 36

Indeed,
2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 ≡ 5, 2^5 ≡ 10, 2^6 ≡ 9, 2^7 ≡ 7, 2^8 ≡ 5^2 ≡ 3, 2^9 ≡ (−3)^3 ≡ 6, 2^10 ≡ 100 ≡ 1.

The primitive roots are the powers of 2 with exponent coprime to ϕ(11) = 10, thus
2^1, 2^3, 2^7, 2^9, which are indeed ϕ(10) = 4 many primitive roots as expected.

Question 37

Thus we have primitive roots modulo p for every prime p.

For which other n’s do we have primitive roots? Not very many, as it turns out.

Answer 37

for not prime: I want to know for numbers coprime to n is there a single element s.t its powers generates all of the elements

Because of the lemma, if a is order d then all the powers of a are distinct solutions of a^d-1≡0 mod p.
But if the order is exactly p-1: we have a primitive root mod p, it has order p-1
how many coprime to p? p-1.
If we have one primitive root all the powers generate everything.

e.g. primitive root mod 5 is 2 I can take the powers of 2 and I get 1,2,3,4 generating them

e.g. generating powers of 2 mod 11 gives me all those not congruent to 0 mod 11. 1,2,3,4,5,6,7,8,9,10

Will taking powers of a give me everything?

Question 38

What about n mod n with n not prime?

primitive roots?

Answer 38

Answer:

Question 39

missed prop 4.3.4?

Question 40

Theorem 4.3.5 (Gauss, 1801)
primitive roots

Answer 40

Let n > 1 be an integer. Then n has a primitive root
IFF
n is 2, 4, pᵏ or 2pᵏ, where k ≥ 1 and p is an odd prime.

(mentioned by prev lecturer)

if n is a product of two numbers that are coprime and both greater than 2 then no primitive roots: e.g. I cant have 4 pᵏ , products of 2 odd primes with primitive roots

Question 41

PROOF

thm Gauss
Let n > 1 be an integer. Then n has a primitive root
IFF
n is 2, 4, pᵏ or 2pᵏ, where k ≥ 1 and p is an odd prime.

Answer 41

thm says if we fix an n we can find primitive roots exactly when n is one of the following 2,4 or power of an odd prime

links to chinese remainder thm:
2) p^2 and p^k have primitive roots when p is prime
3)if p^k is a primitive root then 2p^k has primitive root of 1?
(odd prime powers from 2), twice prime powers come from this, powers of 2 checked explicityly etc..
(see notes and compare as left as exercise)
STEPS
1) There are prim roots for n x p prime (prev lec)
2) if there are prim roots dor n=p^k, p odd and also n x 2p^k
3) There are px’s for p^2, p^k k<=3
4)No prim roots for ____ gcd(a,b)=1 a,b >=2
5)primitive roots for n=2,4 no primitive roots for 8,16,… 2^k for k>=3

23rd feb lect continue 20 mins

Question 42

PROOF

thm Gauss
Let n > 1 be an integer. Then n has a primitive root
IFF
n is 2, 4, pᵏ or 2pᵏ, where k ≥ 1 and p is an odd prime.

part 5
5)primitive roots for n=2,4 no primitive roots for 8,16,… 2^k for k>=3

Answer 42

For n=2 Φ(2)=1 a=1 has order 1 mod 2 so is a primitive root
n=4 Φ(4)= 4(1-0.5)=2
a=1 doesnt work
a=3 3^1 not congruent to 1 mod 4, 3^2=9≡1 mod 4
so 3 is a primitive root mod 4

n=8 Φ(8)= 8(1-0.5)=4
so we are looking for a number of order 4 mod 8
coprime to 8: checking from 1,3,5,7
1 never works, has order 1
3^1≠ 1 mod 8 3^2=9≡1 mod 8
so the order is 2, 3 is no good
5^1 doesnt work, 5^2=25≡1 mod 8 so 5 no good
7^1 trivial 7^2≡1 mod 8
so no primitive root mod 8

Left as an exercise: (tricky) (⋆). Let p be any prime. Show that if a is a primitive root of pᵏ⁺¹, then it is a primitive root of pᵏ

this is applied for example as
3 is a primitive root mod 4 (p=2, k=1)
now we apply to set n=2
3 becomes 1 in mod 2 and 1 is a primitive root mod 2
for e.g primitive root in mod 16 is also a primitive root in 8

Question 43

PROOF

thm Gauss
Let n > 1 be an integer. Then n has a primitive root
IFF
n is 2, 4, pᵏ or 2pᵏ, where k ≥ 1 and p is an odd prime.

part 2

2) if there are prim roots dor n=p^k, p odd and also n x 2p^k

Answer 43

Not about finding a primitive root itself but using one to find another

suppose a is a primitive root of p^k (where p is an odd prime k>=1)

I claim that one of a , a+p^k is a primitive root of 2p^{k}
proof of the claim:
based on chinese remainder thm
(typo in ch 4)
Let integer d>1 . Supposed that a^d=1 (mod 2p^k)
i want that ϕ(2p^k) | d
ϕ(2)ϕ(p^k)=ϕ(2p^k) as p is odd

by chinese remainder thm:
a^d=1 (mod 2p^k) IFF
a^d≡1 mod 2 and a^d ≡ mod p^k
by assumption a is a primitive root of p^k
so
IFF
a≡1 mod 2 and ϕ(p^k) |d
IFF
a is odd

if a is odd im done and a is a primitive root of p^k
If not replace a with a +p^k: if a is even + p^k which is odd, is odd. thus its a primitive root of 2p^k (still a primitive root, didnt change the congruence class p^k )

Question 44

example
gauss

Let n > 1 be an integer. Then n has a primitive root
IFF
n is 2, 4, pᵏ or 2pᵏ, where k ≥ 1 and p is an odd prime.

part 2

2) if there are prim roots dor n=p^k, p odd and also n x 2p^k

Answer 44

2 is a primitive root of 11
thus
(As 2 is even, 2+11=13
13 is a primitive root of 22)

(compute powers of 13 mod 22 to see this)
phi(22)=10 means order 10

Question 45

Exercise 4.3.10 (⋆). Let p be any prime. Show that if a is a primitive root of pᵏ⁺¹, then it is a primitive root of pᵏ. In particular, there are no primitive roots of 2ᵏ for k ≥ 3.

not shown, other things not as useful

Answer 45

first part of lemma 4.3.1 for a mod pᵏ⁺¹
Suppose that a is a primitive root of pᵏ⁺¹, and let
d = ϕ(pᵏ⁺¹) = pᵏ(p −1). By Proposition 4.1.4, the powers a, a², . . . , aᵈare pairwise incongruent modulo
pᵏ, and since there are d = ϕ(pᵏ⁺¹) of them, they represent all numbers coprime to pᵏ⁺¹ modulo pᵏ⁺¹.

Now let e be the order of a modulo pᵏ; recall that e ≤ ϕ(pᵏ) < d. By construction, a, a², . . . , aᵈ represent at most e pairwise incongruent classes modulo pᵏ. On the other hand, by the previous observation, they must also represent all numbers coprime to pᵏ. This implies that e ≥ ϕ(pᵏ), hence e = ϕ(pᵏ), thus a is a primitive
root of pᵏ.

Since there are no primitive roots of 8 = 23 (Example 4.1.7), by induction, there are no primitive roots of 2ᵏ for all k ≥ 3.

Question 46

Proposition 4.3.9.

Answer 46

Let p > 2 be an odd prime. Then pk has primitive roots for all k ≥ 1.

Extra. The proof is a bit long and does not shed any more light, so we skip it from the lectures,
but leave it here for completeness.

Question 47

Example 4.3.7. We can verify by hand that:

primtive roots

Answer 47

2 and 4 have primitive roots (respectively 1 and 3);
* 9 has a primitive root: we look for an element of order ϕ(9) = 6 among
1, 2, 4, 5, 7, 8, and we can see quickly that 2 and 5 have order 6, while all other
elements have lower order (as we expect, since ϕ(6) = 2);
* 12 has no primitive root: we look for an element of order ϕ(12) = 4 among
1, 5, 7, 11, but they all have order 2.

Question 48

Proposition 4.3.8. Let p > 2 be an odd prime. then …primitive roots.

Answer 48

Proposition 4.3.8. Let p > 2 be an odd prime. Then p^2 has primitive roots.

Question 49

Proposition 4.3.8. Let p > 2 be an odd prime. Then p^2 has primitive roots.

PROOF

Answer 49

Proof. Let a be a primitive root of p. We claim that one of a, a + p is a primitive root
of p2. Indeed, suppose that a is not a primitive root, hence that a^d ≡ 1 (mod p^2) for
some 1 < d < ϕ(p2) = p(p − 1). We have in particular ad ≡ 1 (mod p), so (p − 1) | d
because a is a primitive root of p. Since d | p(p − 1), we get d = p − 1, that is
ap−1 ≡ 1 (mod p2)…….