CounterexampleConstruction: AI-adaptedVerification: AI-generatedSession-authored (Fable 5 assisted)precheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)

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.

In the multiplicative monoid $H = \{1, 4, 7, 10, \dots\}$ of positive integers one more than a multiple of $3$ , the element $100$ has two genuinely different factorisations into irreducibles, $4 \cdot 25$ and $10 \cdot 10$

Statement refuted

Refuted claim. Let $(M,\cdot,1)$ be a commutative monoid (Semigroup and monoid) whose underlying set consists of integers $\ge 1$ , contains $1$ , and is closed under the multiplication of $\mathbb{Z}$ (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). Call $h \in M$ with $h > 1$ irreducible in $M$ when there are no $u, v \in M$ with $u > 1$ , $v > 1$ and $h = uv$ . Then factorisation into irreducibles of $M$ is unique up to order: if

$\prod_{i<r} h_i \;=\; \prod_{j<s} h'_j$

with every $h_i$ and $h'_j$ irreducible in $M$ , then $r = s$ and $h'_i = h_{\pi(i)}$ for every $i < r$ , for some $\pi \in \operatorname{Sym}(r)$ (The symmetric group $\operatorname{Sym}(X)$ : the bijections of a set $X$ under composition, The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

Witness. Take

$H \;:=\; \{\, h \in \mathbb{Z} \;:\; h \ge 1 \ \text{ and } \ 3 \mid h - 1 \,\} \;=\; \{1, 4, 7, 10, 13, \dots\},$

with the multiplication of $\mathbb{Z}$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ). Then $4$ , $10$ and $25$ are irreducible in $H$ , and

$100 \;=\; 4 \cdot 25 \;=\; 10 \cdot 10 ,$

two lists of irreducibles of $H$ that no permutation matches, since $10 \ne 4$ and $10 \ne 25$ .

Numerals. For $k \in \mathbb{N}$ the symbol $k$ inside $\mathbb{Z}$ means $\iota(k)$ , the embedding of The naturals embed in the integers.

Facts & Assumptions

Given: The set $H$ above and the integers $4$ , $5$ , $10$ , $25$ , $100$ .

[L1]

A monoid is a set with an associative binary operation and a two-sided identity, and is commutative when the operation is (Semigroup and monoid, 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).

[L2]

$(\mathbb{Z},\cdot,1)$ is a commutative monoid ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ); $\mathbb{Z}$ is a commutative ring with $x \cdot 1 = x$ and distributivity (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L3]

$\prod_{i<0} g_i = e$ and $\prod_{i<\sigma(m)} g_i = \bigl(\prod_{i<m} g_i\bigr) g_m$ (The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

[L4]

$d \mid u$ means $u = dc$ for some $c \in \mathbb{Z}$ ; divisibility is reflexive and transitive and is linear (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ , Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ).

[L5]

For $a \in \mathbb{Z}$ and $b > 0$ there is exactly one pair $(q,r)$ with $a = qb + r$ and $0 \le r < b$ , and $b \mid a$ exactly when $r = 0$ (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$ ).

[L6]

If $d \mid a$ and $a \ne 0$ then $|d| \le |a|$ (If $d \mid a$ and $a \ne 0$ then $d \ne 0$ and $|d| \le |a|$ ; hence the set of divisors of a nonzero integer is bounded above by $|a|$ ).

[L7]

Every integer $> 1$ has a prime divisor (Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime); a prime $q$ satisfies $q > 1$ and has only $1$ and $q$ as positive divisors (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L8]

If $q$ is prime and $q \mid uv$ then $q \mid u$ or $q \mid v$ (Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$ ).

[L9]

A product of two nonzero integers is nonzero, and $xz = yz$ with $z \ne 0$ gives $x = y$ (The integers have no zero divisors; multiplicative cancellation).

[L10]

The order on $\mathbb{Z}$ is total, antisymmetric and transitive, is compatible with addition, and positives are closed under multiplication (The integers form a totally ordered ring, Order on the integers); $\iota$ is injective and order preserving with image the nonnegative integers (The naturals embed in the integers, The natural numbers $\mathbb{N}$ (von Neumann), Order on the natural numbers, Discreteness: $\sigma(n)$ is the immediate successor).

Counterexample

technique · direct

1.1

$0 < 1$ in $\mathbb{Z}$ , and every integer $y > 0$ satisfies $y \ge 1$ : $y = \iota(t)$ with $t \ne 0$ , so $1 \le y$ because $\iota$ preserves the order. Consequently $y > c$ implies $y \ge c+1$ .

L10

1.2

$H$ is a commutative monoid under the multiplication of $\mathbb{Z}$ . It contains $1$ , since $1 \ge 1$ and $1 - 1 = 0 = 3 \cdot 0$ . It is closed: if $h - 1 = 3a$ and $h' - 1 = 3b$ then $hh' - 1 = (3a+1)(3b+1) - 1 = 3(3ab + a + b)$ , so $3 \mid hh' - 1$ ; and $h, h' \ge 1$ give $hh' \ge 1$ . Associativity, commutativity and the identity are inherited from $\mathbb{Z}$ .

L1L2L4L10

1.3

$4$ , $10$ , $25$ and $100$ lie in $H$ : $4 - 1 = 3 = 3 \cdot 1$ , $10 - 1 = 9 = 3 \cdot 3$ , $25 - 1 = 24 = 3 \cdot 8$ and $100 - 1 = 99 = 3 \cdot 33$ , and all four exceed $1$ . And $5 \notin H$ : $5 - 1 = 4 = 1 \cdot 3 + 1$ , whose remainder $1$ is nonzero, so $3 \nmid 4$ by [L5].

L4L5algebra

2.1

Every $h \in H$ with $h > 1$ satisfies $h \ge 4$ . Indeed $h - 1 > 0$ and $h - 1 = 3t$ for some $t$ , so $t > 0$ and hence $t \ge 1$ by step 1.1, giving $h - 1 \ge 3$ and $h \ge 4$ .

step 1.1L4L10

2.2

$5$ is prime. It exceeds $1$ ; a positive divisor $d$ of $5$ satisfies $1 \le d \le 5$ by [L6] and step 1.1, and the intermediate candidates are ruled out by their remainders: $5 = 2 \cdot 2 + 1$ , $5 = 1 \cdot 3 + 2$ and $5 = 1 \cdot 4 + 1$ . So the only positive divisors are $1$ and $5$ .

step 1.1L5L6L7algebra

3.1

$4$ and $10$ are irreducible in $H$ . If $4 = uv$ or $10 = uv$ with $u, v \in H$ both $> 1$ , then $u \ge 4$ and $v \ge 4$ by step 2.1, so $uv \ge 16$ by monotonicity of multiplication by a positive factor; but $16 > 10 > 4$ .

step 2.1L10algebra

3.2

$25$ is irreducible in $H$ . Suppose $25 = uv$ with $u, v \in H$ and $u, v > 1$ . Each of $u$ and $v$ has a prime divisor by [L7]; if $q \mid u$ then $q \mid 25 = 5 \cdot 5$ , so $q \mid 5$ by [L8], and $q$ being a positive divisor of the prime $5$ with $q > 1$ forces $q = 5$ . Hence $5 \mid u$ , and symmetrically $5 \mid v$ ; write $u = 5w$ , $v = 5y$ .

step 2.1step 2.2L4L7L8

4.1

Then $25 \cdot 1 = 25 = uv = 25(wy)$ , and $25 \ne 0$ , so $wy = 1$ by cancellation. Since $u = 5w > 0$ and $5 > 0$ we get $w > 0$ , hence $w \ge 1$ ; likewise $y \ge 1$ ; and $wy = 1$ with both $\ge 1$ forces $w = y = 1$ , since $w \ge 2$ would give $wy \ge 2$ . So $u = v = 5$ , contradicting $5 \notin H$ from step 1.3.

step 1.1step 1.3step 3.2L2L9L10algebra

5.1

The two factorisations. $4 \cdot 25 = 100$ and $10 \cdot 10 = 100$ , and by [L3] the lists $h = (4,25)$ and $h' = (10,10)$ of length $2$ have $\prod_{i<2} h_i = (1 \cdot 4) \cdot 25 = 100$ and $\prod_{i<2} h'_i = (1 \cdot 10) \cdot 10 = 100$ . All four entries are irreducible in $H$ by steps 3.1 and 4.1.

step 3.1step 4.1L2L3algebra

6.1

No permutation matches them. For $\pi \in \operatorname{Sym}(2)$ the value $h_{\pi(0)}$ is $4$ or $25$ , and $h'_0 = 10$ differs from both. So the refuted claim fails for $M = H$ at the element $100$ , with $r = s = 2$ : the lists have the same length and still no permutation carries one to the other.

step 1.2step 5.1L1∎

Remarks

Existence is not the issue; uniqueness is. Every element of $H$ greater than $1$ does factor into irreducibles of $H$ , by exactly the descent that proves Every integer $n \ge 1$ is a finite product of primes: there are $r \in \mathbb{N}$ and a list $p : r \to \mathbb{Z}$ of primes with $n = \prod_{i<r} p_i$ , the case $n = 1$ being the empty product in $\mathbb{Z}$ : a smallest factor above $1$ is irreducible, and the quotient is smaller. What fails in $H$ is the second half of The fundamental theorem of arithmetic: every integer $n \ge 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i<r} p_i = \prod_{j<s} q_j$ with every $p_i$ and $q_j$ prime, then $r = s$ and $q_i = p_{\pi(i)}$ for some $\pi \in \operatorname{Sym}(r)$ .
What fails is Euclid's lemma. In $H$ , $10$ is irreducible and $100 = 4 \cdot 25$ is a product of two elements of $H$ that $10$ divides inside $H$ , since $100 = 10 \cdot 10$ ; yet $10 \nmid 4$ and $10 \nmid 25$ , because $4 = 0 \cdot 10 + 4$ and $25 = 2 \cdot 10 + 5$ have nonzero remainders. So the analogue of Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$ is false in $H$ , and by For an integer $p > 1$ : $p$ is prime if and only if, for all integers $a$ and $b$ , $p \mid ab$ implies $p \mid a$ or $p \mid b$ that property, and not indecomposability, is what unique factorisation actually needs.
The example needs nothing beyond $\mathbb{Z}$ and divisibility. The classical witness for this phenomenon uses algebraic integers, which are not available at this point in the reading order; $H$ is a subset of $\mathbb{Z}$ closed under multiplication, and every claim above is a statement about integers.

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: 97 results over 33 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

Hilbert number (Wikipedia) (standard reference, not scraped)
Fundamental theorem of arithmetic (Wikipedia) (standard reference, not scraped)
San Diego State University notes: Introduction to factorisation (standard reference, not scraped)

In the multiplicative monoid H={1,4,7,10,… }H = \{1, 4, 7, 10, \dots\}H={1,4,7,10,…} of positive integers one more than a multiple of 333, the element 100100100 has two genuinely different factorisations into irreducibles, 4⋅254 \cdot 254⋅25 and 10⋅1010 \cdot 1010⋅10