Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Primitive roots

  1. Mar 13, 2006 #1
    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?
  2. jcsd
  3. Mar 13, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Mar 13, 2006 #3
    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
  5. Mar 14, 2006 #4
    Primitive roots are used in cryptography and such, so I guess that's one reason why they're important.
  6. Mar 14, 2006 #5


    User Avatar
    Science Advisor
    Homework Helper

    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.
  7. Mar 14, 2006 #6
    Thanks everyone for your help.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook