CounterexampleConstruction: AI-adaptedVerification: AI-generatedSession-authored (Fable 5 assisted)precheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28

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.

$6 \mid 4 \cdot 9$ while $6 \nmid 4$ and $6 \nmid 9$ : dividing a product does not force dividing a factor, and the coprimality hypothesis is what fails

Statement refuted

Refuted claim: for all integers $d, a, b$ , if $d \mid ab$ then $d \mid a$ or $d \mid b$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

Witness: $d = 6$ , $a = 4$ , $b = 9$ . Here $4 \cdot 9 = 36 = 6 \cdot 6$ , so $6 \mid 4 \cdot 9$ ; but $4 = 0 \cdot 6 + 4$ and $9 = 1 \cdot 6 + 3$ have nonzero remainders, so $6 \nmid 4$ and $6 \nmid 9$ .

The true statement in this direction carries a coprimality hypothesis (If $\gcd(a,b) = 1$ and $a \mid bc$ then $a \mid c$ ; and if $a \mid c$ , $b \mid c$ and $\gcd(a,b) = 1$ then $ab \mid c$ ): if $\gcd(d,a) = 1$ and $d \mid ab$ then $d \mid b$ . That hypothesis is exactly what fails here, in both readings: $\gcd(6,4) = 2$ and $\gcd(6,9) = 3$ , and neither is $1$ .

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 integers $4$ , $6$ , $9$ and $36$ .

[L1]

$\mathbb{Z}$ is a commutative ring: multiplication is associative and commutative, $x \cdot 1 = x$ , $x \cdot (-1) = -x$ , $x \cdot 0 = 0$ , and multiplication distributes over addition (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L2]

The order on $\mathbb{Z}$ is total, antisymmetric and transitive (The integers form a totally ordered ring, Order on the integers).

[L3]

$d \mid u$ means $u = dq$ for some $q \in \mathbb{Z}$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

[L4]

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

[L5]

$d = \gcd(u,v)$ exactly when $d \ge 0$ , $d \mid u$ , $d \mid v$ , and every common divisor of $u$ and $v$ divides $d$ (Every common divisor of $a$ and $b$ divides $\gcd(a,b)$ ; consequently $d = \gcd(a,b)$ exactly when $d \ge 0$ , $d \mid a$ , $d \mid b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a,b) = (0,0)$ as well, Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ ).

[L6]

If $d \mid u$ and $d \mid v$ then $d \mid ux + vy$ for all $x,y$ (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$ ).

[L7]

If $\gcd(u,v) = 1$ and $u \mid vw$ then $u \mid w$ (If $\gcd(a,b) = 1$ and $a \mid bc$ then $a \mid c$ ; and if $a \mid c$ , $b \mid c$ and $\gcd(a,b) = 1$ then $ab \mid c$ ); $u$ and $v$ are coprime exactly when $\gcd(u,v) = 1$ (Coprime integers: $\gcd(a,b) = 1$ ).

[L8]

$\iota$ is injective and preserves order, and $2 \ne 1$ , $3 \ne 1$ in $\mathbb{N}$ (The naturals embed in the integers).

Counterexample

technique · direct

1.1

$4 \cdot 9 = 36$ and $36 = 6 \cdot 6$ , so $6 \mid 4 \cdot 9$ .

L1L3algebra

1.2

$6 \nmid 4$ : since $6 > 0$ , [L4] applies, and $4 = 0 \cdot 6 + 4$ with $0 \le 4 < 6$ is the unique representation of that form, so the remainder is $4 \ne 0$ .

L1L2L4algebra

1.3

$6 \nmid 9$ : likewise $9 = 1 \cdot 6 + 3$ with $0 \le 3 < 6$ , so the remainder is $3 \ne 0$ .

L1L2L4algebra

1.4

$\gcd(6,4) = 2$ : indeed $2 \ge 0$ , $6 = 2 \cdot 3$ and $4 = 2 \cdot 2$ , so $2$ is a common divisor; and $6 \cdot 1 + 4 \cdot (-1) = 6 - 4 = 2$ , so every common divisor of $6$ and $4$ divides $2$ by [L6]. By [L5], $\gcd(6,4) = 2$ , and $2 \ne 1$ by [L8].

L1L5L6L8algebra

1.5

$\gcd(6,9) = 3$ : indeed $3 \ge 0$ , $6 = 3 \cdot 2$ and $9 = 3 \cdot 3$ ; and $6 \cdot (-1) + 9 \cdot 1 = 3$ , so every common divisor divides $3$ by [L6]. By [L5], $\gcd(6,9) = 3$ , and $3 \ne 1$ by [L8].

L1L5L6L8algebra

2.1

Steps 1.1, 1.2 and 1.3 exhibit $d = 6$ , $a = 4$ , $b = 9$ with $d \mid ab$ , $d \nmid a$ and $d \nmid b$ : the claim is refuted.

step 1.1step 1.2step 1.3

3.1

So [L7] is not contradicted: applied with $u = 6$ it would need $\gcd(6,4) = 1$ or $\gcd(6,9) = 1$ , and by steps 1.4 and 1.5 neither holds. The failure of the refuted claim is exactly the failure of coprimality, not a failure of the lemma.

step 2.1step 1.4step 1.5L7∎

Remarks

This is the gap that primality closes. When $d$ is prime its only positive divisors are $1$ and itself, so $\gcd(d,a) = 1$ for every $a$ that $d$ does not divide, and the refuted claim becomes true. Primes are not defined on this page, and the statement above is not repaired here; it is recorded so that the coprimality hypothesis of If $\gcd(a,b) = 1$ and $a \mid bc$ then $a \mid c$ ; and if $a \mid c$ , $b \mid c$ and $\gcd(a,b) = 1$ then $ab \mid c$ is visibly doing work rather than decorating the statement.
The witness is minimal in spirit, not proved minimal. No claim is made that $(6,4,9)$ is the smallest such triple.

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: 64 results over 22 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

Euclid's lemma (Wikipedia) (standard reference, not scraped)
Coprime integers (Wikipedia) (standard reference, not scraped)

6∣4⋅96 \mid 4 \cdot 96∣4⋅9 while 6∤46 \nmid 46∤4 and 6∤96 \nmid 96∤9: dividing a product does not force dividing a factor, and the coprimality hypothesis is what fails