Associated Topics || Dr. Math Home || Search Dr. Math

### Odd Primes and Primitive Roots

```
Date: 11/14/2001 at 06:44:51
From: Alison Cox
Subject: Odd primes and primitive roots

For a question as part of an assignment on number theory, I have
verified directly that 24 and 28 do not have primitive roots.

I am having problems solving the second part of this question:

Give a proof that N = PQ, with P and Q distinct odd primes, has no
primitive roots.

Thank you.
```

```
Date: 11/14/2001 at 12:26:21
From: Doctor Rob
Subject: Re: Odd primes and primitive roots

Thanks for writing to Ask Dr. Math, Alison.

Let X be any integer relatively prime to N = P*Q.  By Fermat's
Little Theorem (applied first with prime P, then with prime Q),

X^(P-1) = 1 (mod P),            X^(Q-1) = 1 (mod Q)
D = ord_P(X) <= P - 1,          E = ord_Q(X) <= Q - 1,
X^D = 1 (mod P),                X^E = 1 (mod Q),
(X^D)^E = 1^E = 1 (mod P),      (X^E)^D = 1^D = 1 (mod Q),
X^(D*E) = 1 (mod P),            X^(D*E) = 1 (mod Q),
X^(D*E) = 1 (mod P*Q),

by the Chinese Remainder Theorem.  This implies that

ord_N(X) <= D*E,
<= (P-1)*(Q-1),
= P*Q - P - Q + 1,
< P*Q - 1,        (because P + Q > 2)
= N - 1.

Thus X does not have order N - 1 modulo N, so is not a primitive
root.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 11/04/2002 at 09:23:08
From: Claudio Buffara
Subject: Odd Primes and Primitive Roots

Hi,

I think I have found an easy way to do this.

First of all, Phi(PQ) = (P-1)(Q-1). So, any primitive root mod PQ
must have order (P-1)(Q-1).

Let N be any integer such that (N,PQ) = 1. If I can manage to show
that there is a positive integer d < (P-1)(Q-1) such that N^d = 1
(mod PQ) then the problem is solved.

Since P and Q are odd, (P-1)/2 and (Q-1)/2 are positive integers.

Let d = (P-1)(Q-1)/2  -  a positive integer also.

By Fermat's Little Theorem, N^(P-1) = 1 (mod P) and N^(Q-1) = 1
(mod Q).

Therefore, since P-1 | d and Q-1 | d, we have N^d = 1 (mod P) and
N^d = 1 (mod Q).

Since (P,Q)=1 those two congruences imply that: N^d = 1 (mod PQ).

In other words, the order of N (mod PQ) is <= d <' Phi(PQ) ==> N is
not a primitive root mod PQ ==> there are no primitive roots mod PQ.

The same method can be used to prove the following generalizations:

1. If M is a positive integer divisible by at least two distinct odd
primes, then there are no primitive roots mod M.

In this case, M = P^a * Q^b * K, where P and Q are distinct odd
primes, and a, b and K are positive integers with (K,PQ) = 1.

Phi(M) = Phi(P^a) * Phi(Q^b) * Phi(K)

P is odd  ==> Phi(P^a) = P^(a-1) * (P-1) is even  ==>  Phi(P^a)/2 is
a positive integer. In an analogous way, so is Phi(Q^b)/2  ==>

==>  d = Phi(M)/2 is a positive integer such that d < Phi(M) and:
Phi(P^a) | d  ,  Phi(Q^b) | d   and   Phi(K) | d    (%%%)

Let N be a primitive root mod M.

Then, (N,M) = 1  ==>  (N,P^a) = (N,Q^b) = (N,K) = 1.

By Euler's theorem and (%%%) above we have:
N^Phi(P^a) = 1 (mod P^a)  ==>  N^d = 1 (mod P^a)
N^Phi(Q^b) = 1 (mod Q^b)  ==>  N^d = 1 (mod Q^b)
N^Phi(K) = 1 (mod K)    ==>  N^d = 1 (mod K)

Therefore, since the three moduli are pairwise coprime, we conclude
that  N^d = 1 (mod M)  ==>  N is not a primitive root mod M  ==>
Contradiction  ==>  There are no primitive roots mod M.

-------------------------------------------------------------

2. If M is a positive multiple of 4 other than 4 itself, then there
are no primitive roots mod M (if M = 4, then 3 is a primitive root)

In this case, M = 2^(a+1) * K, where a is a positive integer and K is
an odd integer greater than 1.

Phi(M) = 2^a * Phi(K)

Phi(K) is even (this is easily seen by examining the expression of Phi
(K) in terms of the prime factors of K - at least one factor of the
form (P-1) appears where P is an odd prime dividing K) ==> Phi(K)/2
is integer

a >= 1  ==>  2^a is even  ==>  2^a/2 = 2^(a-1) is integer

Therefore, d = Phi(M)/2 is an integer such that d < Phi(M) and:
Phi(K) | d   and   2^a | d    (***)

Let N be a primitive root mod M.

Then (N,M) = 1  ==>  (N,2^a) = (N,K) = 1

By Euler's theorem and (***) above we have:
N^Phi(K) = 1 (mod K)        ==>  N^d = 1 (mod K)
N^(2^a) = 1 (mod 2^(a+1))  ==>  N^d = 1 (mod 2^(a+1))

Therefore, since the two moduli are coprime, we conclude that N^d = 1
(mod M)  ==>  N is not a primitive root mod M  ==>
Contradiction  ==>  There are no primitive roots mod M.

Best regards,
Claudio Buffara.
```

```
Date: 11/05/2002 at 13:16:17
From: Doctor Schwa
Subject: Re: Odd Primes and Primitive Roots

This is a nice alternate solution!  Very nice stuff, thanks!

It all comes down to phi(odd) being even.

- Doctor Schwa, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search