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

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.

A cyclic group of order $n$ has exactly $φ (n)$ generators

Statement

Let $G = ⟨ g ⟩$ be a cyclic group of finite order $n \geq 1$ (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups). For an integer $a$ ,

$⟨ g^{a} ⟩ = G ⟺ \gcd (a, n) = 1,$

that is, $g^{a}$ generates $G$ exactly when $a$ and $n$ are coprime (Coprime integers: $\gcd (a, b) = 1$ ). Consequently $G$ has exactly $φ (n)$ generators (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

At $n = 1$ the group is trivial, every integer is coprime to $1$ , and the single element is its own generator, in agreement with $φ (1) = 1$ .

Facts & Assumptions

Given: A cyclic group $G = ⟨ g ⟩$ whose underlying set is finite of order $n \geq 1$ .

[A1]

$∣ G ∣ = n$ , and since $G = ⟨ g ⟩$ , [L1] gives $ord (g) = ∣ ⟨ g ⟩ ∣ = n$ ; in particular $g^{n} = e$ .

[L1]

For an element $x$ of finite order $m$ in a group: $x^{k} = e$ if and only if $m ∣ k$ ; the powers $x^{0}, x^{1}, \dots, x^{m - 1}$ are pairwise distinct; and $⟨ x ⟩ = {x^{s} : s \in N, s < m}$ , so $∣ ⟨ x ⟩ ∣ = m = 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$ , 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]

$⟨ x ⟩ = {x^{k} : k \in Z}$ ( $⟨ g ⟩ = {g^{n} : n \in Z}$ , and every cyclic group is abelian); and $⟨ S ⟩$ is the smallest subgroup containing $S$ (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups).

[L3]

For $a, b \in Z$ not both $0$ there are integers $x_{0}, y_{0}$ with $a x_{0} + b y_{0} = \gcd (a, b)$ (Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution).

[L4]

$\gcd (a, b)$ is a common divisor of $a$ and $b$ , and $\gcd (a, b) \geq 1$ whenever $(a, b) \neq (0, 0)$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L5]

For $n \geq 1$ , every class in $Z / n$ contains exactly one integer $r$ with $0 \leq r < n$ , and $r \mapsto [r]_{n}$ is a bijection from ${0, \dots, n - 1}$ onto $Z / n$ (For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ ).

[L6]

For $n \geq 1$ and $a \in Z$ , the class $[a]_{n}$ is a unit of $Z / n$ if and only if $\gcd (a, n) = 1$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

[L7]

$φ (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.1L4given

Put $m : = \gcd (a, n)$ . Since $n \geq 1$ the pair $(a, n)$ is not $(0, 0)$ , so $m \geq 1$ , $m ∣ a$ and $m ∣ n$ by [L4].

2.1step 1.1A1L2L3

If $m = 1$ then $g^{a}$ generates $G$ : by [L3] there are integers $u, v$ with $a u + n v = 1$ , whence $g = g^{a u + n v} = (g^{a})^{u} (g^{n})^{v} = (g^{a})^{u}$ using $g^{n} = e$ from [A1]; so $g \in ⟨ g^{a} ⟩$ by [L2], and $⟨ g^{a} ⟩$ is then a subgroup containing $g$ , so it contains $⟨ g ⟩ = G$ by [L2] and equals $G$ .

2.2step 1.1A1L1algebra

Conversely, if $g^{a}$ generates $G$ then $m = 1$ : from $m ∣ a$ and $m ∣ n$ the integer $n / m$ is at least $1$ and $(g^{a})^{n / m} = (g^{n})^{a / m} = e$ by [A1], so $ord (g^{a}) \leq n / m$ and hence $∣ ⟨ g^{a} ⟩ ∣ \leq n / m$ by [L1]; but $⟨ g^{a} ⟩ = G$ has $n$ elements, so $n \leq n / m$ and therefore $m = 1$ .

3.1step 2.1step 2.2A1L1

By [A1] and [L1] the powers $g^{0}, g^{1}, \dots, g^{n - 1}$ are pairwise distinct and exhaust $G$ , so the generators of $G$ are exactly the elements $g^{r}$ with $0 \leq r < n$ and $\gcd (r, n) = 1$ , one for each such $r$ .

4.1step 3.1L5L6L7∎

By [L5] the map $r \mapsto [r]_{n}$ is a bijection from ${0, \dots, n - 1}$ onto $Z / n$ , and by [L6] it carries the $r$ with $\gcd (r, n) = 1$ onto the units of $Z / n$ ; so the number of such $r$ is $∣ (Z / n)^{\times} ∣ = φ (n)$ by [L7], and by step 3.1 that is the number of generators of $G$ .

Remarks

Why the criterion is stated and not only the count. The count answers "how many", but the development below repeatedly needs "which": that $ζ^{a}$ is again a primitive $n$ -th root of unity exactly when $a$ is coprime to $n$ is the criterion, and it is what makes the exponent of a cyclotomic automorphism a unit modulo $n$ ( $K (μ_{n}) / K$ is Galois and $σ \mapsto a_{σ}$ embeds its Galois group into $(Z / n)^{\times}$ ).

Depends on

Used by

Dependency tree · two levels

52 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

K. Conrad, Cyclotomic Extensions (expository blurb), Section 1 (standard reference, not scraped)
P. L. Clark, Field Theory (course notes/monograph), Chapter 9, Section 1 (standard reference, not scraped)

A cyclic group of order nn has exactly φ(n)φ(n) generators