properties of primitive roots


Definition.

Let m>1 be an integer. An integer g is said to be a primitive rootMathworldPlanetmath of m if gcd(g,m)=1 and the multiplicative orderMathworldPlanetmath of g is exactly ϕ(m), where ϕ is the Euler phi function. In other words, gϕ(m)1modm and gn1modm for any n<ϕ(m).

Theorem.

An integer m>1 has a primitive root if and only if m is 2,4,pk or 2pk for some k1. In particular, every prime has a primitive root.

Proposition.

Let m>1 be an integer.

  1. 1.

    If g is a primitive root of m then the set {1,g,g2,,gϕ(m)} is a complete set of representatives for (/m)×.

  2. 2.

    If gcd(g,m)=1 then g is a primitive root of m if and only if gϕ(m)/q1modm for every prime divisorPlanetmathPlanetmathPlanetmath q of ϕ(m).

  3. 3.

    If g is a primitive root of m, then gsgtmodm if and only if stmodϕ(m). Thus gs1modm if and only if ϕ(m) divides s.

  4. 4.

    If g is a primitive root of m, then gk is a primitive root of m if and only if gcd(k,ϕ(m))=1.

  5. 5.

    If m has a primitive root then m has exactly ϕ(ϕ(m)) incongruent primitive roots.

Title properties of primitive roots
Canonical name PropertiesOfPrimitiveRoots
Date of creation 2013-03-22 16:20:47
Last modified on 2013-03-22 16:20:47
Owner alozano (2414)
Last modified by alozano (2414)
Numerical id 4
Author alozano (2414)
Entry type Theorem
Classification msc 11-00