CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck 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 ∣ 4 \cdot 9$ while $6 ∤ 4$ and $6 ∤ 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 ∣ a b$ then $d ∣ a$ or $d ∣ b$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

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

The true statement in this direction carries a coprimality hypothesis (If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ ): if $\gcd (d, a) = 1$ and $d ∣ a b$ then $d ∣ 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 N$ the symbol $k$ inside $Z$ means $ι (k)$ , the embedding of The naturals embed in the integers.

Facts & Assumptions

Given: The integers $4$ , $6$ , $9$ and $36$ .

[L1]

$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 $Z$ is total, antisymmetric and transitive (The integers form a totally ordered ring, Order on the integers).

[L3]

$d ∣ u$ means $u = d q$ for some $q \in Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L4]

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

[L5]

$d = \gcd (u, v)$ exactly when $d \geq 0$ , $d ∣ u$ , $d ∣ 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 \geq 0$ , $d ∣ a$ , $d ∣ 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 ∣ u$ and $d ∣ v$ then $d ∣ u x + v y$ for all $x, y$ (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$ ).

[L7]

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

[L8]

$ι$ is injective and preserves order, and $2 \neq 1$ , $3 \neq 1$ in $N$ (The naturals embed in the integers).

Counterexample

technique · direct

1.1

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

L1L3algebra

1.2

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

L1L2L4algebra

1.3

$6 ∤ 9$ : likewise $9 = 1 \cdot 6 + 3$ with $0 \leq 3 < 6$ , so the remainder is $3 \neq 0$ .

L1L2L4algebra

1.4

$\gcd (6, 4) = 2$ : indeed $2 \geq 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 \neq 1$ by [L8].

L1L5L6L8algebra

1.5

$\gcd (6, 9) = 3$ : indeed $3 \geq 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 \neq 1$ by [L8].

L1L5L6L8algebra

2.1

Steps 1.1, 1.2 and 1.3 exhibit $d = 6$ , $a = 4$ , $b = 9$ with $d ∣ a b$ , $d ∤ a$ and $d ∤ 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 ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ 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 · two levels

41 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

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

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