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.1L10

$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$ .

1.2L1L2L4L10

$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$ .

1.3L4L5algebra

$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].

2.1step 1.1L4L10

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$ .

2.2step 1.1L5L6L7algebra

$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$ .

3.1step 2.1L10algebra

$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$ .

3.2step 2.1step 2.2L4L7L8

$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$ .

4.1step 1.1step 1.3step 3.2L2L9L10algebra

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.

5.1step 3.1step 4.1L2L3algebra

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.

6.1step 1.2step 5.1L1∎

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.

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.

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

Facts & Assumptions

Counterexample

Remarks

Depends on

Dependency tree · 2 levels

Sources

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

Statement refuted

Facts & Assumptions

Counterexample

Remarks

Depends on

Dependency tree · 2 levels

Sources

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$