
Number theory
Posted:
Jun 18, 1996 2:41 AM


In my desperate attempts to understand a little bit more of prime numbers I ran into the following assertion that I found in an old math text book:
LET P BE PRIME, AND G = (N mod P, . ) BE THE GROUP OF NATURAL NUMBERS WITH MULTIPLICATION MODULO P. THEN G IS CYCLIC.
The statement was left unproven, however, and a reference was given to old to find in a library today.
My questions are: 1. Can someone provide me with a proof of this statement? 2. Is it possible to point out genericly (as a function of P) which of the elements in N mod P are generators in the group?
FOR EXAMPLE: Let P=7 then 3 and 5 are generators of the whole set {1,2,3,4,5,6}, that is: every number in N mod 7 is a power of three and of five. If we write ~ for the power sign (3~2 is the square of 3) then: 3~1 = 3 (mod 7) 3~2 = 2 (mod 7) 3~3 = 6 (mod 7) 3~4 = 4 (mod 7) 3~5 = 5 (mod 7) 3~6 = 1 (mod 7) 3~7 = 3 (mod 7) Similarly: 2,6,7, 8 are the generators of (N mod 11, . ); 2,6,7,11 are the generators of (N mod 13, . ); 3,5,6,7,10,11,12,14 are the generators of (N mod 17, . ); 2,3,10,13,14,15 are the generators of (N mod 19, . );
It is not so difficult to see that G is a group. Note that G has p1 elements. Clearly, N mod p is closed with respect to multiplication modulo p, and multiplication is associative. G has 1 as the unit element. Finally, if we write ~ for the power sign (so a~2 is the square of a) then according to Fermat's little theorem a~(p1) = 1 (mod p), as p is prime, and thus a~(p2) is the inverse of a.
Note that G is the multiplicative group of the field F = (Z mod p, + , . ) with p elements and addition and multiplication modulo p.

