What Are Primitive Roots and Why Are They Important?

Click For Summary

Discussion Overview

The discussion revolves around the concept of primitive roots, their significance, and methods for determining their existence and quantity for given integers. It touches on theoretical aspects, practical applications, and specific cases in number theory.

Discussion Character

  • Exploratory
  • Technical explanation
  • Conceptual clarification
  • Debate/contested

Main Points Raised

  • Some participants express curiosity about the importance of primitive roots and how to identify them.
  • One participant explains that a primitive root of Z/nZ is a generator of the group of units and notes conditions under which a primitive root exists, such as when n is prime or a specific form involving primes.
  • Another participant describes the relationship between primitive roots and the Euler Phi function, stating that a number r is a primitive root modulo M if r raised to the power of Phi(M) equals 1 modulo M, and outlines a method to check this.
  • It is mentioned that the number of primitive roots can be determined based on the elements that are relatively prime to Phi(M), though this does not provide the roots themselves.
  • One participant highlights the application of primitive roots in cryptography as a reason for their importance.
  • Another participant lists specific cases where primitive roots exist, including when N is 1, 2, 4, or related to powers of odd primes.

Areas of Agreement / Disagreement

Participants present multiple viewpoints on the conditions for the existence of primitive roots and their applications, indicating that there is no consensus on all aspects of the topic.

Contextual Notes

Some limitations include the lack of detailed definitions and the need for further exploration of specific cases where primitive roots do not exist, such as modulus 8.

buzzmath
Messages
108
Reaction score
0
I was curious why primitive roots are so important? Also, how one would find out if a number has a primitive root and what and how many of them they are?
 
Physics news on Phys.org
Let n be some integer, a primitive root, if one exists, of Z/nZ is a generator of the group of units. One may show that there is such if and only if n is prime, 2 times a prime or one of a small number of other cases (1 I think, but I don't have a book to hand to check so take that with a pinch of salt).

The point is that a primitive root is a cyclic generator for the group: any other element is a power of that root.

It is an easy exercise to verify the number of them in a given situation; it is after all elementary group theory for a group of known order: if g is a generator of G then the number of other generators is well known (to to work it out if you know a little group theory).

To find out if something is a primitive root one would simply check that it satisfies the definition.
 
A primitive root Modulo M is a number,r, such that the Euler Phi function, Phi(M), is the smallest value such at r^Phi(M) ==1 Mod M. In the case of a prime, p, this means that r^(p-1) ==1 Mod p is the smallest power such this occurs.

You want to know if a number,r, is a primitive root modulo M? This is simple, just consider all the powers of r, r^1, r^2...r^(phi(M), if only r^Phi(M)==1 Mod M, then r is a primitative root.

If the group is of order Phi(M), then, if there is a primitative root, the number of primitative roots is the number of elements relative prime to Phi(M), or Phi(Phi(M)). This, however does not find these roots. Some cases to do not have a primitive root, the first Modulus being 8. http://mathworld.wolfram.com/PrimitiveRoot.html
 
Primitive roots are used in cryptography and such, so I guess that's one reason why they're important.
 
You have a primitive root mod N when N is 1, 2, 4, the power of an odd prime, or 2 times the power of an odd prime, and no others.
 
Thanks everyone for your help.
 

Similar threads

Number Theory What books or materials are needed to understand primitive roots?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Are there primitive roots in Z_32?
  • · Replies 5 ·
Replies
5
Views
3K
MHB Number of natural numbers that have primitive roots
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Quintic Polynomial Tschirnhaus Transform: Possible complex Bring Radicals
  • · Replies 0 ·
Replies
0
Views
3K
Undergrad Questions Regarding Primitive Unit Cell
  • · Replies 4 ·
Replies
4
Views
4K
Undergrad Question on Primitive Roots and GCDs
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Finding a polynomial that has solution (root) as the sum of roots
  • · Replies 13 ·
Replies
13
Views
2K
Graduate Classification of reductive groups via root datum
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Matrix rank in terms of determinant polynomial
  • · Replies 14 ·
Replies
14
Views
4K
Undergrad Primitive Elements and Free Modules .... ....
  • · Replies 2 ·
Replies
2
Views
2K