Multiplicative Groups of Order (p-1)

Date: 05/12/2000 at 09:47:12
From: Jeff Olbrys
Subject: Multiplicative groups of order (p-1), p = prime

I have seen several passing references that multiplicative groups of 
order (prime-1) are cyclic, but can't find a proof.

Euler's generalization of Fermat's theorem gives us

      a^(p-1) = 1 (mod p)

but (p-1) is not necessarily minimal.

In Z mod 7, 3 and 5 are the generators of the multiplicative group. In 
Z mod 11, the generators are 2, 6, 7 and 8. I don't see a pattern here 
to suggest an approach.

Date: 05/12/2000 at 15:07:39
From: Doctor Schwa
Subject: Re: Multiplicative groups of order (p-1), p = prime

Finding the generators is difficult, but proving that it's cyclic is 
not so hard. There's a nice theorem which says: in the integers mod m 
there will be exactly phi(d) elements of order d, for each d that 
divides phi(m).

If you need some help on how to prove this, please write back.

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/   

Date: 11/30/2000 at 08:39:45
From: Jeffrey Olbrys
Subject: Re: Multiplicative groups of order (p-1), p = prime

Dr. Schwa,

Thanks for your earlier help. After reading your reply, I went back to 
my Number Theory book (we used Stark's) and filled in the details.

I now need a topic for a little research paper. I was wondering about 
the question of finding those generators - the theorem proves 
existence, and provides not a clue about how to actually find one. 
(For small p, brute force calculation will work, but I'd hate to have 
to do that for large p.) Do you think this is an interesting question? 
Can it lead me to about 10 pages worth of "meaty" math?

Thanks in advance for your consideration.

Jeff Olbrys

Date: 11/30/2000 at 15:14:57
From: Doctor Schwa
Subject: Re: Multiplicative groups of order (p-1), p = prime

Jeff,

I'm glad my small hint was enough. Sounds like it took some research 
on your own. Well done.

I think there's a LOT more than 10 pages of meaty math in actually 
finding the generators (mod p). In fact, I worked on this problem for 
quite a while when I took number theory. The answer wasn't in my text, 
and I'm sure I generated FAR more than 10 pages in trying to figure it 
out (unsuccessfully, I might add).

Once you have one generator, of course, the powers of it give you all 
the rest. (That is, the generator raised to powers that are relatively 
prime to p-1.)

On the Web, I found some Mathematica code that determines the 
generator:

   Help With PrimitiveRoot - MathGroup archive
   http://hilbert.math.hr/arhive/mathgroup/1998/10/0135.html   

but unfortunately I'm not fluent enough in Mathematica to figure out 
what algorithm they're using. There's something recursive going on, to 
find the generator for the group of units mod p^k in terms of the one 
mod p, but I can't quite understand exactly what's going on when it 
gets down to that base case.

I'll do a little more research and see if I can get you pointed in the 
right direction.

Anyway, the problem of finding a generator for the cyclic group of 
multiplication mod p is certainly hard enough; I wonder if it might be 
too hard. I'd prefer to find a generator for the additive group ;-).

I found some interesting problems on the net here and there, including 
these from a course on group theory:

  Math 302: Group Theory
  Dr. Ken Pledger, School of Mathematical and Computing Sciences,
  Victoria University of Wellington, New Zealand

  http://www.mcs.vuw.ac.nz/courses/MATH302/assignments/ass_4/ass_4.html   

  Assignment 4 Solutions:
  http://www.mcs.vuw.ac.nz/courses/MATH302/assignments/sol_4/sol_4.html   

which might well give you other ideas for a project.

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/   

Date: 12/01/2000 at 10:19:25
From: Doctor Rob
Subject: Re: Multiplicative groups of order (p-1), p = prime

Thanks for writing to Ask Dr. Math, Jeff.

The matter of finding a primitive root modulo n is of some interest. 
Yes, it could lead to 10 pages of meaty math.

The proof that primitive roots exist modulo p goes as follows. Let 
(a,p) = 1, and let h be the least exponent such that a^h = 1 (mod p). 
Then h is called the order of a modulo p. By Lagrange's theorem on the 
order of elements and the order of a group, h | p-1. Now a^i for 
i = 1, ..., h are all distinct, by the definition of h. a^i has order 
modulo p exactly h/(i,h). That means that the ones with order h modulo 
p have (i,h) = 1. By the definition of the Euler phi function, there 
are exactly phi(h) of these with order h modulo p. Thus for each h 
dividing p-1 there are either phi(h) or 0 elements of order h modulo 
p. Let n(h) be that number. Then, since every nonzero element modulo p 
has some order dividing p-1,

     p - 1 =  SUM  n(h) <=  SUM  phi(h) = p - 1
             h|p-1         h|p-1

with equality if and only if n(h) = phi(h) for all h | p-1. Since 
equality is evident, we have that for all h | p-1, there are exactly 
phi(h) elements of order h modulo p. In particular, there are exactly 
phi(p-1) elements of order p-1 modulo p, that is, phi(p-1) primitive 
roots modulo p. phi(n) is always positive, so primitive roots always 
exist.

The finding of a primitive root modulo p depends on knowing the 
complete prime-power factorization of p-1. If this is not known, then 
you cannot prove that any particular number is a primitive root. That 
means that for most very large values of p, we cannot solve the 
problem. We assume below that the prime factorization of p-1 is known:

                r
     p - 1 = PRODUCT q(i)^e(i)
               i=1

Any particular integer x with 1 <= x <= p-1 is a primitive root if and 
only if for every i with 1 <= i <= r,

     x^[(p-1)/q(i)] =/= 1 (mod p)

Proof of this one way is easy: if the ith of these powers were 
congruent to 1 modulo p, then the order of x would be at most 
(p-1)/q(i) < p - 1, so x would not be primitive. Proof the other way 
is also easy. If the order of x were h < p - 1, then pick an i such 
that q(i) | (p-1)/h. Then

     x^[(p-1)/q(i)] = (x^h)^([p-1]/[q(i)*h]) (mod p)
                    = 1^([p-1]/[q(i)*h]) (mod p)
                    = 1 (mod p)

This fact is how you test a number for being a primitive root.

The obvious, brute-force approach to finding a primitive root is to 
try x = 2, 3, 4, 5, ... in order to see if any of them is a primitive 
root. Actually, this is quite a good method, because there are so many 
primitive roots that you are likely to find one quickly. Furthermore, 
you can speed this up a little by skipping x's which are perfect 
powers, like 4, 8, 9, 16, 25, 27, 32, 36, etc. You can do this because 
if x = y^k for some k, then the order of x is a divisor of the order 
of y, which is < p-1 (or you would have stopped on finding y < x).

Another systematic way is as follows. Set z = p-1. Pick a random x, 
1 < x < p. Determine for which i values you have q(i) | z and

     x^[(p-1)/q(i)] =/= 1 (mod p)

Then for each such i, divide z by q(i)^e(i), and compute

     s(i) = x^[(p-1)/q(i)^e(i)] (mod p)

Each s(i) is picked so that its order is exactly q(i)^e(i). If z > 1, 
pick another random x, and repeat the above. When z = 1, compute

            r
     a = PRODUCT s(i) (mod p)
           i=1

and that will be your primitive root (because its order will be the 
product of the powers q(i)^e(i), which is p-1).

Example: Find a primitive root modulo 109. The prime factorization of 
108 is 2^2 * 3^3. Thus q(1) = 2, q(2) = 3, e(1) = 2, e(2) = 3, and 
r = 2. Set z = 108. Start with x = 23. It turns out that

     23^(108/2) = 23^54 = 108 (mod 109)
     23^(108/3) = 23^36 = 1 (mod 109)

Thus we divide z by 2^2, so z = 27. We also compute

     s(1) = 2^27 = 33 (mod 109).

(Observe that the order of 33 is 4 modulo 109.) Since z = 4 < 108, we 
continue with x = 83. It turns out that

     83^(108/3) = 83^36 = 63 (mod 109)

Thus we divide z by 3^3, so z = 1. We also compute

     s(2) = 83^(108/27) = 48 (mod 109)

(Observe that the order of 48 is 27 modulo 109.) Since z = 1, we stop, 
and find the primitive root

     a = s(1)*s(2) = 33*48 = 58 (mod 109)

If we had done a brute-force search, we would have had to try four 
values, x = 2, 3, 5 and 6 before finding that x = 6 is also a 
primitive root.

I hope that this has been helpful. If you have further questions, 
please write again.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/