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

 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.

 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 .

It is an interesting exercise to prove that only primes, 2*primes and prime
powers have primitive roots.   Thread Tools Show Printable Version Email this Page 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