Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Number theory
Replies: 0

 weijland@pi.net Posts: 4 Registered: 12/12/04
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 p-1
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~(p-1) = 1 (mod p), as p is prime, and thus
a~(p-2) 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.