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.

Primitive Roots and Unit Groups Modulo N

1 · Prerequisites

2 · Summary

The published unit group $(Z / n Z)^{\times}$ collects the residue classes coprime to $n$ , the unit criterion recognises them, and Euler's totient counts them. The order of a group element, its characterisation by which powers are trivial, and the fact that it divides the order of the group constrain every generator argument. The Chinese remainder theorem splits $Z / n Z$ along a prime factorisation, $Z / p Z$ is a field, a finite subgroup of the units of an integral domain is cyclic, and the solvability and solution count of a linear congruence are known. Coprimality, least common multiples and the $p$ -adic valuation supply the remaining arithmetic.

A primitive root modulo $n$ is a generator of the unit group, and the index relative to a chosen generator converts multiplication into addition modulo $φ (n)$ . Cyclicity of the unit group of a prime field yields primitive roots modulo a prime, Euler's criterion for the solvability of $x^{m} \equiv a$ , and the exact number of its solution classes. The page then lifts a primitive root from $p$ to every odd prime power and determines the exceptional structure $(Z / 2^{k} Z)^{\times} ≅ C_{2} \times C_{2^{k - 2}}$ for $k \geq 3$ . The Chinese remainder decomposition assembles the prime-power factors into the structure of the unit group modulo any $n$ , and from it the page derives the Carmichael function and its formula, classifies the moduli $1, 2, 4, p^{k}, 2 p^{k}$ admitting primitive roots, and counts them.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Primitive roots modulo $n$

Definition

Let $n \geq 1$ . A unit $g \in (Z / n)^{\times}$ is a primitive root modulo $n$ when

$ord (g) = φ (n),$

where the unit group and Euler totient are those of The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ and the order is that of The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity. Thus the unique class modulo $1$ is a primitive root under this definition, since both its order and $φ (1)$ are $1$ .

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

A unit is a primitive root modulo $n$ if and only if it generates $(Z / n Z)^{\times}$

Statement

Let $n \geq 1$ and $g \in (Z / n)^{\times}$ . Then $g$ is a primitive root modulo $n$ if and only if

$⟨ g ⟩ = (Z / n)^{\times} .$

Facts & Assumptions

Given: A positive integer $n$ and a unit $g$ modulo $n$ .

[L1]

A primitive root modulo $n$ is a unit whose order is $φ (n)$ (Primitive roots modulo $n$ ).

[L2]

If $g$ has finite order $r$ , then $⟨ g ⟩$ has exactly $r$ elements (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L3]

The subgroup $⟨ g ⟩$ is the smallest subgroup containing $g$ (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups).

[L4]

The unit group modulo $n$ has exactly $φ (n)$ elements (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

Proof

technique · direct

1.1L2L4

The unit group has $φ (n)$ elements by [L4], while [L2] gives $∣ ⟨ g ⟩ ∣ = ord (g)$ .

2.1step 1.1L1L3

If $g$ is primitive, [L1] and step 1.1 give $∣ ⟨ g ⟩ ∣ = ∣ (Z / n)^{\times} ∣$ ; since [L3] makes $⟨ g ⟩$ a subgroup of the finite unit group, the two sets are equal.

3.1step 1.1L1∎

Conversely, if $⟨ g ⟩ = (Z / n)^{\times}$ , step 1.1 gives $ord (g) = φ (n)$ , so $g$ is primitive by [L1].

DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 2026-08-16Open item page →

The index ${ind}_{g} (a)$ of a unit relative to a primitive root

Definition

Let $n \geq 1$ and let $g$ be a primitive root modulo $n$ . For every $a \in (Z / n)^{\times}$ , the index of $a$ relative to $g$ is the unique residue class

${ind}_{g} (a) \in Z / φ (n)$

such that $g^{r} = a$ whenever the class is represented by $r \in Z$ .

Existence follows from A unit is a primitive root modulo $n$ if and only if it generates $(Z / n Z)^{\times}$ , since every unit is a power of $g$ . If $g^{r} = g^{s}$ , then $g^{r - s} = 1$ , and If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ with $ord (g) = φ (n)$ gives $r \equiv s (m o d φ (n))$ ; hence the residue class is well-defined and unique.

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

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

Statement

Let $g$ be a primitive root modulo $n$ . For units $a, b$ modulo $n$ and $k \in Z$ ,

${ind}_{g} (a b) = {ind}_{g} (a) + {ind}_{g} (b), {ind}_{g} (a^{k}) = k {ind}_{g} (a)$

in $Z / φ (n)$ .

Facts & Assumptions

Given: A primitive root $g$ modulo $n$ , units $a, b$ , and an integer $k$ .

[L1]

The index of a unit is its unique exponent class modulo $φ (n)$ relative to $g$ (The index ${ind}_{g} (a)$ of a unit relative to a primitive root).

[L2]

Group powers satisfy $g^{r + s} = g^{r} g^{s}$ and $(g^{r})^{k} = g^{r k}$ (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute).

[L3]

For an element of order $f$ , $g^{u} = 1$ if and only if $f ∣ u$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

Proof

technique · direct

1.1L1

Choose integers $r, s$ representing ${ind}_{g} (a)$ and ${ind}_{g} (b)$ , so $a = g^{r}$ and $b = g^{s}$ .

2.1step 1.1L2

By [L2], $a b = g^{r + s}$ and $a^{k} = g^{r k}$ .

3.1step 2.1L1L3∎

Applying the uniqueness in [L1], equivalently [L3], to step 2.1 gives the two asserted congruences modulo $φ (n)$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

In a cyclic group of order $m$ , $g^{a}$ has order $m / \gcd (a, m)$

Statement

Let $G = ⟨ g ⟩$ be cyclic of finite order $m \geq 1$ . For every integer $a$ ,

$ord (g^{a}) = \frac{m}{\gcd (a, m)} .$

Facts & Assumptions

Given: A generator $g$ of a cyclic group of order $m$ and an integer $a$ .

[L1]

The order of an element is the least positive exponent giving the identity (The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity).

[L2]

Since $ord (g) = m$ , one has $g^{u} = 1$ exactly when $m ∣ u$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L3]

$(g^{a})^{t} = g^{a t}$ for every integer $t$ (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute).

[L4]

Put $d = \gcd (a, m)$ ; then $d$ divides both $a$ and $m$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L5]

After dividing two integers by their nonzero greatest common divisor, the resulting quotients are coprime (If $d = \gcd (a, b)$ is nonzero then $a / d$ and $b / d$ are coprime).

[L6]

If $\gcd (r, s) = 1$ and $r ∣ s t$ , then $r ∣ t$ (If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ ).

Proof

technique · direct

1.1L4L5algebra

Since $m \geq 1$ , the common divisor $d$ is nonzero. Write $a = d a^{'}$ and $m = d m^{'}$ ; [L5] gives $\gcd (a^{'}, m^{'}) = 1$ .

2.1L2L3step 1.1algebra

By [L2] and [L3], $(g^{a})^{t} = 1$ is equivalent to $m ∣ a t$ , hence to $m^{'} ∣ a^{'} t$ .

3.1step 2.1L6

By [L6] and $\gcd (a^{'}, m^{'}) = 1$ , the condition in step 2.1 is equivalent to $m^{'} ∣ t$ .

4.1step 3.1L1∎

Thus the least positive $t$ with $(g^{a})^{t} = 1$ is $m^{'} = m / d$ , which is the asserted order by [L1].

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

The generators of a cyclic group of order $m$ are the $g^{a}$ with $\gcd (a, m) = 1$ , so there are $φ (m)$ of them

Statement

Let $G = ⟨ g ⟩$ be cyclic of order $m$ . The generators of $G$ are exactly the elements $g^{a}$ with $\gcd (a, m) = 1$ , for $a$ taken modulo $m$ . Consequently $G$ has $φ (m)$ generators.

Facts & Assumptions

Given: A cyclic group $G = ⟨ g ⟩$ of finite order $m$ .

[L1]

$ord (g^{a}) = m / \gcd (a, m)$ (In a cyclic group of order $m$ , $g^{a}$ has order $m / \gcd (a, m)$ ).

[L2]

For $x$ of finite order $r$ , the powers $x^{0}, \dots, x^{r - 1}$ are pairwise distinct and $⟨ x ⟩ = {x^{s} : s < r}$ , so $⟨ x ⟩$ is finite with $∣ ⟨ x ⟩ ∣ = ord (x)$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L3]

The unit classes modulo $m$ are exactly the classes represented by integers coprime to $m$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

[L4]

There are $φ (m)$ units modulo $m$ (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

Proof

technique · direct

1.1L1L2algebra

By [L2], $∣ ⟨ g^{a} ⟩ ∣ = ord (g^{a})$ and $∣ G ∣ = ∣ ⟨ g ⟩ ∣ = ord (g) = m$ . Since $⟨ g^{a} ⟩ \subseteq G$ and $G$ is finite, $g^{a}$ generates $G$ exactly when $∣ ⟨ g^{a} ⟩ ∣ = m$ , that is exactly when $ord (g^{a}) = m$ . By [L1] this says $m / \gcd (a, m) = m$ , equivalently $\gcd (a, m) = 1$ .

1.2L2

By [L2] the powers $g^{0}, \dots, g^{m - 1}$ are pairwise distinct, so distinct exponent classes modulo $m$ give distinct powers of $g$ .

2.1step 1.1step 1.2L3L4∎

By [L3] and [L4], exactly $φ (m)$ exponent classes satisfy the condition in step 1.1, proving the count.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

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

Statement

If $C_{m}$ and $C_{n}$ are finite cyclic groups of orders $m, n \geq 1$ , then $C_{m} \times C_{n}$ is cyclic if and only if $\gcd (m, n) = 1$ .

Facts & Assumptions

Given: Cyclic groups $C_{m} = ⟨ g ⟩$ and $C_{n} = ⟨ h ⟩$ .

[L1]

The external direct product uses componentwise multiplication (The external direct product $G \times H$ with componentwise multiplication) and is a group ( $G \times H$ is a group with identity $(e_{G}, e_{H})$ , coordinatewise inverses, and homomorphic coordinate projections).

[L2]

A power of an element of order $r$ is the identity exactly when its exponent is divisible by $r$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L3]

$lcm (r, s)$ is the least positive common multiple of $r$ and $s$ (Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ).

[L4]

For positive integers $m, n$ , $\gcd (m, n) lcm (m, n) = m n$ (Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ ).

Proof

technique · direct

1.1L1L2L3

For $(x, y) \in C_{m} \times C_{n}$ with coordinate orders $r$ and $s$ , [L1] and [L2] show that $(x, y)^{t} = (1, 1)$ exactly when both $r ∣ t$ and $s ∣ t$ ; its order is therefore $lcm (r, s)$ by [L3].

2.1step 1.1L4algebra

If $\gcd (m, n) = 1$ , [L4] and step 1.1 give $ord (g, h) = lcm (m, n) = m n$ , so $(g, h)$ generates the product of order $m n$ .

3.1step 1.1L2L3L4algebra∎

Conversely, if the product is cyclic, a generator $(x, y)$ has order $m n$ . Its coordinate orders divide $m$ and $n$ , so step 1.1 gives $m n = lcm (r, s) \leq lcm (m, n) \leq m n$ ; hence $lcm (m, n) = m n$ , and [L4] gives $\gcd (m, n) = 1$ .

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

For every prime $p$ , the multiplicative group $(Z / p Z)^{\times}$ is cyclic

Statement

For every prime $p$ , the group $(Z / p)^{\times}$ is cyclic of order $p - 1$ .

Facts & Assumptions

Given: A prime $p$ .

[L1]

$Z / p$ is a field (For every prime $p$ , the two operations on $Z / p$ make it a field).

[L2]

Every field is an integral domain (Every field is a commutative ring with $1 \neq 0$ ; it is an integral domain, and it is a commutative division ring).

[L3]

Every finite subgroup of the unit group of an integral domain is cyclic (Every finite subgroup of the unit group of an integral domain is cyclic).

[L4]

$(Z / p)^{\times}$ is finite of order $φ (p)$ (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[L5]

For prime $p$ , $φ (p) = p - 1$ ( $φ (1) = 1$ , and $φ (p) = p - 1$ for every prime $p$ ).

Proof

technique · direct

1.1L1L2

By [L1] and [L2], $Z / p$ is an integral domain.

2.1step 1.1L3L4L5∎

By [L4], its entire unit group is a finite subgroup of its units, so [L3] makes it cyclic; [L4] and [L5] give its order. This includes $p = 2$ , when the group is trivial.

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Every prime modulus admits a primitive root

Statement

Every prime $p$ admits a primitive root modulo $p$ .

Facts & Assumptions

Given: A prime $p$ .

[L1]

The unit group $(Z / p)^{\times}$ is a finite cyclic group (For every prime $p$ , the multiplicative group $(Z / p Z)^{\times}$ is cyclic).

[L2]

A unit is a primitive root exactly when it generates the unit group (A unit is a primitive root modulo $n$ if and only if it generates $(Z / n Z)^{\times}$ ).

Proof

technique · direct

1.1L1choose

Choose a generator $g$ of the cyclic group in [L1]; such a generator exists also when $p = 2$ , since the one-element group is cyclic.

2.1step 1.1L2∎

By [L2], the chosen $g$ is a primitive root modulo $p$ .

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

For prime $p$ and $d \geq 1$ , the congruence $x^{d} \equiv 1 (m o d p)$ has $\gcd (d, p - 1)$ nonzero solutions

Statement

Let $p$ be prime and $d \geq 1$ . The congruence $x^{d} \equiv 1 (m o d p)$ has exactly $\gcd (d, p - 1)$ nonzero residue-class solutions. In particular, it has exactly $d$ solutions when $d ∣ (p - 1)$ .

Facts & Assumptions

Given: A prime $p$ and a positive integer $d$ .

[L1]

$(Z / p)^{\times}$ is cyclic of order $p - 1$ (For every prime $p$ , the multiplicative group $(Z / p Z)^{\times}$ is cyclic).

[L2]

If $g$ has order $p - 1$ , then $g^{u} = 1$ exactly when $(p - 1) ∣ u$ , and its powers with exponents modulo $p - 1$ are distinct (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L3]

The greatest common divisor $c = \gcd (d, p - 1)$ divides both $d$ and $p - 1$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L4]

Dividing two integers by their nonzero greatest common divisor gives coprime quotients (If $d = \gcd (a, b)$ is nonzero then $a / d$ and $b / d$ are coprime).

[L5]

If two integers are coprime and one divides a product containing the other, it divides the remaining factor (If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ ).

Proof

technique · direct

1.1L1L2choose

Choose a generator $g$ from [L1]. Every nonzero class is uniquely $g^{a}$ with $a$ modulo $p - 1$ .

1.2L3L4algebra

Put $c = \gcd (d, p - 1)$ . Since $p - 1 \geq 1$ , $c$ is nonzero; write $d = c d^{'}$ , $p - 1 = c m^{'}$ , and use [L4] to obtain $\gcd (d^{'}, m^{'}) = 1$ .

2.1step 1.1step 1.2L2L5

By [L2], $(g^{a})^{d} = 1$ exactly when $(p - 1) ∣ a d$ , which by step 1.2 and [L5] is equivalent to $m^{'} ∣ a$ .

3.1step 2.1algebra∎

Modulo $p - 1 = c m^{'}$ , precisely the $c$ classes $0, m^{'}, \dots, (c - 1) m^{'}$ satisfy step 2.1, proving the count. If $d ∣ (p - 1)$ then $c = d$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Euler's criterion: if $n$ has a primitive root, $\gcd (a, n) = 1$ , and $m \geq 1$ , then $x^{m} \equiv a (m o d n)$ is solvable if and only if $a^{φ (n) / \gcd (φ (n), m)} \equiv 1 (m o d n)$

Statement

Let $n \geq 1$ admit a primitive root, let $\gcd (a, n) = 1$ , and let $m \geq 1$ . Put $d = \gcd (m, φ (n))$ . Then

$x^{m} \equiv a (m o d n)$

is solvable if and only if

$a^{φ (n) / d} \equiv 1 (m o d n) .$

Facts & Assumptions

Given: Integers $n \geq 1$ , $a$ , and $m \geq 1$ satisfying the stated hypotheses, and $d = \gcd (m, φ (n))$ .

[L1]

A primitive root has order $φ (n)$ (Primitive roots modulo $n$ ).

[L2]

Relative to a primitive root $g$ , every unit has a unique index modulo $φ (n)$ (The index ${ind}_{g} (a)$ of a unit relative to a primitive root).

[L3]

Index calculus turns a power into scalar multiplication of its index (Index calculus: products become sums and powers become scalar multiples modulo $φ (n)$ ).

[L4]

The congruence $u y \equiv v (m o d f)$ is solvable exactly when $\gcd (u, f) ∣ v$ (For $n \geq 1$ , $a x \equiv b (m o d n)$ is solvable exactly when $\gcd (a, n) ∣ b$ , and then has exactly $\gcd (a, n)$ solution classes modulo $n$ ).

[L5]

A greatest common divisor divides both of its arguments (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L6]

A class modulo $n$ is a unit exactly when its representative is coprime to $n$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

Proof

technique · direct

1.1L1L2L6choosealgebra

Choose a primitive root $g$ , put $f = φ (n)$ , and let $k = {ind}_{g} (a)$ . By [L6], $a$ is a unit. If $x^{m} = a$ , then $x (x^{m - 1} a^{- 1}) = 1$ , so every solution $x$ is also a unit.

1.2L1L3L5algebra

Again by [L1] and [L3], $a^{f / d} = 1$ exactly when $f ∣ k f / d$ . Since $d ∣ f$ by [L5], this is equivalent to $d ∣ k$ .

2.1step 1.1L2L3L4

By [L2] and [L3], writing a candidate unit as $x = g^{y}$ turns $x^{m} = a$ in the unit group into $m y \equiv k (m o d f)$ . By [L4], this is solvable exactly when $d ∣ k$ .

3.1step 2.1step 1.2∎

Steps 2.1 and 1.2 give the claimed biconditional. The argument also covers $n = 1$ and $m = 1$ , where $f = d = 1$ .

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

If $n$ has a primitive root, $\gcd (a, n) = 1$ , $m \geq 1$ , and $x^{m} \equiv a (m o d n)$ is solvable, then it has exactly $\gcd (φ (n), m)$ solution classes modulo $n$

Statement

Let $n \geq 1$ admit a primitive root, let $\gcd (a, n) = 1$ , and let $m \geq 1$ . If $x^{m} \equiv a (m o d n)$ is solvable, then it has exactly

$\gcd (φ (n), m)$

solution classes modulo $n$ .

Facts & Assumptions

Given: The stated hypotheses and the solvability of $x^{m} \equiv a (m o d n)$ .

[L1]

Relative to a primitive root $g$ , every unit has a unique index modulo $φ (n)$ (The index ${ind}_{g} (a)$ of a unit relative to a primitive root).

[L2]

The index of $x^{m}$ is congruent to $m {ind}_{g} (x)$ modulo $φ (n)$ (Index calculus: products become sums and powers become scalar multiples modulo $φ (n)$ ).

[L3]

For $u, v \in Z$ and $f \geq 1$ , the congruence $u y \equiv v (m o d f)$ is solvable exactly when $\gcd (u, f) ∣ v$ , and when solvable it has exactly $\gcd (u, f)$ solution classes in $Z / f$ (For $n \geq 1$ , $a x \equiv b (m o d n)$ is solvable exactly when $\gcd (a, n) ∣ b$ , and then has exactly $\gcd (a, n)$ solution classes modulo $n$ ).

[L4]

A class modulo $n$ is a unit exactly when its representative is coprime to $n$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

Proof

technique · direct

1.1L1choose

Choose a primitive root $g$ , put $f = φ (n)$ , and let $r = {ind}_{g} (a)$ .

1.2L4givenalgebra

By [L4], $a$ is a unit. If $x^{m} = a$ , then $x (x^{m - 1} a^{- 1}) = 1$ , so every solution $x$ is a unit.

2.1step 1.1step 1.2L1L2

By [L1], exponent classes $y$ modulo $f$ parametrise unit classes bijectively as $x = g^{y}$ , and by [L2] the solutions correspond exactly to the classes satisfying $m y \equiv r (m o d f)$ .

3.1step 2.1L3∎

Here $f = φ (n) \geq 1$ , so [L3] applies; the latter congruence is solvable by the Given, so [L3] gives exactly $\gcd (m, f) = \gcd (φ (n), m)$ classes; the bijection in step 2.1 preserves this count, including when $n = 1$ or $m = 1$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

For an odd prime $p$ and a primitive root $g$ modulo $p$ , at least one of $g$ and $g + p$ is primitive modulo $p^{2}$

Statement

Let $p$ be an odd prime and let the integer $g$ represent a primitive root modulo $p$ . Then at least one of $g$ and $g + p$ represents a primitive root modulo $p^{2}$ .

Facts & Assumptions

Given: An odd prime $p$ and a primitive root $g$ modulo $p$ .

[L1]

A class is a primitive root when its order equals the totient of the modulus (Primitive roots modulo $n$ ), and it is a unit exactly when its representative is coprime to the modulus (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

[L2]

The order of an element of a finite group divides the group order (The order of every element of a finite group divides the order of the group), and $φ (p^{2}) = p (p - 1)$ (For a prime $p$ and $k \geq 1$ , $φ (p^{k}) = p^{k} - p^{k - 1}$ ).

[L3]

If an element has finite order $r$ , a power is the identity exactly when its exponent is divisible by $r$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L4]

Group powers satisfy the usual addition and iteration laws (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute).

[L5]

Congruence modulo $p^{2}$ means divisibility of the difference by $p^{2}$ (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ).

[L6]

Mathematical induction holds on $N$ (The principle of mathematical induction).

Proof

technique · cases

1.1givenL1L2L3algebra

Both $g$ and $g + p$ are units modulo $p^{2}$ by [L1] and reduce to the same primitive root modulo $p$ . If either has order $r$ modulo $p^{2}$ , reduction modulo $p$ makes its $r$ th power $1$ , so $p - 1 ∣ r$ by [L1] and [L3]. By [L2], $r$ also divides $p (p - 1)$ , and hence $r$ is either $p - 1$ or $p (p - 1)$ .

1.2L4L5L6

For every $r \geq 1$ , induction using the product law gives $(g + p)^{r} \equiv g^{r} + r p g^{r - 1} (m o d p^{2})$ .

2.1assume-case firststep 1.1

Assume first that $g^{p - 1} \equiv̸ 1 (m o d p^{2})$ . Then step 1.1 excludes order $p - 1$ , so $g$ has order $p (p - 1)$ and is primitive modulo $p^{2}$ .

2.2assume-case secondstep 1.1step 1.2L1L5

Assume instead that $g^{p - 1} \equiv 1 (m o d p^{2})$ . Step 1.2 gives $(g + p)^{p - 1} \equiv 1 + p (p - 1) g^{p - 2} (m o d p^{2})$ ; the second term is not divisible by $p^{2}$ , since neither $p - 1$ nor $g$ is divisible by $p$ . Thus $(g + p)^{p - 1} \equiv̸ 1 (m o d p^{2})$ , and step 1.1 makes $g + p$ primitive.

3.1step 2.1step 2.2cases-exhaustive∎

The two cases are exhaustive, and in each one of the two representatives is primitive modulo $p^{2}$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

For odd prime $p$ and $s \geq 1$ , $(1 + p^{s} u)^{p} \equiv 1 + p^{s + 1} u (m o d p^{s + 2})$

Statement

If $p$ is an odd prime, $s \geq 1$ , and $u \in Z$ , then

$(1 + p^{s} u)^{p} \equiv 1 + p^{s + 1} u (m o d p^{s + 2}) .$

Facts & Assumptions

Given: An odd prime $p$ , an integer $s \geq 1$ , and $u \in Z$ .

[L1]

Binomial coefficients count subsets and have their usual boundary values (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

[L2]

Pascal's rule holds for binomial coefficients (Pascal's rule $(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n}{k + 1})$ , and the hockey-stick identity $\sum_{i \leq n} (\binom{i}{k}) = (\binom{n + 1}{k + 1})$ ), and the closed factorial formula holds when the lower index does not exceed the upper one ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ ).

[L3]

If a prime divides a product, it divides one factor (Euclid's lemma: if $p$ is prime and $p ∣ a b$ then $p ∣ a$ or $p ∣ b$ ); a divisor coprime to one factor may be cancelled from a divisibility relation (If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ ).

[L4]

Congruence modulo an integer is divisibility of the difference (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ).

[L5]

Mathematical induction holds on $N$ (The principle of mathematical induction).

Proof

technique · direct

1.1L1L2L5

Induction on the exponent using [L2] gives the binomial expansion $(1 + z)^{p} = \sum_{r = 0}^{p} (\binom{p}{r}) z^{r}$ in $Z$ .

1.2L2L3algebra

For $1 \leq r < p$ , the identity $r (\binom{p}{r}) = p (\binom{p - 1}{r - 1})$ follows from [L2]. Since $p ∤ r$ , [L3] implies $p ∣ (\binom{p}{r})$ .

2.1step 1.1step 1.2algebra

Substitute $z = p^{s} u$ in step 1.1. For $2 \leq r < p$ , step 1.2 makes the $r$ th term divisible by $p^{1 + s r}$ , hence by $p^{s + 2}$ ; the final term is divisible by $p^{s p}$ , and $s p \geq s + 2$ because $p \geq 3$ and $s \geq 1$ .

3.1step 2.1L4∎

Modulo $p^{s + 2}$ only the constant and linear terms remain, namely $1 + p \cdot p^{s} u = 1 + p^{s + 1} u$ , which is the asserted congruence by [L4].

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

For odd prime $p$ , $p ∤ u$ , and $k \geq 1$ , the class of $1 + p u$ has order $p^{k - 1}$ modulo $p^{k}$

Statement

Let $p$ be an odd prime and $u \in Z$ with $p ∤ u$ . For every $k \geq 1$ , the class of $1 + p u$ in $(Z / p^{k})^{\times}$ has order $p^{k - 1}$ .

Facts & Assumptions

Given: An odd prime $p$ , an integer $u$ not divisible by $p$ , and $k \geq 1$ .

[L1]

The units modulo a positive modulus form a finite group (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ), and a class is a unit exactly when its representative is coprime to the modulus (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

[L2]

If $p ∤ v$ and $s \geq 1$ , then $(1 + p^{s} v)^{p} \equiv 1 + p^{s + 1} v (m o d p^{s + 2})$ (For odd prime $p$ and $s \geq 1$ , $(1 + p^{s} u)^{p} \equiv 1 + p^{s + 1} u (m o d p^{s + 2})$ ).

[L3]

Group powers satisfy $(x^{r})^{s} = x^{r s}$ (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute).

[L4]

$v_{p} (a) = j$ means $p^{j} ∣ a$ but $p^{j + 1} ∤ a$ (For a prime $p$ and a nonzero integer $a$ : $p^{v_{p} (a)} ∣ a$ and $p^{v_{p} (a) + 1} ∤ a$ ; $p^{k} ∣ a$ holds exactly for $k \leq v_{p} (a)$ ; $v_{p} (a) \geq 1$ exactly when $p ∣ a$ ; $v_{p} (1) = v_{p} (- 1) = 0$ ; and $v_{p} (p) = 1$ ), and valuations add on nonzero products ( $v_{p} (a b) = v_{p} (a) + v_{p} (b)$ for nonzero integers $a, b$ , and $v_{p} (a + b) \geq \min {v_{p} (a), v_{p} (b)}$ whenever $a$ , $b$ and $a + b$ are all nonzero).

[L5]

Mathematical induction holds on $N$ (The principle of mathematical induction).

[L6]

If an element has finite order $r$ , its $m$ th power is the identity exactly when $r ∣ m$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

Proof

technique · induction

1.1basegivenL4

For $j = 0$ , $(1 + p u)^{p^{0}} - 1 = p u$ has valuation $1$ .

1.2ihL2L3L4

Assume $(1 + p u)^{p^{j}} = 1 + p^{j + 1} v$ with $p ∤ v$ . Applying [L2] with $s = j + 1$ and using [L3] gives $(1 + p u)^{p^{j + 1}} = 1 + p^{j + 2} v^{'}$ with $p ∤ v^{'}$ .

1.3givenL1algebra

Any common prime divisor of $1 + p u$ and $p^{k}$ would be $p$ , but $1 + p u \equiv 1 (m o d p)$ . Thus $1 + p u$ is coprime to $p^{k}$ , so [L1] places its class in $(Z / p^{k})^{\times}$ .

2.1step 1.1step 1.2L5

By induction, $v_{p} ((1 + p u)^{p^{j}} - 1) = j + 1$ for every $j \geq 0$ .

3.1step 1.3step 2.1L4L6discharge-induction∎

By step 1.3 the order is defined in the finite unit group. Step 2.1 at $j = k - 1$ and [L6] show that it divides $p^{k - 1}$ . If it were a proper divisor of this prime power, it would divide $p^{k - 2}$ when $k \geq 2$ , so [L6] would make the $p^{k - 2}$ nd power equal to $1$ , contradicting step 2.1 at $j = k - 2$ ; for $k = 1$ the class is already the identity and has order $1$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

For every odd prime $p$ and $k \geq 1$ , $(Z / p^{k} Z)^{\times}$ is cyclic of order $p^{k - 1} (p - 1)$

Statement

For every odd prime $p$ and integer $k \geq 1$ , the group $(Z / p^{k})^{\times}$ is cyclic of order

$φ (p^{k}) = p^{k - 1} (p - 1) .$

Facts & Assumptions

Given: An odd prime $p$ and an integer $k \geq 1$ .

[L1]

Every prime modulus admits a primitive root (Every prime modulus admits a primitive root), and from a primitive root modulo an odd prime $p$ , at least one of $g$ and $g + p$ is primitive modulo $p^{2}$ (For an odd prime $p$ and a primitive root $g$ modulo $p$ , at least one of $g$ and $g + p$ is primitive modulo $p^{2}$ ).

[L2]

If $p ∤ u$ , the class $1 + p u$ has order $p^{k - 1}$ modulo $p^{k}$ (For odd prime $p$ , $p ∤ u$ , and $k \geq 1$ , the class of $1 + p u$ has order $p^{k - 1}$ modulo $p^{k}$ ).

[L3]

$φ (p^{k}) = p^{k - 1} (p - 1)$ (For a prime $p$ and $k \geq 1$ , $φ (p^{k}) = p^{k} - p^{k - 1}$ ).

[L4]

For an element of finite order $r$ , $x^{t} = 1$ exactly when $r ∣ t$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L5]

The order of an element of a finite group divides the group order (The order of every element of a finite group divides the order of the group).

[L6]

If two coprime integers divide an integer, then their product divides it (If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ ).

Proof

technique · direct

1.1L1L4choosealgebra

Choose a primitive root modulo $p$ by [L1], and replace its integer representative by the lift supplied there so that it is primitive modulo $p^{2}$ . Reduction modulo $p$ gives $g^{p - 1} = 1 + p u$ for some integer $u$ , while primitivity modulo $p^{2}$ and [L4] show $p ∤ u$ .

2.1step 1.1L2L4

Reduction modulo $p$ shows that the order of $g$ modulo $p^{k}$ is divisible by $p - 1$ , while [L2] applied to step 1.1 shows that the order of $g^{p - 1}$ is $p^{k - 1}$ .

3.1step 2.1L3L5L6algebra

The cyclic subgroup generated by $g^{p - 1}$ lies in that generated by $g$ , so [L5] and step 2.1 make $p^{k - 1}$ divide the order of $g$ . That order is also divisible by $p - 1$ by step 2.1. These two divisors are coprime, so [L6] makes their product divide the order; conversely [L3] and [L5] make the order divide $p^{k - 1} (p - 1)$ . Therefore it equals that group order.

4.1step 3.1L3∎

Thus $g$ generates the entire unit group, proving cyclicity; when $k = 1$ the same argument reduces to the original primitive root modulo $p$ .

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

An odd prime power $p^{k}$ has exactly $φ (φ (p^{k}))$ primitive roots

Statement

If $p$ is an odd prime and $k \geq 1$ , then there are exactly $φ (φ (p^{k}))$ primitive roots modulo $p^{k}$ .

Facts & Assumptions

Given: An odd prime $p$ and $k \geq 1$ .

[L1]

$(Z / p^{k})^{\times}$ is cyclic of order $φ (p^{k})$ (For every odd prime $p$ and $k \geq 1$ , $(Z / p^{k} Z)^{\times}$ is cyclic of order $p^{k - 1} (p - 1)$ ).

[L2]

Primitive roots are exactly generators of the unit group (A unit is a primitive root modulo $n$ if and only if it generates $(Z / n Z)^{\times}$ ).

[L3]

A cyclic group of order $m$ has $φ (m)$ generators (The generators of a cyclic group of order $m$ are the $g^{a}$ with $\gcd (a, m) = 1$ , so there are $φ (m)$ of them).

Proof

technique · direct

1.1L1L2

By [L1] and [L2], the primitive roots modulo $p^{k}$ are the generators of a cyclic group of order $φ (p^{k})$ .

2.1step 1.1L3∎

Applying [L3] to step 1.1 gives $φ (φ (p^{k}))$ primitive roots.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

For $k \geq 3$ , the class of $5$ has order $2^{k - 2}$ modulo $2^{k}$

Statement

For every integer $k \geq 3$ , the residue class of $5$ has order $2^{k - 2}$ in $(Z / 2^{k})^{\times}$ .

Facts & Assumptions

Given: An integer $k \geq 3$ .

[L1]

The order is the least positive exponent giving the identity (The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity), and an element of order $r$ has $x^{t} = 1$ exactly when $r ∣ t$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L2]

Group powers satisfy $x^{r + s} = x^{r} x^{s}$ and $(x^{r})^{s} = x^{r s}$ (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute).

[L3]

$v_{2} (a) = j$ means $2^{j} ∣ a$ and $2^{j + 1} ∤ a$ (For a prime $p$ and a nonzero integer $a$ : $p^{v_{p} (a)} ∣ a$ and $p^{v_{p} (a) + 1} ∤ a$ ; $p^{k} ∣ a$ holds exactly for $k \leq v_{p} (a)$ ; $v_{p} (a) \geq 1$ exactly when $p ∣ a$ ; $v_{p} (1) = v_{p} (- 1) = 0$ ; and $v_{p} (p) = 1$ ), and valuations add on nonzero products ( $v_{p} (a b) = v_{p} (a) + v_{p} (b)$ for nonzero integers $a, b$ , and $v_{p} (a + b) \geq \min {v_{p} (a), v_{p} (b)}$ whenever $a$ , $b$ and $a + b$ are all nonzero).

[L4]

Mathematical induction holds on $N$ (The principle of mathematical induction).

[L5]

A residue class is a unit exactly when its representative is coprime to the modulus (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

Proof

technique · induction

1.1baseL3L5algebra

The odd integer $5$ is coprime to $2^{k}$ , so [L5] puts its class in the unit group. At $j = 0$ , $5^{2^{0}} - 1 = 4$ , so its $2$ -adic valuation is $2$ .

1.2ihL2L3

Assume $v_{2} (5^{2^{j}} - 1) = j + 2$ . Since $5^{2^{j}} \equiv 1 (m o d 4)$ , the factor $5^{2^{j}} + 1$ is congruent to $2$ modulo $4$ and has valuation $1$ . The factorisation $5^{2^{j + 1}} - 1 = (5^{2^{j}} - 1) (5^{2^{j}} + 1)$ and [L3] therefore give valuation $j + 3$ .

2.1step 1.1step 1.2L4

By induction, $v_{2} (5^{2^{j}} - 1) = j + 2$ for all $j \geq 0$ .

3.1step 2.1L3

Step 2.1 with $j = k - 2$ gives $5^{2^{k - 2}} \equiv 1 (m o d 2^{k})$ , while the case $j = k - 3$ gives $5^{2^{k - 3}} \equiv̸ 1 (m o d 2^{k})$ .

4.1step 1.1step 3.1L1discharge-induction∎

By [L1], the order divides $2^{k - 2}$ ; every proper divisor of this prime power divides $2^{k - 3}$ , which step 3.1 excludes. Hence the order is $2^{k - 2}$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

For $k \geq 3$ , $(Z / 2^{k} Z)^{\times} ≅ C_{2} \times C_{2^{k - 2}}$ , generated uniquely as $(- 1)^{ε} 5^{j}$

Statement

For every $k \geq 3$ ,

$(Z / 2^{k})^{\times} ≅ C_{2} \times C_{2^{k - 2}} .$

More precisely, every unit has a unique representation $(- 1)^{ε} 5^{j}$ with $ε \in {0, 1}$ and $j$ modulo $2^{k - 2}$ .

Facts & Assumptions

Given: An integer $k \geq 3$ .

[L1]

The class of $5$ has order $2^{k - 2}$ modulo $2^{k}$ (For $k \geq 3$ , the class of $5$ has order $2^{k - 2}$ modulo $2^{k}$ ).

[L2]

$φ (2^{k}) = 2^{k - 1}$ (For a prime $p$ and $k \geq 1$ , $φ (p^{k}) = p^{k} - p^{k - 1}$ ).

[L3]

A direct product of finite groups has the product of their orders (For finite groups $G$ and $H$ , $∣ G \times H ∣ = ∣ G ∣ ∣ H ∣$ ).

[L4]

The units modulo $2^{k}$ are the classes represented by odd integers (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

[L5]

Multiplication modulo $2^{k}$ is commutative and restricts to the unit group (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[L6]

A bijective group homomorphism is a group isomorphism (Group isomorphisms, automorphisms and the set $Aut (G)$ ).

Proof

technique · direct

1.1L1algebra

The class of $- 1$ has order $2$ , and [L1] gives order $2^{k - 2}$ for $5$ .

1.2algebra

Every power of $5$ is $1$ modulo $4$ , whereas $- 1$ is $3$ modulo $4$ ; hence $⟨ - 1 ⟩ \cap ⟨ 5 ⟩ = {1}$ .

2.1step 1.1step 1.2L4L5

The map $C_{2} \times C_{2^{k - 2}} \to (Z / 2^{k})^{\times}$ given by $(ε, j) \mapsto (- 1)^{ε} 5^{j}$ is a homomorphism by [L5], and step 1.2 makes it injective.

3.1step 2.1L2L3

Its domain has $2^{k - 1}$ elements by [L3], equal to the size of the target by [L2]; thus it is bijective.

4.1step 3.1L6∎

By [L6] the map is an isomorphism, and its bijectivity is exactly the asserted unique representation.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

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

Statement

Let $n_{0}, \dots, n_{r - 1}$ be pairwise coprime positive integers and $N = \prod_{i < r} n_{i}$ . The Chinese remainder map restricts to a group isomorphism

$(Z / N)^{\times} ≅ \prod_{i < r} (Z / n_{i})^{\times} .$

For the empty list this identifies the two one-element groups.

Facts & Assumptions

Given: The stated finite pairwise-coprime list and its product $N$ .

[L1]

The Chinese remainder map $Z / N \to \prod_{i < r} Z / n_{i}$ is a bijection preserving multiplication and identity, including for the empty list (Chinese remainder theorem for a finite pairwise-coprime list: simultaneous residues determine one class modulo the product, and the resulting bijection preserves addition and multiplication).

[L2]

For $n \geq 1$ , the invertible classes of $Z / n$ form a group $(Z / n)^{\times}$ under multiplication (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[L3]

A bijective group homomorphism is an isomorphism (Group isomorphisms, automorphisms and the set $Aut (G)$ ).

Proof

technique · direct

1.1L1L2

By [L1], the CRT map preserves multiplication and identity. If a class has an inverse, its image has the coordinatewise image of that inverse.

1.2L1L2choose

Conversely, if every coordinate is a unit, take the tuple of coordinatewise inverses and use surjectivity in [L1] to lift it; multiplicativity shows that the lift is an inverse of the original class.

2.1step 1.1step 1.2L1L2

Steps 1.1 and 1.2 show that [L1] restricts to a bijective homomorphism between the displayed unit groups.

3.1step 2.1L1L3∎

It is therefore an isomorphism by [L3], and [L1] supplies the empty-list case.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

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

Statement

Let $n \geq 1$ have prime-power factorisation $n = 2^{a} \prod_{i < r} p_{i}^{k_{i}}$ , where the $p_{i}$ are distinct odd primes and $k_{i} \geq 1$ . Then

$(Z / n)^{\times} ≅ U_{2, a} \times \prod_{i < r} C_{p_{i}^{k_{i} - 1} (p_{i} - 1)},$

where $U_{2, 0}$ and $U_{2, 1}$ are trivial, $U_{2, 2} = C_{2}$ , and

$U_{2, a} = C_{2} \times C_{2^{a - 2}} (a \geq 3) .$

For $n = 1$ the product is empty and hence trivial.

Facts & Assumptions

Given: A positive integer $n$ and its displayed prime-power factorisation.

[L1]

CRT gives an isomorphism from a unit group to the product of the unit groups of pairwise coprime factors (For pairwise coprime positive moduli, the Chinese remainder bijection restricts to an isomorphism of unit groups).

[L2]

For odd $p$ , $(Z / p^{k})^{\times}$ is cyclic of order $p^{k - 1} (p - 1)$ (For every odd prime $p$ and $k \geq 1$ , $(Z / p^{k} Z)^{\times}$ is cyclic of order $p^{k - 1} (p - 1)$ ).

[L3]

For $a \geq 3$ , $(Z / 2^{a})^{\times} ≅ C_{2} \times C_{2^{a - 2}}$ (For $k \geq 3$ , $(Z / 2^{k} Z)^{\times} ≅ C_{2} \times C_{2^{k - 2}}$ , generated uniquely as $(- 1)^{ε} 5^{j}$ ).

[L4]

Given an injective list of primes containing every prime divisor of $n \geq 1$ , one has $n = \prod_{i} p_{i}^{v_{p_{i}} (n)}$ , the exponents being determined by $n$ (For $n \geq 1$ and any injective list $p : r \to Z$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i < r} p_{i}^{v_{p_{i}} (n)}$ ; the exponents are determined by $n$ , and $v_{q} (n) = 0$ for every prime $q$ outside the list). The Given of this theorem supplies exactly such a list, namely the primes of the displayed factorisation.

[L5]

$φ (2) = 1$ and $φ (4) = 2$ by the prime-power formula (For a prime $p$ and $k \geq 1$ , $φ (p^{k}) = p^{k} - p^{k - 1}$ ).

[L7]

The totient is the cardinality of the unit group: $φ (n) = ∣ (Z / n)^{\times} ∣$ (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[L6]

Every group of prime order is cyclic (A finite group of prime order is cyclic and every nonidentity element generates it).

Proof

technique · direct

1.1L4L1

By [L4], the displayed factors are pairwise coprime, so [L1] decomposes the unit group into its $2$ -power factor and the odd-prime-power factors.

2.1step 1.1L2L3

Substitute [L2] for every odd factor and [L3] for the $2$ -power factor when $a \geq 3$ .

2.2step 1.1L5L6L7

If $a = 0$ there is no $2$ -factor. If $a = 1$ , then [L5] gives $φ (2) = 1$ and [L7] reads that as $∣ (Z / 2)^{\times} ∣ = 1$ , so the unit group is trivial. If $a = 2$ , then [L5] and [L7] give $∣ (Z / 4)^{\times} ∣ = 2$ , prime order, so [L6] makes it cyclic.

3.1step 2.1step 2.2L1∎

Steps 2.1 and 2.2 give the asserted decomposition. When $n = 1$ , [L1] identifies the empty product with the one-element unit group.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Carmichael's function $λ (n)$ as the exponent of $(Z / n Z)^{\times}$

Definition

For $n \geq 1$ , Carmichael's function is the exponent of the finite unit group:

$λ (n) : = \exp ((Z / n)^{\times}) .$

The unit group is finite by The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ , and its exponent exists by The exponent of a finite group. In particular $λ (1) = 1$ , since the unit group modulo $1$ is trivial.

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

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

Statement

For every $n \geq 1$ there is a unit modulo $n$ of order $λ (n)$ , and every unit has order dividing $λ (n)$ . Thus $λ (n)$ is the maximum element order in $(Z / n)^{\times}$ .

Facts & Assumptions

Given: A positive integer $n$ .

[L1]

$λ (n)$ is the exponent of the unit group (Carmichael's function $λ (n)$ as the exponent of $(Z / n Z)^{\times}$ ).

[L2]

The unit group is a finite direct product of cyclic groups with the explicit $2$ -power factors described in The unit group modulo $n$ is the product of its odd-prime cyclic factors and its explicit $2$ -power factor.

[L3]

An element of order $r$ is killed precisely by the multiples of $r$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L4]

For $a, b \in Z$ both nonzero, $lcm (a, b)$ is the least positive common multiple of $a$ and $b$ ; if $a = 0$ or $b = 0$ then the only common multiple is $0$ and $lcm (a, b) = 0$ . It is defined for two arguments only (Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ).

[L5]

Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ (Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ ).

[L6]

If $g$ and $h$ have finite orders $m, n \geq 1$ , then $ord (g, h) = lcm (m, n)$ in the external direct product (If $g$ and $h$ have finite orders $m$ and $n$ , then $ι (ord (g, h)) = lcm (ι (m), ι (n))$ in $G \times H$ ).

Proof

technique · direct

1.1L2choose

In the decomposition [L2], choose a generator in every cyclic factor, including generators of both cyclic factors in the exceptional $2$ -power component.

1.2L1L2L3L4L5algebra

Let $r_{0}, \dots, r_{k - 1}$ be the orders of the chosen generators and define the iterated least common multiple from the binary operation of [L4] by $ℓ_{0} = 1$ and $ℓ_{s + 1} = lcm (ℓ_{s}, r_{s})$ ; [L4] supplies only the binary operation, so this recursion is what gives the list value. Induction on $s$ shows a positive $m$ satisfies $ℓ_{s} ∣ m$ exactly when $r_{i} ∣ m$ for every $i < s$ : at $s = 0$ both sides always hold, and $ℓ_{s + 1} ∣ m$ holds exactly when $ℓ_{s} ∣ m$ and $r_{s} ∣ m$ , by [L5] one way and because both divide $ℓ_{s + 1}$ the other. By [L3] a power kills the product exactly when it is divisible by every $r_{i}$ , so the exponent of the product is $ℓ_{k}$ .

2.1step 1.1step 1.2L3L4L6

The tuple of chosen generators has order $ℓ_{k}$ : iterating [L6] over the $k$ factors gives $ord$ of the tuple as the same iterated least common multiple, with the empty product contributing the identity of order $ℓ_{0} = 1$ .

3.1step 2.1step 1.2L1L2∎

Steps 2.1 and 1.2 produce a unit of order $λ (n)$ , while [L1] makes every element order divide $λ (n)$ . The empty product at $n = 1$ gives the identity of order $1$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

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

Statement

Carmichael's function satisfies $λ (1) = 1$ , and for prime powers,

$λ (p^{k}) = p^{k - 1} (p - 1) (p odd, k \geq 1),$

$λ (2) = 1, λ (4) = 2, λ (2^{k}) = 2^{k - 2} (k \geq 3) .$

If $n = \prod_{i < r} q_{i}^{e_{i}}$ is its prime-power factorisation, then

$λ (n) = {lcm}_{i < r} λ (q_{i}^{e_{i}}) .$

Here $lcm$ of a finite list is the iterated binary least common multiple of Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ , which defines that operation for two arguments only: set ${lcm}_{i < 0} a_{i} : = 1$ and ${lcm}_{i < s + 1} a_{i} : = lcm ({lcm}_{i < s} a_{i}, a_{s})$ . In particular the empty least common multiple is $1$ , which is the value taken at $n = 1$ .

Facts & Assumptions

Given: A positive integer $n$ and its prime-power factorisation.

[L1]

$λ (n)$ is the exponent of the unit group (Carmichael's function $λ (n)$ as the exponent of $(Z / n Z)^{\times}$ ).

[L2]

The structure theorem gives every prime-power factor of the unit group explicitly (The unit group modulo $n$ is the product of its odd-prime cyclic factors and its explicit $2$ -power factor).

[L3]

An exponent kills an element precisely when it is divisible by that element's order (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[L4]

[L5]

Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ (Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ ).

Proof

technique · direct

1.1L1L2L3

Reading the exponents of the cyclic factors in [L2] gives the displayed odd-prime and $2$ -power formulas, as well as $λ (1) = 1$ .

1.2L1L3L4L5algebra

Let $a_{0}, \dots, a_{r - 1}$ be the factor exponents and $ℓ_{s} = {lcm}_{i < s} a_{i}$ as defined in the Statement from the binary operation of [L4]. Induction on $s$ shows that a positive integer $m$ satisfies $ℓ_{s} ∣ m$ exactly when $a_{i} ∣ m$ for every $i < s$ : at $s = 0$ both sides hold always, since $ℓ_{0} = 1$ and the condition is vacuous; and $ℓ_{s + 1} = lcm (ℓ_{s}, a_{s})$ divides $m$ exactly when $ℓ_{s} ∣ m$ and $a_{s} ∣ m$ , by [L5] for one direction and because $ℓ_{s}$ and $a_{s}$ both divide $ℓ_{s + 1}$ for the other. In a finite direct product a power kills every tuple exactly when it is divisible by the exponent of each factor, by [L1] and [L3]; so the least such positive power is $ℓ_{r}$ .

2.1step 1.2L2∎

Apply step 1.2 to the CRT decomposition in [L2] to obtain the formula for general $n$ , including the empty product at $n = 1$ .

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

If $\gcd (a, n) = 1$ , then $a^{λ (n)} \equiv 1 (m o d n)$

Statement

If $n \geq 1$ and $\gcd (a, n) = 1$ , then

$a^{λ (n)} \equiv 1 (m o d n) .$

Facts & Assumptions

Given: Integers $n \geq 1$ and $a$ with $\gcd (a, n) = 1$ .

[L1]

$λ (n)$ is the exponent of $(Z / n)^{\times}$ (Carmichael's function $λ (n)$ as the exponent of $(Z / n Z)^{\times}$ ).

[L2]

The class of $a$ is a unit exactly when $\gcd (a, n) = 1$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

[L3]

Every element of a finite group raised to its exponent is the identity (The exponent of a finite group).

Proof

technique · direct

1.1L2

By [L2], the class of $a$ lies in the unit group modulo $n$ .

2.1step 1.1L1L3∎

By [L1] and [L3], its $λ (n)$ th power is the identity class, which is the asserted congruence. For $n = 1$ , both sides are the unique class and $λ (1) = 1$ .

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

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

Statement

If $n \geq 1$ is odd, then $n$ admits a primitive root if and only if $2 n$ admits a primitive root.

Facts & Assumptions

Given: An odd positive integer $n$ .

[L1]

CRT restricts to an isomorphism of unit groups for coprime positive moduli (For pairwise coprime positive moduli, the Chinese remainder bijection restricts to an isomorphism of unit groups).

[L2]

A modulus admits a primitive root exactly when its unit group is cyclic (A unit is a primitive root modulo $n$ if and only if it generates $(Z / n Z)^{\times}$ ).

[L3]

For a prime $p$ , $φ (p) = p - 1$ ; in particular $φ (2) = 1$ ( $φ (1) = 1$ , and $φ (p) = p - 1$ for every prime $p$ ).

[L4]

The totient is the cardinality of the unit group: $φ (n) = ∣ (Z / n)^{\times} ∣$ (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

Proof

technique · direct

1.1L1

Since $n$ is odd, [L1] gives $(Z / 2 n)^{\times} ≅ (Z / 2)^{\times} \times (Z / n)^{\times}$ .

1.2L3L4algebra

By [L3], $φ (2) = 1$ , and by [L4] that number is $∣ (Z / 2)^{\times} ∣$ , so the first factor is trivial and the right-hand side is isomorphic to $(Z / n)^{\times}$ .

2.1step 1.1step 1.2L2∎

Therefore the two unit groups are cyclic simultaneously, and [L2] converts this into the asserted equivalence of primitive-root existence.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

A positive integer admits a primitive root exactly when it is $1$ , $2$ , $4$ , $p^{k}$ , or $2 p^{k}$ for an odd prime $p$

Statement

A positive integer $n$ admits a primitive root if and only if

$n \in {1, 2, 4, p^{k}, 2 p^{k}},$

where $p$ is an odd prime and $k \geq 1$ .

Facts & Assumptions

Given: A positive integer $n$ .

[L1]

A primitive root exists exactly when the unit group is cyclic (A unit is a primitive root modulo $n$ if and only if it generates $(Z / n Z)^{\times}$ ).

[L2]

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

[L3]

A product of finite cyclic groups is cyclic exactly when the factor orders are pairwise coprime, by repeated use of A direct product of two finite cyclic groups is cyclic if and only if their orders are coprime.

[L4]

Primitive-root existence is equivalent for odd $n$ and $2 n$ (For odd $n$ , primitive-root existence is equivalent for $n$ and $2 n$ ).

Proof

technique · direct

1.1L2L4

The unit groups for $1$ and $2$ are trivial, that for $4$ is $C_{2}$ , and [L2] makes the unit group for every odd prime power cyclic. By [L4], every twice-odd-prime-power also has a cyclic unit group.

1.2L2L3

Conversely, write $n = 2^{a} \prod p_{i}^{k_{i}}$ . If $a \geq 3$ , [L2] contains cyclic factors of orders $2$ and $2^{a - 2}$ , which are not coprime, so [L3] makes the unit group noncyclic. If $a = 2$ and an odd factor is present, the factor $C_{2}$ and the even-order odd-prime factor are likewise not coprime.

1.3L2L3

If two distinct odd-prime factors are present, both cyclic factor orders are even, so [L3] again makes the product noncyclic. Thus cyclicity leaves only $1, 2, 4, p^{k}$ , and $2 p^{k}$ .

2.1step 1.1L1

By [L1], all moduli in the displayed list admit primitive roots.

3.1step 2.1step 1.2step 1.3L1∎

Combining steps 2.1 and 1.3 with [L1] proves both directions, including the convention at $n = 1$ .

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

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

Statement

If $n \geq 1$ admits a primitive root, then it has exactly $φ (φ (n))$ primitive roots.

Facts & Assumptions

Given: A positive modulus $n$ admitting a primitive root.

[L1]

Primitive roots are exactly generators of the unit group (A unit is a primitive root modulo $n$ if and only if it generates $(Z / n Z)^{\times}$ ).

[L2]

A cyclic group of order $m$ has $φ (m)$ generators (The generators of a cyclic group of order $m$ are the $g^{a}$ with $\gcd (a, m) = 1$ , so there are $φ (m)$ of them).

Proof

technique · direct

1.1givenL1

By the Given and [L1], the unit group is cyclic of order $φ (n)$ , and its generators are exactly the primitive roots.

2.1step 1.1L2∎

Applying [L2] with $m = φ (n)$ yields $φ (φ (n))$ primitive roots. At $n = 1$ this is $φ (1) = 1$ , counting the unique class.

5 · Examples, counterexamples and false statements

None yet.

Primitive Roots and Unit Groups Modulo N

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Primitive roots modulo nn

Definition

A unit is a primitive root modulo nn if and only if it generates (Z/nZ)×(Z/nZ)×

Statement

Facts & Assumptions

Proof

The index ind⁡g(a)indg​(a) of a unit relative to a primitive root

Definition

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

Statement

Facts & Assumptions

Proof

In a cyclic group of order mm, gaga has order m/gcd⁡(a,m)m/gcd(a,m)

Statement

Facts & Assumptions

Proof

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

Statement

Facts & Assumptions

Proof

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

Statement

Facts & Assumptions

Proof

For every prime pp, the multiplicative group (Z/pZ)×(Z/pZ)× is cyclic

Statement

Facts & Assumptions

Proof

Every prime modulus admits a primitive root

Statement

Facts & Assumptions

Proof

For prime pp and d≥1d≥1, the congruence xd≡1(modp)xd≡1(modp) has gcd⁡(d,p−1)gcd(d,p−1) nonzero solutions

Statement

Facts & Assumptions

Proof

Euler's criterion: if nn has a primitive root, gcd⁡(a,n)=1gcd(a,n)=1, and m≥1m≥1, then xm≡a(modn)xm≡a(modn) is solvable if and only if aφ(n)/gcd⁡(φ(n),m)≡1(modn)aφ(n)/gcd(φ(n),m)≡1(modn)

Statement

Facts & Assumptions

Proof

If nn has a primitive root, gcd⁡(a,n)=1gcd(a,n)=1, m≥1m≥1, and xm≡a(modn)xm≡a(modn) is solvable, then it has exactly gcd⁡(φ(n),m)gcd(φ(n),m) solution classes modulo nn

Statement

Facts & Assumptions

Proof

For an odd prime pp and a primitive root gg modulo pp, at least one of gg and g+pg+p is primitive modulo p2p2

Statement

Facts & Assumptions

Proof

For odd prime pp and s≥1s≥1, (1+psu)p≡1+ps+1u(modps+2)(1+psu)p≡1+ps+1u(modps+2)

Statement

Facts & Assumptions

Proof

For odd prime pp, p∤up∤u, and k≥1k≥1, the class of 1+pu1+pu has order pk−1pk−1 modulo pkpk

Statement

Facts & Assumptions

Proof

For every odd prime pp and k≥1k≥1, (Z/pkZ)×(Z/pkZ)× is cyclic of order pk−1(p−1)pk−1(p−1)

Statement

Facts & Assumptions

Proof

An odd prime power pkpk has exactly φ(φ(pk))φ(φ(pk)) primitive roots

Statement

Facts & Assumptions

Proof

For k≥3k≥3, the class of 55 has order 2k−22k−2 modulo 2k2k

Statement

Facts & Assumptions

Proof

For k≥3k≥3, (Z/2kZ)×≅C2×C2k−2(Z/2kZ)×≅C2​×C2k−2​, generated uniquely as (−1)ε5j(−1)ε5j

Statement

Facts & Assumptions

Proof

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

Statement

Facts & Assumptions

Primitive roots modulo $n$

A unit is a primitive root modulo $n$ if and only if it generates $(Z / n Z)^{\times}$

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^{a}$ has order $m / \gcd (a, m)$

The generators of a cyclic group of order $m$ are the $g^{a}$ with $\gcd (a, m) = 1$ , so there are $φ (m)$ of them

For every prime $p$ , the multiplicative group $(Z / p Z)^{\times}$ is cyclic

For prime $p$ and $d \geq 1$ , the congruence $x^{d} \equiv 1 (m o d p)$ has $\gcd (d, p - 1)$ nonzero solutions

Euler's criterion: if $n$ has a primitive root, $\gcd (a, n) = 1$ , and $m \geq 1$ , then $x^{m} \equiv a (m o d n)$ is solvable if and only if $a^{φ (n) / \gcd (φ (n), m)} \equiv 1 (m o d n)$

If $n$ has a primitive root, $\gcd (a, n) = 1$ , $m \geq 1$ , and $x^{m} \equiv a (m o d 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^{2}$

For odd prime $p$ and $s \geq 1$ , $(1 + p^{s} u)^{p} \equiv 1 + p^{s + 1} u (m o d p^{s + 2})$

For odd prime $p$ , $p ∤ u$ , and $k \geq 1$ , the class of $1 + p u$ has order $p^{k - 1}$ modulo $p^{k}$

For every odd prime $p$ and $k \geq 1$ , $(Z / p^{k} Z)^{\times}$ is cyclic of order $p^{k - 1} (p - 1)$

An odd prime power $p^{k}$ has exactly $φ (φ (p^{k}))$ primitive roots

For $k \geq 3$ , the class of $5$ has order $2^{k - 2}$ modulo $2^{k}$

For $k \geq 3$ , $(Z / 2^{k} Z)^{\times} ≅ C_{2} \times C_{2^{k - 2}}$ , generated uniquely as $(- 1)^{ε} 5^{j}$

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 $(Z / n Z)^{\times}$

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

If $\gcd (a, n) = 1$ , then $a^{λ (n)} \equiv 1 (m o d n)$

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

A positive integer admits a primitive root exactly when it is $1$ , $2$ , $4$ , $p^{k}$ , or $2 p^{k}$ for an odd prime $p$

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