Odd Primes and Primitive RootsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/