Primitive root: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Richard Pinch
(new entry, just a placeholder, needs more work)
 
imported>Richard Pinch
(expanded)
Line 1: Line 1:
In [[number theory]], a '''primitive root''' of a [[modulus]] is a number whose powers run through all the residue classes [[coprime]] to the modulus.  This may be expressed by saying that ''n'' has a primitive root if the [[multiplicative group]] modulo ''n'' is [[cyclic group|cyclic]], and the primitive root is a [[generator]], having an [[order (group theory)|order]] equal to [[Euler's totient function]] φ(''n'').
In [[number theory]], a '''primitive root''' of a [[modulus]] is a number whose powers run through all the residue classes [[coprime]] to the modulus.  This may be expressed by saying that ''n'' has a primitive root if the [[multiplicative group]] modulo ''n'' is [[cyclic group|cyclic]], and the primitive root is a [[generator]], having an [[order (group theory)|order]] equal to [[Euler's totient function]] φ(''n''). Another way of saying that ''n'' has a primitive root is that the value of Carmichael's [[lambda function]], λ(''n'') is equal to φ(''n'').
 
The numbers which possess a primitive root are:
* 2 and 4;
* <math>p^n</math> and <math>2p^n</math> where ''p'' is an odd [[prime number|prime]].
 
If ''g'' is a primitive root modulo an odd prime ''p'', then one of ''g'' and ''g''+''p'' is a primitive root modulo <math>p^2</math> and indeed modulo <math>p^n</math> for all ''n''.
 
There is no known fast method for determining a primitive root modulo ''p'', if one exists.  It is known that the smallest primitive root modulo ''p'' is of the order of <math>p^{4/\sqrt e}</math>, and if the [[generalised Riemann hypothesis]] is true, this can be improved to an upper bound of <math>2 (\log p)^2</math>.
 
''Artin's conjecture for primitive roots'' states that any number ''g'' which is not a perfect square is infinitely often a primitive root.
 
==See also==
* [[Primitive element]]

Revision as of 13:22, 2 December 2008

In number theory, a primitive root of a modulus is a number whose powers run through all the residue classes coprime to the modulus. This may be expressed by saying that n has a primitive root if the multiplicative group modulo n is cyclic, and the primitive root is a generator, having an order equal to Euler's totient function φ(n). Another way of saying that n has a primitive root is that the value of Carmichael's lambda function, λ(n) is equal to φ(n).

The numbers which possess a primitive root are:

  • 2 and 4;
  • and where p is an odd prime.

If g is a primitive root modulo an odd prime p, then one of g and g+p is a primitive root modulo and indeed modulo for all n.

There is no known fast method for determining a primitive root modulo p, if one exists. It is known that the smallest primitive root modulo p is of the order of , and if the generalised Riemann hypothesis is true, this can be improved to an upper bound of .

Artin's conjecture for primitive roots states that any number g which is not a perfect square is infinitely often a primitive root.

See also