CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck 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 $\geq 1$ , contains $1$ , and is closed under the multiplication of $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 = u v$ . 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_{π (i)}$ for every $i < r$ , for some $π \in Sym (r)$ (The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition, The product $g_{0} g_{1} \dots 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 Z : h \geq 1 and 3 ∣ h - 1} = {1, 4, 7, 10, 13, \dots},$

with the multiplication of $Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ 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 \neq 4$ and $10 \neq 25$ .

Numerals. For $k \in N$ the symbol $k$ inside $Z$ means $ι (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]

$(Z, \cdot, 1)$ is a commutative monoid ( $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ); $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 < σ (m)} g_{i} = (\prod_{i < m} g_{i}) g_{m}$ (The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

[L4]

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

[L5]

For $a \in Z$ and $b > 0$ there is exactly one pair $(q, r)$ with $a = q b + r$ and $0 \leq r < b$ , and $b ∣ a$ exactly when $r = 0$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ ).

[L6]

If $d ∣ a$ and $a \neq 0$ then $∣ d ∣ \leq ∣ a ∣$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ 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 ∣ u v$ then $q ∣ u$ or $q ∣ v$ (Euclid's lemma: if $p$ is prime and $p ∣ a b$ then $p ∣ a$ or $p ∣ b$ ).

[L9]

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

[L10]

The order on $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); $ι$ is injective and order preserving with image the nonnegative integers (The naturals embed in the integers, The natural numbers $N$ (von Neumann), Order on the natural numbers, Discreteness: $σ (n)$ is the immediate successor).

Counterexample

technique · direct

1.1

$0 < 1$ in $Z$ , and every integer $y > 0$ satisfies $y \geq 1$ : $y = ι (t)$ with $t \neq 0$ , so $1 \leq y$ because $ι$ preserves the order. Consequently $y > c$ implies $y \geq c + 1$ .

L10

1.2

$H$ is a commutative monoid under the multiplication of $Z$ . It contains $1$ , since $1 \geq 1$ and $1 - 1 = 0 = 3 \cdot 0$ . It is closed: if $h - 1 = 3 a$ and $h^{'} - 1 = 3 b$ then $h h^{'} - 1 = (3 a + 1) (3 b + 1) - 1 = 3 (3 a b + a + b)$ , so $3 ∣ h h^{'} - 1$ ; and $h, h^{'} \geq 1$ give $h h^{'} \geq 1$ . Associativity, commutativity and the identity are inherited from $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 ∤ 4$ by [L5].

L4L5algebra

2.1

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

step 1.1L4L10

2.2

$5$ is prime. It exceeds $1$ ; a positive divisor $d$ of $5$ satisfies $1 \leq d \leq 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 = u v$ or $10 = u v$ with $u, v \in H$ both $> 1$ , then $u \geq 4$ and $v \geq 4$ by step 2.1, so $u v \geq 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 = u v$ with $u, v \in H$ and $u, v > 1$ . Each of $u$ and $v$ has a prime divisor by [L7]; if $q ∣ u$ then $q ∣ 25 = 5 \cdot 5$ , so $q ∣ 5$ by [L8], and $q$ being a positive divisor of the prime $5$ with $q > 1$ forces $q = 5$ . Hence $5 ∣ u$ , and symmetrically $5 ∣ v$ ; write $u = 5 w$ , $v = 5 y$ .

step 2.1step 2.2L4L7L8

4.1

Then $25 \cdot 1 = 25 = u v = 25 (w y)$ , and $25 \neq 0$ , so $w y = 1$ by cancellation. Since $u = 5 w > 0$ and $5 > 0$ we get $w > 0$ , hence $w \geq 1$ ; likewise $y \geq 1$ ; and $w y = 1$ with both $\geq 1$ forces $w = y = 1$ , since $w \geq 2$ would give $w y \geq 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 $π \in Sym (2)$ the value $h_{π (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 \geq 1$ is a finite product of primes: there are $r \in N$ and a list $p : r \to Z$ of primes with $n = \prod_{i < r} p_{i}$ , the case $n = 1$ being the empty product in $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 \geq 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_{π (i)}$ for some $π \in 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 ∤ 4$ and $10 ∤ 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 ∣ a b$ then $p ∣ a$ or $p ∣ 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 ∣ a b$ implies $p ∣ a$ or $p ∣ b$ that property, and not indecomposability, is what unique factorisation actually needs.
The example needs nothing beyond $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 $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 · two levels

72 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

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,…} of positive integers one more than a multiple of 33, the element 100100 has two genuinely different factorisations into irreducibles, 4⋅254⋅25 and 10⋅1010⋅10