Primitive Elements vs. GeneratorsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/