NUMBER THEORY Primitive roots 24 ONLY the first in Jor each

the first in Jor each given number n tell how many primitive are a reduced residue system modulo n. 2. 19 3. 4. 14 6. 103 5. 101 7. 105 8. 107 9. which of the numbers 50, 51 59 have primitive roots? 10. Which of the numbers 80, 81 89 have primitive roots? In the nert four problems, use the tables for n 13 at the end of this section to find the least residue modulo 13 for the given number. 12. 11.7 13. 6. 7.8 15. Make a table like the last one in this section for the modulus prim- itive 3. 7 and root 16. Make a table like the last one in this section for the m 11 and primitive 6 True-False. In the nert nine problems, tell which statements are true, and give countereramples for those that are false. Assume that a and b are primitive roots modulo m. 17. The integer ab is a primitive root (mod m). The integer a is a primitive root (mod m) 9. The integer a b is a primitive root (mod m) The integer a b is not a primitive root (mod m). 21. The integer a2 is not a primitive root (mod m). 22. If b a ak (mod m), then (m, k) 1. 23. If m 2, then a (m)/2 s 1 (mod m) (mod m) 24 If c is solution to 1 (mod m), then c is a primitive root a ac 25. If c (m)/2 -1 (mod m), then c is a primitive root (mod 20. Let p be an odd prime and g a primitive root (mod p). Prove g is not a quadratic residue (mod p), p prime, and (a, p) 1, then 27. that if g is a primitive root (mod 1, such that g a (mod p) there exists a unique integer t, 0 st p quadratic 28. Let g, a, p, and t be as in the previous problem. Show that a is a 29. residue (mod p) if and only if t is even. hold if the modulus is not re- Show that Lagrange\'s theorem does not stricted to be a prime

Solution

24.

False

Counterexample

Let, m=5

a=c=4

ac=16=1 mod 5

But, c^2=16=1 mod 5

c^3=64=4 mod 5

c^4=1 mod 5

So, c is not a primitive root because for c to be a primitive root there must be some m,n so that

c^m=2 mod 5, c^n=3 mod 5