Primitive Roots and Unit Groups Modulo N

About this page

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 25 results · all verified · 14 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 11 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

1 · Prerequisites

Abstract Algebra

Combinatorics

Finite Counting, Factorials and Binomial Coefficients

Number Theory

Real Analysis

Set Theory

2 · Logical flowchart

3 · Items

Definition

Euler's criterion: if n has a primitive root, gcd(a,n)=1, and m≥1, then xᵐ≡ a (mod n) is solvable if and only if a^φ(n)/gcd(φ(n),m)≡1 (mod n)

Corollary

If n has a primitive root, gcd(a,n)=1, m≥1, and xᵐ≡ a (mod n) is solvable, then it has exactly gcd(φ(n),m) solution classes modulo n

Lemma

Primitive Roots and Unit Groups Modulo N

3 · Items

Primitive roots modulo n

A unit is a primitive root modulo n if and only if it generates (ℤ/nℤ)^×

The index ind_g(a) of a unit relative to a primitive root

Index calculus: products become sums and powers become scalar multiples modulo φ(n)

In a cyclic group of order m, gᵃ has order m/gcd(a,m)

The generators of a cyclic group of order m are the gᵃ with gcd(a,m)=1, so there are φ(m) of them

A direct product of two finite cyclic groups is cyclic if and only if their orders are coprime

For every prime p, the multiplicative group (ℤ/pℤ)^× is cyclic

Every prime modulus admits a primitive root

For prime p and d≥1, the congruence xᵈ≡1 (mod p) has gcd(d,p-1) nonzero solutions

Euler's criterion: if n has a primitive root, gcd(a,n)=1, and m≥1, then xᵐ≡ a (mod n) is solvable if and only if a^φ(n)/gcd(φ(n),m)≡1 (mod n)

If n has a primitive root, gcd(a,n)=1, m≥1, and xᵐ≡ a (mod n) is solvable, then it has exactly gcd(φ(n),m) solution classes modulo n

For an odd prime p and a primitive root g modulo p, at least one of g and g+p is primitive modulo p²

For odd prime p and s≥1, (1+pˢu)ᵖ≡1+pˢ⁺¹u (mod pˢ⁺²)

For odd prime p, p∤ u, and k≥1, the class of 1+pu has order pᵏ⁻¹ modulo pᵏ

For every odd prime p and k≥1, (ℤ/pᵏℤ)^× is cyclic of order pᵏ⁻¹(p-1)

An odd prime power pᵏ has exactly φ(φ(pᵏ)) primitive roots

For k≥3, the class of 5 has order 2ᵏ⁻² modulo 2ᵏ

For k≥3, (ℤ/2ᵏℤ)^×≅ C₂× C_2ᵏ⁻², generated uniquely as (-1)^ε5ʲ

For pairwise coprime positive moduli, the Chinese remainder bijection restricts to an isomorphism of unit groups

The unit group modulo n is the product of its odd-prime cyclic factors and its explicit 2-power factor

Carmichael's function λ(n) as the exponent of (ℤ/nℤ)^×

Carmichael's λ(n) is the maximum order of a unit modulo n

Carmichael's function on prime powers and its least-common-multiple formula

If gcd(a,n)=1, then a^λ(n)≡1 (mod n)

For odd n, primitive-root existence is equivalent for n and 2n

A positive integer admits a primitive root exactly when it is 1, 2, 4, pᵏ, or 2pᵏ for an odd prime p

A modulus with primitive roots has exactly φ(φ(n)) primitive roots