proof about modulii permitting primitive roots

[wildrabbitt]

Hi,

I'd like to see a proof of the fact that only modulii of the form

\( 2, 4, p^k, 2p^k \) have primitive roots. Can someone point me to one?

[LaurV]

You could at least google it... You need to follow 3 links deep from here:

https://en.wikipedia.org/wiki/Primit...o_n#Definition

[Nick]

Originally Posted by wildrabbitt

Hi,

I'd like to see a proof of the fact that only modulii of the form

\( 2, 4, p^k, 2p^k \) have primitive roots. Can someone point me to one?

You can also find what you need right here on the forum!
Basic Number Theory 16: unit group structure in modular arithmetic

[Dr Sardonicus]

Originally Posted by wildrabbitt

Hi,

I'd like to see a proof of the fact that only modulii of the form

\( 2, 4, p^k, 2p^k \) have primitive roots. Can someone point me to one?

The remaining numbers are of three types:

(1) Powers of 2, 2^k, for k > 2,

(2) Numbers divisible by 4, and by at least one odd prime p, and

(3) Numbers with at least two odd prime factors p1 and p2.

These cases can be treated separately. The first case can be dealt with by showing that 8 does not have a primitive root.

In the other two cases, you can show that the order of any invertible element (Mod 4*p) or (Mod p1*p2) divides the least common multiple of its orders (Mod 4) and (Mod p) or (Mod p1) and (Mod p2). All you need is a common divisor greater than 1 for the orders of primitive roots (Mod 4) and (Mod p), or (Mod p1) and (Mod p2).

[wildrabbitt]

Right. I have tried to understand your explanation Dr S.

It's plain to me that with the additional condition that the p I mentioned be an odd prime in the modulii \(p^k \) and \( 2p^k \) the
remaining numbers are those of the form you mentioned.

I was thereafter looking at a particular case of the second form of number
(a multiple of 4 and at least one odd prime p) to see if I could glean the general rule.

I took \( p = 3 \).
Then I found an invertible element, namely 5 (as \(5*5 \equiv 1 ( \text{mod 12} )\) ).

Since you invited me to prove the statement

\(\text{the order of any invertible element (mod 4p) divides the least common multiple of it's orders (mod 4) and (mod p)}\)

I looked to see what the order of 5 is mod 4 and mod 3.

I found them to be 1 and 2 respectively.

I could see that \( 2 | lcm(1, 2) = 2 \).

Although I yet tried really hard to prove the general case, I'm most intrigued as it how your second sentence related to what I've done :

Your second sentence :

All you need is a common divisor greater than 1 for the orders of primitive roots (Mod 4) and (Mod p)

2 questions that stand out in my mind are.
A common divisor of which two numbers?
The orders of which integers?

Answers to these two questions might help me understand how it is that no primtives exist for these numbers.

Please help.

[wildrabbitt]

From the lack of response I guess I'm either being very stupid or my post was just plain unintelligable.

I didn't mean to be rude. I did read some of Nicks basic number theory no 16 thread. I thought that thread was very good except I didn't know what the little lines above the numbers meant. I'm used to thinking of them as specifying conjugates.

I wanted to try to see if I could get to understand the proof from Dr.Sardonicus' post so by responding only acknowledging what Dr.Sardonicus said didn't mean I hadn't used Nick's and Lauv's suggestion

I've currently decided that I need to look at my OU course materials again.

[science_man_88]

Originally Posted by wildrabbitt

I did read some of Nicks basic number theory no 16 thread. I thought that thread was very good except I didn't know what the little lines above the numbers meant. I'm used to thinking of them as specifying conjugates.

from:
https://en.m.wikipedia.org/wiki/Modu...cative_inverse

Using the notation of \({\displaystyle {\overline {w}}}\) to indicate the congruence class containing w

[wildrabbitt]

Thanks science_man .

[Nick]

Let's take your example of the integers modulo 12.
We can write 12 as 4x3 where gcd(4,3)=1 so, by the Chinese Remainder Theorem,
integers modulo 12 behave exactly like ordered pairs of integers where we take the
first coordinate modulo 4 and the second coordinate modulo 3:

0  (mod 12) corresponds with (0,0) (mod 4, mod 3)
1  (mod 12) corresponds with (1,1) (mod 4, mod 3)
2  (mod 12) corresponds with (2,2) (mod 4, mod 3)
3  (mod 12) corresponds with (3,0) (mod 4, mod 3)
4  (mod 12) corresponds with (0,1) (mod 4, mod 3)
5  (mod 12) corresponds with (1,2) (mod 4, mod 3)
6  (mod 12) corresponds with (2,0) (mod 4, mod 3)
7  (mod 12) corresponds with (3,1) (mod 4, mod 3)
8  (mod 12) corresponds with (0,2) (mod 4, mod 3)
9  (mod 12) corresponds with (1,0) (mod 4, mod 3)
10 (mod 12) corresponds with (2,1) (mod 4, mod 3)
11 (mod 12) corresponds with (3,2) (mod 4, mod 3)

Which are the units, i.e. invertible elements?
In the integers modulo 12, the units are the integers n with gcd(n,12)=1,
so they are 1,5,7 and 11 (mod 12).
There are 4 of them so ϕ(12)=4 where ϕ is Euler's totient function.
Similarly, in the integers modulo 4 the units are 1 and 3 (mod 4), with ϕ(4)=2
and, in the integers modulo 3 the units are 1 and 2 (mod 3) with ϕ(3)=2.
Notice in the above table that the units modulo 12 correspond with the pairs of units
modulo 4 and modulo 3.
Take a pair such as (1,2) (mod 4, mod 3), which corresponds with 5 (mod 12).
The order of 5 (mod 12) is the lcm of the order of 1 (mod 4) and the order of 2 (mod 3),
which is lcm(1,2)=2.
So taking powers of 5 (mod 12) will only give us 2 of the 4 units, and therefore 5 is not a primitive root (mod 12).
In this example, that happens with all the units.
The order of the first coordinate (mod 4) is always a factor of ϕ(4)=2,
the order of the second coordinate (mod 3) is always a factor of ϕ(3)=2,
so their lcm can never be ϕ(12)=4.