mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-09-11, 15:49   #1
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

1100001002 Posts
Default Primitive Roots

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

Fermats 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 Im 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?
Numbers is offline   Reply With Quote
Old 2005-09-11, 18:14   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

10,781 Posts
Default

Quote:
Originally Posted by Numbers
I guess what Im 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
xilman is offline   Reply With Quote
Old 2005-09-11, 20:53   #3
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22·97 Posts
Default

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 Ive seen so far this is not entirely obvious. All weve 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 Im 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 dont think there is much value to be gained from trying to learn more than this right now. When the course Im 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.
Numbers is offline   Reply With Quote
Old 2005-09-12, 12:08   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

101010000111012 Posts
Default

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
xilman is offline   Reply With Quote
Old 2005-09-12, 12:36   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

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.....
R.D. Silverman is offline   Reply With Quote
Old 2005-09-12, 12:43   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-09-12, 12:46   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-09-21, 09:02   #8
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

18416 Posts
Default

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?
Numbers is offline   Reply With Quote
Old 2005-09-21, 09:47   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

>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
akruppa is offline   Reply With Quote
Old 2005-09-21, 11:10   #10
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

38810 Posts
Default

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)?
Numbers is offline   Reply With Quote
Old 2005-09-21, 11:31   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
primitive roots- when the base is a quadratic algebraic integer devarajkandadai Number Theory Discussion Group 0 2018-02-08 05:15
Primitive roots for a set of primes mart_r Math 0 2013-07-20 12:23
Primitive root question __HRB__ Math 0 2009-07-10 00:41
efficient generation of highly non-primitive roots vector Math 7 2007-11-14 16:07
New primitive trinomials 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.