proof of properties of primitive roots

The material in the main article is conveniently recast in terms of the groups (/m)×, the multiplicative groupMathworldPlanetmath of units in /m. Note that the order of this group is exactly ϕ(m) where ϕ is the Euler phi function. Then saying that an integer g is a primitive rootMathworldPlanetmath of m is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to saying that the residue classMathworldPlanetmath of g(modm) generates (/m)×.


(of Theorem):
The proof of the theorem is an immediate consequence of the structureMathworldPlanetmath of (/m)× as an abelian groupMathworldPlanetmath; (/m)× is cyclic precisely for m=2,4,pk, or 2pk. ∎


(of PropositionPlanetmathPlanetmath):

  1. 1.

    Restated, this says that if the residue class of g(modm) generates (/m)×, then the set {1,g,g2,,gϕ(m)} is a complete set of representatives for (/m)×; this is obvious.

  2. 2.

    Restated, this says that g(modm) generates (/m)× if and only if g has exact order m, which is also obvious.

  3. 3.

    If g(modm) generates (/m)×, then g has exact order ϕ(m) and thus gs=gt(modm) if and only if gs-t=1 if and only if ϕ(m)s-t.

  4. 4.

    Suppose g generates (/m)×. Then (gk)r=1 if and only if gkr=1 if and only if ϕ(m)kr. Clearly we can choose r<ϕ(m) if and only if gcd(k,ϕ(m))>1.

  5. 5.

    This follows immediately from (4).∎

Title proof of properties of primitive roots
Canonical name ProofOfPropertiesOfPrimitiveRoots
Date of creation 2013-03-22 18:43:48
Last modified on 2013-03-22 18:43:48
Owner rm50 (10146)
Last modified by rm50 (10146)
Numerical id 4
Author rm50 (10146)
Entry type Proof
Classification msc 11-00