Primitive root: Difference between revisions
imported>Richard Pinch (expanded) |
imported>Bruce M. Tindall mNo edit summary |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | |||
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''). | 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''). | ||
| Line 7: | Line 8: | ||
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''. | 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>. | 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> by a result of Burgess<ref>{{ cite journal | author=D.A. Burgess | title=The distribution of quadratic residues and non-residues | journal=Mathematika | volume=4 | pages=106-112 | year=1957 }}</ref>, and if the [[generalised Riemann hypothesis]] is true, this can be improved to an upper bound of <math>2 (\log p)^2</math> by a result of Bach<ref>{{cite journal | author=Eric Bach | title=Explicit bounds for primality testing and related problems | journal=Math. Comp. | volume=55 | number=191 | year=1990 | pages=355--380 }}</ref>. | ||
''Artin's conjecture for primitive roots'' states that any number ''g'' which is not a perfect square is infinitely often a primitive root. | ==Artin's conjecture== | ||
''Artin's conjecture for primitive roots'' states that any number ''g'' which is not a perfect square is infinitely often a primitive root. [[Roger Heath-Brown]] has shown that there are at most two exceptional prime numbers ''a'' for which Artin's conjecture fails.<ref>{{cite journal | author=D.R. Heath-Brown | title=Artin's conjecture for primitive roots | journal=Q. J. Math., Oxf. II. Ser. | volume=37 | pages=27-38 | year=1986}}</ref> | |||
==See also== | ==See also== | ||
* [[Primitive element]] | * [[Primitive element]] | ||
==References== | |||
<references/> | |||
Latest revision as of 16:43, 6 February 2009
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 by a result of Burgess[1], and if the generalised Riemann hypothesis is true, this can be improved to an upper bound of by a result of Bach[2].
Artin's conjecture
Artin's conjecture for primitive roots states that any number g which is not a perfect square is infinitely often a primitive root. Roger Heath-Brown has shown that there are at most two exceptional prime numbers a for which Artin's conjecture fails.[3]
See also
References
- ↑ D.A. Burgess (1957). "The distribution of quadratic residues and non-residues". Mathematika 4: 106-112.
- ↑ Eric Bach (1990). "Explicit bounds for primality testing and related problems". Math. Comp. 55: 355--380.
- ↑ D.R. Heath-Brown (1986). "Artin's conjecture for primitive roots". Q. J. Math., Oxf. II. Ser. 37: 27-38.