Encyclopedia > Primitive root modulo n

  Article Content

Primitive root modulo n

Primitive roots modulo n are a concept in number theory. If n is an integer, the numbers coprime to n, taken modulo n, form a group with multiplication as operation; it is written as (Z/nZ)×. This group is cyclic if and only if n is equal to 2 or 4 or pk or 2 pk for an odd prime number p and k ≥ 1. A generator of this cyclic group is called a primitive root modulo n.

Take for example n = 14. The elements of (Z/14Z)× are the congruence classes of 1, 3, 5, 9, 11 and 13. Then 3 is a primitive root modulo 14, as we have 32 = 9, 33 = 13, 34 = 11, 35 = 5 and 36 = 1 (modulo 14). The only other primitive root modulo 14 is 5.

Here is a table containing the smallest primitive root for various values of n (see A046145 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A046145)):

n primitive root mod n

No simple general formula to compute primitive roots modulo n is known. There are however methods to locate a primitive root that are faster than simply trying out all candidates: first compute φ(n), the order of (Z/nZ)×. Then determine the different prime factors of φ(n), say p1,...,pk. Now, for every element m of (Z/nZ)×, compute

<math>m^{\phi(n)/p_i}\mod n \qquad\mbox{ for } i=1,\ldots,k</math>
using the fast exponentiating by squaring. As soon as you find a number m for which these k results are all different from 1, you stop: m is a primitive root.

The number of primitive roots modulo n is equal to φ(φ(n)) since, in general, a cyclic group with r elements has φ(r) generators.

There exist positive constants C, ε and p0 such that, for every prime pp0, there exists a primitive root modulo p that is less than C p1/4+ε. If the generalized Riemann hypothesis is true, then for every prime number p, there exists a primitive root modulo p that is less than 70 (ln(p))2.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... with their corsets and pantaloons[?] in favor of "step-in" panties. They also wrapped cloth across their breasts in order to flatten them. Flapper dresses were straight and ...

This page was created in 72.3 ms