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

### Primitive Elements vs. Generators

```Date: 05/24/2002 at 01:15:51
From: James
Subject: confused on primitive elements questions

I have no clue on how to solve this question:

The integer 97 is a prime number. Prove that x is a
primitive element modulo 97 where x =/ 0 if and only
if x^32 =/ 1 (mod 97) and x^48 =/ 1 (mod 97).

The operator "=/" means "is not congruent to".

What is a primitive element? Is it same as generator? If so, then why
use different terms?  If not, when do we differentiate between the two
(generator and primitive element)?

Thank you.
```

```
Date: 05/24/2002 at 09:09:08
From: Doctor Paul
Subject: Re: confused on primitive elements questions

A primitive elemement is the same as a generator.  The reason for the
multiple names is as follows:

This type of problem can occur in two contexts -- in a Number Theory
class, or in an Abstract Algebra class.  In Number Theory, such an

http://mathworld.wolfram.com/PrimitiveRoot.html

Primitive roots have been studied much longer than Abstract Algebra.

But as Abstract Algebra was developed, people began to look at the
subgroups of a group generated by certain elements.  A group is said
to be cyclic if one of its elements generates the entire group.  Such
an element is called a generator for the group.

In this particular example, the group of nonzero integers modulo a
prime p under multiplication forms a cyclic group and hence has a
generator.  This generator will be any of the phi(phi(p)) primitive
roots for the prime p. (In general, there can be more than one element
that generates the group.)

Now regarding the main question:

Prove that x is a primitive element modulo 97 where
x =/ 0 if and only if x^32 =/ 1 (mod 97) and x^48 =/ 1
(mod 97).

Well, one direction is easy.  Suppose x is a primitive element modulo
97.  Then the powers of x generate all of the nonzero elements of the
field.  So in particular, we know that x, x^2, x^3, ..., x^96 are
distinct.

Fermat's Little Theorem guarantees that x^96 = 1 (mod 97).  So it
cannot be the case that x^32 = 1 (mod 97) and it similarly cannot be
the case that x^48 = 1 (mod 97) since the powers of x are distinct.
That is, if x^96 = 1 (mod 97) then no other power of x less than 96
can be congruent to 1 mod 97.  Thus x^32 and x^48 must be congruent to
some other number mod 97 and this is what we wanted to show.

Now we need to establish the reverse direction.  Let x be an element
of the group of nonzero elements of Z_97 under multiplication.  Then
x is an element of a group which has order 96.  For this direction,
we get to assume that x^32 =/ 1 (mod 97) and x^48 =/ 1 (mod 97).
We'll use this assumption a bit later on.

We want to consider the subgroup generated by x.  We know from
Lagrange's Theorem that the order of a subgroup must divide the order
of the group.  So the only possibilities for the order of the
subgroup generated by x are the divisors of 96:

2, 4, 6, 8, 12, 16, 24, 32, 48, 96

Now we just have a bunch of cases to consider:

Suppose that x^2 = 1 (mod 97).

But then raising both sides to the 16th power gives:

x^32 = 1 mod 97.

This cannot be -- it contradicts one of our assumptions.

Suppose that x^4 = 1 mod 97.

But then raising both sides to the 8th power gives:

x^32 = 1 mod 97.

This cannot be -- it contradicts one of our assumptions.

Suppose that x^6 = 1 mod 97.

But then raising both sides to the 8th power gives:

x^48 = 1 mod 97.

This cannot be -- it contradicts one of our assumptions.

In a similar manner, you can eleminate all of the possibilities
except 96.  So it must be the case that x^96 = 1 mod 97 and that no
smaller power of x is congruent to 1 mod 97.  Thus x is a generator
for the group, or equivalently, x is a primitive root mod 97.

I hope this helps.  Please write back if you'd like to talk about
this some more.

- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Modern Algebra
College Number Theory
High School 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