primitive root


Given any positive integer n, the group of units U(/n) of the ring /n is a cyclic groupMathworldPlanetmath iff n is 4, pm or 2pm for any odd positive prime p and any non-negative integer m.  A primitive rootMathworldPlanetmath is a generatorPlanetmathPlanetmathPlanetmath of this group of units when it is cyclic.

Equivalently, one can define the integer r to be a primitive root modulo n, if the numbers r0,r1,,rn-2 form a reduced residue systemMathworldPlanetmath modulo n.

For example, 2 is a primitive root modulo 5, since 1, 2, 22=4, 23=83(mod5) are all with 5 coprimeMathworldPlanetmathPlanetmath positive integers less than 5.

The generalized Riemann hypothesisMathworldPlanetmath implies that every prime numberMathworldPlanetmath p has a primitive root below 70(lnp)2.

References

Wikipedia, “Primitive root modulo n”

Title primitive root
Canonical name PrimitiveRoot
Date of creation 2013-03-22 16:04:33
Last modified on 2013-03-22 16:04:33
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 12
Author CWoo (3771)
Entry type Definition
Classification msc 11-00
Synonym primitive root modulo n
Synonym primitive elementMathworldPlanetmath
Related topic MultiplicativeOrderOfAnIntegerModuloM
Related topic PrimeResidueClass
Related topic UsingPrimitiveRootsAndIndexToSolveCongruences