mersenneforum.org > Math Primitive Roots
 Register FAQ Search Today's Posts Mark Forums Read

 2005-09-11, 15:49 #1 Numbers     Jun 2005 Near Beetlegeuse 1100001002 Posts Primitive Roots 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?
2005-09-11, 18:14   #2
xilman
Bamboozled!

"ð’‰ºð’ŒŒð’‡·ð’†·ð’€­"
May 2003
Down not across

10,781 Posts

Quote:
 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

2005-09-11, 20:53   #3
Numbers

Jun 2005
Near Beetlegeuse

22·97 Posts

Quote:
 Originally Posted by xilman Does the following help?
Yes, thank you very much.

Quote:
 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.

Quote:
 Originally Posted by xilman Ok so far?
Yes.

Quote:
 Originally Posted by xilman the order of that group is (p-1). OK?
Not really, see below. Number this 1)

Quote:
 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.

Quote:
 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.

Quote:
 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.

 2005-09-12, 12:08 #4 xilman Bamboozled!     "ð’‰ºð’ŒŒð’‡·ð’†·ð’€­" May 2003 Down not across 101010000111012 Posts 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
2005-09-12, 12:36   #5
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 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.....

2005-09-12, 12:43   #6
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 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

2005-09-12, 12:46   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 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.

2005-09-21, 09:02   #8
Numbers

Jun 2005
Near Beetlegeuse

18416 Posts

Quote:
 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?

 2005-09-21, 09:47 #9 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts >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
2005-09-21, 11:10   #10
Numbers

Jun 2005
Near Beetlegeuse

38810 Posts

Quote:
 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)?

2005-09-21, 11:31   #11
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Number Theory Discussion Group 0 2018-02-08 05:15 mart_r Math 0 2013-07-20 12:23 __HRB__ Math 0 2009-07-10 00:41 vector Math 7 2007-11-14 16:07 akruppa Math 0 2007-09-06 20:23

All times are UTC. The time now is 18:13.

Tue Aug 3 18:13:49 UTC 2021 up 11 days, 12:42, 1 user, load averages: 3.05, 3.44, 3.28