CH4 Primitive roots Flashcards

1
Q

EULERS THM recall

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

ϕ(n) can be the maximal power when n

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Definition 4.1.1
(Order)

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

lagranges thm and order of an element

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

a=7 n =52

The order of 7 modulo 52?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

E.g ϕ(12)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are Euler’s totient properties?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

order d what can it be?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Proposition 4.1.4.

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

then orders

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

extra

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Definition 4.1.6 (Primitive root)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Example 4.1.7. There are no primitive roots modulo 8.

dont always exist

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

primitive roots for n=2

A

one element coprime 1

phi(n)=1 trivial

1 prmitive root mod 2

21
Q

primitive roots for n=3

A

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

22
Q

primitive roots for n=4

A

coprime 1,3

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

so 3 is a primitive root

23
Q

n=5 a =2

A

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

24
Q

what values of n give primitive roots

Find for which n there are primitive roots
(twice)

A

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

25
Q

Theorem 4.2.1 (Lagrange)

A

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

26
Q

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

A

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.

27
Q

Example 4.2.2. This fails miserably for non-primes:

A

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.

28
Q

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

A

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)

29
Q

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

A

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

30
Q

recall formula

A

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

31
Q

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

(and a coprime to p)

A

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?

32
Q

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.

A

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

33
Q

prev thm corollary

A

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

34
Q

Corollary 4.3.2.

if we have primitive roots then we can find…

A

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
35
Q

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

A

(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

36
Q

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

A

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.

37
Q

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.

A

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?

38
Q

What about n mod n with n not prime?

primitive roots?

A

Answer:

39
Q

missed prop 4.3.4?

A
40
Q

Theorem 4.3.5 (Gauss, 1801)
primitive roots

A

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

41
Q

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.

A

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

42
Q

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

A

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

43
Q

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

A

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 )

44
Q

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

A

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

45
Q

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

A

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.

46
Q

Proposition 4.3.9.
When does p^k have primitive roots

A

Let p > 2 be an odd prime. Then p^k 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.

47
Q

Example 4.3.7. We can verify by hand that:

primtive roots

A

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.

48
Q

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

A

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

49
Q

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

PROOF

A

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