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

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.

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.

Depends on

Used by

Dependency tree · two levels

38 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

William Stein, Elementary Number Theory, Proposition 2.5.12 (standard reference, not scraped)

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