ExampleConstruction: AI-adaptedVerification: AI-generatedSession-authored (Fable 5 assisted)precheck passverified 2026-08-02 (claude-opus-5)

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.

For $n \ge 1$ the congruence classes modulo $n$ form an abelian group $(\mathbb{Z}/n, +)$ of order $n$ , generated by the class of $1$

Example

Fix a natural number $n \ge 1$ and write $\bar n := \iota(n)$ for the corresponding positive integer, $\iota : \mathbb{N} \to \mathbb{Z}$ being the embedding of The naturals embed in the integers. For $a, b \in \mathbb{Z}$ define

$a \equiv b \pmod n \quad :\iff \quad a - b = q \bar n \ \text{ for some } q \in \mathbb{Z},$

that is, $\bar n \mid (a - b)$ (Division with remainder in $\mathbb{Z}$ : for $a \in \mathbb{Z}$ and $b > 0$ there are unique $q, r \in \mathbb{Z}$ with $a = qb + r$ and $0 \le r < b$ ). Then:

$\equiv$ is an equivalence relation on $\mathbb{Z}$ (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ); its classes are the congruence classes modulo $n$ , and the quotient set is written $\mathbb{Z}/n$ ;
$[a] + [b] := [a+b]$ is a well-defined binary operation on $\mathbb{Z}/n$ , and $(\mathbb{Z}/n, +, [0])$ is an abelian group (Group and abelian group);
$\mathbb{Z}/n$ is finite of order $n$ : $|\mathbb{Z}/n| = n$ (The order $|G|$ of a finite group and the order $\operatorname{ord}(g)$ of an element, with $\operatorname{ord}(g) = \infty$ when no positive power of $g$ is the identity);
$\mathbb{Z}/n = \langle [1] \rangle$ , so it is cyclic, generated by the class of $1$ (The subgroup $\langle S \rangle$ generated by a subset, the cyclic subgroup $\langle g \rangle$ , and cyclic groups).

The hypothesis $n \ge 1$ is needed for claim 3, and for claim 3 only: at $n = 0$ the relation is equality, so $\mathbb{Z}/0$ has one class for each integer and is infinite, and there is no natural number $n$ with $|\mathbb{Z}/0| = n$ . Claims 1, 2 and 4 do hold at $n = 0$ , where $\mathbb{Z}/0$ is an infinite cyclic group generated by $[1]$ .

Facts & Assumptions

Given: A natural number $n \ge 1$ , the integer $\bar n = \iota(n)$ , and the relation $a \equiv b$ meaning $a - b = q\bar n$ for some $q \in \mathbb{Z}$ (The integers as equivalence classes of pairs of naturals, Arithmetic on the integers).

[L1]

$\mathbb{Z}$ is a commutative ring, with $u - v := u + (-v)$ (The integers form a commutative ring, Arithmetic on the integers); its order is total and antisymmetric and compatible with addition, and positives are closed under multiplication (The integers form a totally ordered ring, Order on the integers).

[L2]

$\iota$ is injective, preserves addition, multiplication and order, and its image is exactly the nonnegative integers; $\iota(0) = 0$ , $\iota(1) = 1$ ; hence $\bar n > 0$ because $n \ge 1$ (The naturals embed in the integers, Order on the natural numbers, The natural numbers $\mathbb{N}$ (von Neumann)). Moreover $n = \{\, s \in \mathbb{N} : s < n \,\}$ : a natural number is exactly the set of the naturals below it (On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$ ).

[L3]

An equivalence relation is a reflexive, symmetric and transitive relation; $[a] = \{ b : a \sim b \}$ and the quotient set is the set of classes (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ); and $a \sim b$ if and only if $[a] = [b]$ (The equivalence classes of an equivalence relation are nonempty, cover $A$ , and are pairwise equal or disjoint; conversely every such cover arises from exactly one equivalence relation).

[L4]

Division with remainder: for $a \in \mathbb{Z}$ and $b > 0$ there are unique $q, r \in \mathbb{Z}$ with $a = qb + r$ and $0 \le r < b$ (Division with remainder in $\mathbb{Z}$ : for $a \in \mathbb{Z}$ and $b > 0$ there are unique $q, r \in \mathbb{Z}$ with $a = qb + r$ and $0 \le r < b$ ).

[L5]

A group is a monoid all of whose elements are invertible; abelian means commutative; the order $|G|$ of a finite group is the unique natural $m$ with $G \approx m$ ; $\langle g \rangle$ is the smallest subgroup containing $g$ and equals the set of integer powers of $g$ (Group and abelian group, Binary operation on a set; associativity, commutativity, and a subset closed under the operation, Left identity, right identity, and two-sided identity for a binary operation, The order $|G|$ of a finite group and the order $\operatorname{ord}(g)$ of an element, with $\operatorname{ord}(g) = \infty$ when no positive power of $g$ is the identity, The subgroup $\langle S \rangle$ generated by a subset, the cyclic subgroup $\langle g \rangle$ , and cyclic groups, $\langle g \rangle = \{\, g^{n} : n \in \mathbb{Z} \,\}$ , and every cyclic group is abelian, Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A \preceq B$ , Injection, surjection, bijection).

[L6]

Powers in a group written additively: $g^{0}$ is the identity, $g^{\sigma(m)} = g^{m} + g$ , and $g^{x} = -g^{k}$ when $x < 0$ and $-x = \iota(k)$ (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ).

[L7]

Induction on $\mathbb{N}$ (The principle of mathematical induction); on $\mathbb{N}$ exactly one of $s<t$ , $s=t$ , $t<s$ holds (Trichotomy of the order on $\mathbb{N}$ ).

Verification

technique · direct

1.1

$\equiv$ is reflexive, since $a - a = 0 = 0 \cdot \bar n$ ; symmetric, since $a - b = q\bar n$ gives $b - a = (-q)\bar n$ ; and transitive, since $a - b = q\bar n$ and $b - c = q'\bar n$ give $a - c = (a-b) + (b-c) = (q + q')\bar n$ . So it is an equivalence relation, and $\mathbb{Z}/n$ is its quotient set.

L1L3

1.2

The operation is well defined: if $a \equiv a'$ and $b \equiv b'$ , say $a - a' = q\bar n$ and $b - b' = q'\bar n$ , then $(a+b) - (a'+b') = (a - a') + (b - b') = (q+q')\bar n$ , so $a + b \equiv a' + b'$ and $[a+b] = [a'+b']$ . Hence $[a] + [b] := [a+b]$ depends only on the classes.

L1L3

1.3

$\iota$ reflects the order: if $\iota(s) < \iota(t)$ then $s < t$ , since otherwise $t \le s$ would give $\iota(t) \le \iota(s)$ , contradicting antisymmetry.

L1L2L7

1.4

Distinct such representatives give distinct classes: let $s, t \in \mathbb{N}$ with $s < n$ , $t < n$ and $[\iota(s)] = [\iota(t)]$ , so $\iota(s) - \iota(t) = q\bar n$ for some $q$ , that is $\iota(s) = q\bar n + \iota(t)$ . Both $\iota(s)$ and $\iota(t)$ are nonnegative and, $\iota$ preserving the order, both are $< \iota(n) = \bar n$ . So $\iota(s)$ is written as $q\bar n + \iota(t)$ with $0 \le \iota(t) < \bar n$ and also as $0 \cdot \bar n + \iota(s)$ with $0 \le \iota(s) < \bar n$ ; the uniqueness clause of division with remainder forces $q = 0$ and $\iota(t) = \iota(s)$ , whence $s = t$ by injectivity of $\iota$ .

L1L2L3L4

1.5

In the group $\mathbb{Z}/n$ the $k$ -th power of $[1]$ in additive notation is $[\iota(k)]$ for every $k \in \mathbb{N}$ : the set of $k$ for which this holds contains $0$ , since the identity is $[0] = [\iota(0)]$ , and is closed under $\sigma$ , since the power at $\sigma(k)$ is the power at $k$ plus $[1]$ , that is $[\iota(k)] + [1] = [\iota(k) + 1] = [\iota(\sigma(k))]$ .

L1L2L6L7

2.1

$(\mathbb{Z}/n, +, [0])$ is an abelian group: associativity, commutativity, the identity law $[a] + [0] = [a+0] = [a]$ and the inverse law $[a] + [-a] = [0]$ all follow from the corresponding identities in $\mathbb{Z}$ applied to representatives, which is legitimate by step 1.2.

step 1.2L1L5

2.2

Every class has a representative $r$ with $0 \le r < \bar n$ : given $a$ , divide $a = q\bar n + r$ with $0 \le r < \bar n$ , so $a - r = q\bar n$ and $[a] = [r]$ . Moreover $r \ge 0$ gives $r = \iota(s)$ for a unique $s \in \mathbb{N}$ , and $\iota(s) < \iota(n)$ gives $s < n$ .

step 1.3L2L3L4

3.1

The map $\varphi : n \to \mathbb{Z}/n$ with $\varphi(s) = [\iota(s)]$ is well defined, the elements of the natural number $n$ being exactly the naturals $s < n$ ; it is surjective by step 2.2 and injective by step 1.4, hence a bijection. So $\mathbb{Z}/n \approx n$ and $|\mathbb{Z}/n| = n$ .

step 2.2step 1.4L2L5

3.2

For a negative integer $x$ with $-x = \iota(k)$ , the $x$ -th power of $[1]$ is the inverse of $[\iota(k)]$ , namely $[-\iota(k)] = [x]$ ; with step 1.5 this gives that the set of integer powers of $[1]$ is $\{\, [a] : a \in \mathbb{Z} \,\} = \mathbb{Z}/n$ .

step 2.1step 1.5L1L2L6

4.1

Since $\langle [1] \rangle$ is exactly the set of integer powers of $[1]$ , step 3.2 gives $\langle [1] \rangle = \mathbb{Z}/n$ , so $\mathbb{Z}/n$ is cyclic, generated by $[1]$ .

step 3.2L5

5.1

Claims 1 to 4 are established in steps 1.1, 2.1, 3.1 and 4.1.

step 1.1step 2.1step 3.1step 4.1∎

Remarks

The hypothesis $n \ge 1$ is carried by the title and by the statement, not left implicit. It is used twice and in an essential way: $\bar n > 0$ is what makes Division with remainder in $\mathbb{Z}$ : for $a \in \mathbb{Z}$ and $b > 0$ there are unique $q, r \in \mathbb{Z}$ with $a = qb + r$ and $0 \le r < b$ applicable in step 2.2, and it is what makes the count in step 3.1 come out as $n$ . At $n = 0$ the relation $\equiv$ is equality on $\mathbb{Z}$ , the quotient set is in bijection with $\mathbb{Z}$ itself, and the group is infinite.
No greatest common divisor is used anywhere above, and none is available at this point in the reading order. Only division with remainder is needed. The multiplicative structure of $\mathbb{Z}/n$ , where the units are the classes coprime to $n$ , does need gcd theory and belongs to a later page.
The elements are congruence classes, that is subsets of $\mathbb{Z}$ , and $[a]$ is a set. Nothing above ever names an element of $\mathbb{Z}/n$ except through a representative, which is why step 1.2 has to be checked before the operation may be written down at all.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 90 results over 27 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

Modular arithmetic (Wikipedia) (standard reference, not scraped)
Cyclic group (Wikipedia) (standard reference, not scraped)

For n≥1n \ge 1n≥1 the congruence classes modulo nnn form an abelian group (Z/n,+)(\mathbb{Z}/n, +)(Z/n,+) of order nnn, generated by the class of 111