Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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 
element is called a primitive root.  There's more about this here:

  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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/