20050911, 15:49  #1 
Jun 2005
Near Beetlegeuse
110000100_{2} 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^(p1) = 1(mod p) for all a >= 1. One definition of Primitive Root that I have come across says that, where p1 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 = 71, 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 p1 can be expressed by a = r^k(mod p), with k a nonnegative integer < p1. 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^((p1)/q) > 1 (mod p) for all prime divisors q of p1. 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(p1)/q) is only an integer where q  p1. So what about the case where q does divide p1 but q is not a prime divisor of p1? 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? 
20050911, 18:14  #2  
Bamboozled!
"ð’‰ºð’ŒŒð’‡·ð’†·ð’€"
May 2003
Down not across
10,781 Posts 
Quote:
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 (p1). OK? (Exercise: prove this. It should be immediately obvious that zero is not an element of the group, so the order is at most p1.) 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 

20050911, 20:53  #3  
Jun 2005
Near Beetlegeuse
2^{2}·97 Posts 
Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
Thank you very much. 

20050912, 12:08  #4 
Bamboozled!
"ð’‰ºð’ŒŒð’‡·ð’†·ð’€"
May 2003
Down not across
10101000011101_{2} Posts 
You almost have enough to prove it's a group with order p1. 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.. p1. 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 nonzero 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..p1}, x^y mod p is nonzero mod p. There are p1 different elements x and y, so the group order is p1. Paul 
20050912, 12:36  #5  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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..... 

20050912, 12:43  #6  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
Alex 

20050912, 12:46  #7  
Nov 2003
2^{2}×5×373 Posts 
Quote:


20050921, 09:02  #8  
Jun 2005
Near Beetlegeuse
184_{16} Posts 
Quote:
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? 

20050921, 09:47  #9 
"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 kfold group operation of a with itself). If no such integer exists, the order is said to be infinite. Alex 
20050921, 11:10  #10  
Jun 2005
Near Beetlegeuse
388_{10} Posts 
Quote:
So that in Z/7*, ord(2) = 3, since 2^3 = 1(mod 7)? 

20050921, 11:31  #11  
Nov 2003
1D24_{16} Posts 
Quote:
[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. 

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  20180208 05:15 
Primitive roots for a set of primes  mart_r  Math  0  20130720 12:23 
Primitive root question  __HRB__  Math  0  20090710 00:41 
efficient generation of highly nonprimitive roots  vector  Math  7  20071114 16:07 
New primitive trinomials  akruppa  Math  0  20070906 20:23 