Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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?

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

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

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,

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Modern Algebra
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search