Primitive Roots

[Numbers]

Note: where sqrt(a) means the square root of a, I shall say curt(a) to mean the cube root of a.

Fermat�s Little Theorem tells us that where p is prime, a^(p-1) = 1(mod p) for all a >= 1.

One definition of Primitive Root that I have come across says that, where p-1 is the least integer x >= 1 for which a^x = 1(mod p), a is a primitive root of p.

By this definition, we can see that since 2^3 = 1(mod 7) whereas 3 not = 7-1, 2 is not a Primitive Root of 7. But since there is not an integer x < 6 for which 3^x = 1(mod 7), 3 is a Primitive Root of 7.

If we say f(a, p) = the set of remainders a^x(mod p) for all x < p, then f(2, 7) = {2, 4, 1, 2, 4, 1} while f(3, 7) = {3, 2, 6, 4, 5, 1} and it is obvious that if 1 appears in the set in any position except the last then one at least of the other elements of f(a, p) is not in the set.

This gives us a second definition of Primitive Root that I have come across that says:

A Primitive Root of p is a number r such that any integer a between 1 and p-1 can be expressed by a = r^k(mod p), with k a non-negative integer < p-1.

Assuming that �any� in this instance means �all� we can easily see that this is in complete agreement with the previous definition where f(a, p) contains all integers > 0, < p. And, if and only if this is true will a be a Primitive Root of p.

Then I come across a third definition of Primitive Root that says:

If p is prime, r is a Primitive Root of p if and only if r^((p-1)/q) > 1 (mod p) for all prime divisors q of p-1.

From this we can easily see that 2^(6/2) = sqrt(2^6) = 1(mod 7) again proving that 2 is not a Primitive Root of 7. But 3^(6/2) = sqrt(3^6) = 6(mod 7) and 3^(6/3) = curt(3^6) = 2(mod 7) showing that 3 is a Primitive Root of 7.

One reason for this will be that 2^8 for example will pretty obviously have a sqrt and a 4th root but not an integer 5th root because 8/5 is not an integer. I understand this in the language of logarithms where inv(log(p-1)/q) is only an integer where q | p-1. So what about the case where q does divide p-1 but q is not a prime divisor of p-1?

I guess what I�m aiming at is that I already know the definition, more than one in fact, but I have no concept of the �meaning� of a primitive root. What does it mean for 3 to be a Primitive Root of 7?

[xilman]

Originally Posted by Numbers

I guess what I�m aiming at is that I already know the definition, more than one in fact, but I have no concept of the �meaning� of a primitive root. What does it mean for 3 to be a Primitive Root of 7?

Does the following help? Note that p is assumed prime in everything below.

Let x be an integer less than p. The powers of x form a group where the group operation is multiplication mod p and the identity is 1. Ok so far?

Next statement: the order of that group (i.e the number of elements in it) is (p-1). OK? (Exercise: prove this. It should be immediately obvious that zero is not an element of the group, so the order is at most p-1.)

Final statement: at least one element, x, exists such that all the powers of x constitute the entire group. (Exercise: prove this).

Such an element x is a primitive root.

Paul

[Numbers]

Originally Posted by xilman

Does the following help?

Yes, thank you very much.

Originally Posted by xilman

The powers of x form a group

I had only been playing with powers < p. It was only after realising that you said �the powers� without limit that I saw that as we increment the power y, then x^y(mod p) cycles through the group always in the same order. So in this sense the group behaves like a ring, even though it is not a ring because it has no zero element � see below.

Originally Posted by xilman

Ok so far?

Yes.

Originally Posted by xilman

the order of that group is (p-1). OK?

Not really, see below. Number this 1)

Originally Posted by xilman

zero is not an element of the group

Since p is prime > x, p does not divide x, and since all powers of x are only divisible by x or by the prime divisors of x neither x nor any of its powers are divisible by p. Therefore, zero is not an element of the group.

Originally Posted by xilman

so the order is at most p-1

Yes. This is why I was not sure about 1) above. It is obvious that the order of the group is at most p-1, but it is a big step from there to saying that it is exactly p-1. To prove this is analogous to proving that x exists, and from what I�ve seen so far this is not entirely obvious. All we�ve done so far is say �if x exists, then such and such is true�. See below.

Originally Posted by xilman

at least one element, x, exists such that all the powers of x constitute the entire group.

I agree that if x exists all powers of x will constitute the entire group, but I�m going to have to take it as read that if p is prime, x exists. However, at the current state of my math education I don�t think there is much value to be gained from trying to learn more than this right now. When the course I�m on gets up to group theory the light bulb will come on when I understand the significance of this. But as my fellow students are currently engaged � on another forum � in a discussion about the mystical significance of the 11th digit of pi (unfortunately I am not making this up) I am not holding my breath.

Thank you very much.

[xilman]

You almost have enough to prove it's a group with order p-1. Here's a sketch to get you started.

First, it's a finite group (because there are only p different residue classes modulo p and these can be represented by the integers 0.. p-1.

Second, 1 is the identity element.

Third, 0 is not in the group because it does not have a unique inverse --- 0^x = 0 for all non-zero x.

All you have to do (left as an easy exercise) is to show that for all elements x and y in the set {1..p-1}, x^y mod p is non-zero mod p.

There are p-1 different elements x and y, so the group order is p-1.


Paul

[R.D. Silverman]

Originally Posted by xilman

You almost have enough to prove it's a group with order p-1. Here's a sketch to get you started.

First, it's a finite group (because there are only p different residue classes modulo p and these can be represented by the integers 0.. p-1.

Second, 1 is the identity element.

Third, 0 is not in the group because it does not have a unique inverse --- 0^x = 0 for all non-zero x.

All you have to do (left as an easy exercise) is to show that for all elements x and y in the set {1..p-1}, x^y mod p is non-zero mod p.

There are p-1 different elements x and y, so the group order is p-1.


Paul

Proving that there exists at least one element of full order takes a bit
more work, however. Here are some hints:

Start by proving Lagrange's Theorem. That the order of an element
divides the order of the group.

Then suppose that x and y are elements that are NOT full order and
that x,y have different order.

Show that ord(x*y) = LCM( ord(x), ord(y))

Show that there is an element of order p for each prime p dividing the
order of the group.

Put this all together and.....

[akruppa]

Originally Posted by R.D. Silverman

Show that ord(x*y) = LCM( ord(x), ord(y))

This can't be correct. Let y=1/x, then ord(x)=ord(y) but ord(x*y)=1. Afaik ord(x*y)|LCM( ord(x), ord(y)), but I'm not aware of a stronger statement about the order of products (in a multiplicatively written group).

Alex

[R.D. Silverman]

Originally Posted by akruppa

This can't be correct. Let y=1/x, then ord(x)=ord(y) but ord(x*y)=1. Afaik ord(x*y)|LCM( ord(x), ord(y)), but I'm not aware of a stronger statement about the order of products (in a multiplicatively written group).

Alex

Yes. I was too hasty. Mea Culpa. Divides, not equals.

[Numbers]

Originally Posted by akruppa

Afaik ord(x*y)|LCM( ord(x), ord(y))

Since my group is closed under multiplication I cannot divide anything by anything. What I can do is multiply by the inverse, which is division by the back door. So we get

Ord(x*y)^-1 * Lcm( ord(x), ord(y) ) = some element in the group

Since ord(x) and ord(y) are elements of the group, all we have to show is that (x*y)^-1 * Lcm(x, y) is an element of the group.

By closure and inverses we know that (x*y)^-1 exists and is an element of the group, say g_1

By closure we know that (x*y) exists and is an element of the group, say g_2, so clearly x*y have at least one common multiple.

By closure we know that g_1 * g_2 is an element of the group.

I got the impression it was supposed to be harder than that. Am I missing something?

[akruppa]

>Since ord(x) and ord(y) are elements of the group

No, no! The order of an element a is an integer. It is the smallest positive integer k so that a^k is the neutral element of the group (where a^k is the k-fold group operation of a with itself). If no such integer exists, the order is said to be infinite.

Alex

[Numbers]

Originally Posted by akruppa

so that a^k is the neutral element of the group

By neutral element I take it you mean the identity element?

So that in Z/7*, ord(2) = 3, since 2^3 = 1(mod 7)?

[R.D. Silverman]

Originally Posted by Numbers

[1]

One definition of Primitive Root that I have come across says that, where p-1 is the least integer x >= 1 for which a^x = 1(mod p), a is a primitive root of p.


This gives us a second definition of Primitive Root that I have come across that says:

[2]

A Primitive Root of p is a number r such that any integer a between 1 and p-1 can be expressed by a = r^k(mod p), with k a non-negative integer < p-1.

[1] is the usual definition. A better way of expressing it is to say that
a primitive root is an element of a group whose order equals the order of
the group.

[2] says that a primitive root generates the entire group; The powers
of a primitive root r generate the entire group. This is what is known as
a *cyclic* group. While this can be used as a definition, it is more
properly viewed as a *consequence* of definition [1].

It is an interesting exercise to prove that only primes, 2*primes and prime
powers have primitive roots.