primitive roots

buzzmath

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?

matt grime

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.

robert Ihnot

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

devious_

Primitive roots are used in cryptography and such, so I guess that's one reason why they're important.

shmoe

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.

buzzmath

Thanks everyone for your help.