Math 453 Definitions and Theorems 5 3 30 2011 A J Hildebrand Primitive roots 5 1 The order of an integer Definition 5 1 Order of an integer Let m N and a Z be such that a m 1 The order of a modulo m denoted by ordm a is the least positive integer k such that ak 1 mod m 5 1 In order for this definition to make sense there has to be at least one positive integer k for which 5 1 holds The existence of such a k is guaranteed by Euler s Theorem Theorem 2 21 which states that under the same assumptions on m and a as in the definition 5 1 holds for k m Thus the order ordm a is well defined and it is at most equal to m Proposition 5 2 Properties of an order Let m N and a Z be such that a m 1 and let ordm a be the order of a modulo m Then i Periodicity If b a mod m then ordm b ordm a ii Relation to Euler phi ordm a is a divisor of m iii Characterization of good exponents The set of positive integers k for which the congruence 5 1 holds consists exactly of the positive integer multiples of ordm a iv Order of powers of a For any positive integer i ordm ai ordm a ordm a i In particular ordm ai ordm a if and only if ordm a i 1 Proposition 5 3 Number of elements of given order Let p be an odd prime Then the possible orders of integers modulo p are exactly the positive divisors of p 1 p Moreover given any positive divisor d p 1 there exist exactly d incongruent integers a with ordp a d 5 2 Primitive roots The question when the order of an integer a modulo m is equal to its maximal possible value the Euler order m motivates the following definition Definition 5 4 Primitive root Let m N and a Z be such that a m 1 Then a is called a primitive root modulo m if ordm a m i e if the order of a is equal to the maximal possible value Proposition 5 5 Primitive roots and reduced systems of residues Let m N and suppose r is a primitive root modulo m Then the set r r2 r m is a system of reduced residues modulo m That is the elements in this set are pairwise incongruent modulo m and every integer a with a m 1 is congruent modulo m to an element in the above set 19 Math 453 Definitions and Theorems 5 3 3 30 2011 A J Hildebrand The Primitive Root Theorem Theorem 5 6 Existence of Primitive Roots Let m be a positive integer Then there exists a primitive root modulo m if and only if m has one of the following forms i m p where p is an odd prime and N ii m 2p where p is an odd prime and N iii m 1 2 4 Theorem 5 7 Number of primitive roots Let m be of one of the forms in the Primitive Root Theorem so that there exists at least one primitive root modulo m Then there exist exactly m incongruent primitive roots modulo m 20