LemmaStatement: AI-adaptedProof: AI-adaptedSession-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.

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$

Statement

Let $a, b, c \in \mathbb{Z}$ .

If $\gcd(a,b) = 1$ and $a \mid bc$ , then $a \mid c$ .
If $a \mid c$ , $b \mid c$ and $\gcd(a,b) = 1$ , then $ab \mid c$ .

Facts & Assumptions

Given: Integers $a, b, c$ .

[L1]

$a$ and $b$ are coprime exactly when $\gcd(a,b) = 1$ , and this holds exactly when $ax + by = 1$ for some $x, y \in \mathbb{Z}$ (Coprime integers: $\gcd(a,b) = 1$ , $a$ and $b$ are coprime if and only if $ax + by = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $-1$ , Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ ).

[L2]

$\gcd(a,b) = \gcd(b,a)$ ( $\gcd$ is symmetric and unchanged by signs: $\gcd(a,b) = \gcd(b,a) = \gcd(|a|,|b|)$ ; moreover $\gcd(a,0) = |a|$ , $\gcd(a,1) = 1$ , $\gcd(a,a) = |a|$ , and $\gcd(a,b) \ge 1$ unless $a = b = 0$ ).

[L3]

Divisibility is reflexive and transitive; if $d \mid u$ and $d \mid v$ then $d \mid ux + vy$ for all $x, y$ ; and $d \mid u$ implies $d \mid uw$ (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$ ).

[L4]

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

[L5]

$\mathbb{Z}$ is a commutative ring: addition and multiplication are associative and commutative, $x \cdot 1 = x$ , and multiplication distributes over addition (The integers form a commutative ring, Arithmetic on the integers).

Proof

technique · direct

1.1

Claim 1. Assume $\gcd(a,b) = 1$ and $a \mid bc$ , and fix $x, y$ with $ax + by = 1$ .

L1choose

1.2

Claim 2. Assume $a \mid c$ , $b \mid c$ and $\gcd(a,b) = 1$ . Write $c = as$ with $s \in \mathbb{Z}$ .

L4choose

2.1

Multiplying $ax + by = 1$ by $c$ gives $a(xc) + (bc)y = c$ , using associativity, commutativity and distributivity.

step 1.1L5

3.1

Now $a \mid a$ , hence $a \mid a(xc)$ by [L3]; and $a \mid bc$ , hence $a \mid (bc)y$ by [L3]. Applying linearity to these two with coefficients $1$ and $1$ gives $a \mid a(xc) + (bc)y = c$ .

step 1.1step 2.1L3L5

4.1

Then $b \mid c = as$ , and $\gcd(b,a) = \gcd(a,b) = 1$ by [L2], so claim 1 applied with $b$ , $a$ , $s$ in place of $a$ , $b$ , $c$ gives $b \mid s$ .

step 3.1step 1.2L2

5.1

Write $s = bt$ ; then $c = as = a(bt) = (ab)t$ , so $ab \mid c$ .

step 1.2step 4.1L4L5∎

Remarks

No primality is used. Claim 1 is exactly the statement usually met as Euclid's lemma with $a$ prime; what the proof needs is coprimality of $a$ with $b$ , and primality of $a$ enters only later, as a way of guaranteeing that coprimality. This is why the lemma is homed here rather than with the primes.
Coprimality is essential in both claims. Without it, $6 \mid 4 \cdot 9$ while $6$ divides neither factor ( $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 ↗); and $2 \mid 4$ , $4 \mid 4$ but $2 \cdot 4 = 8 \nmid 4$ .

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 52 results over 19 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)

If gcd⁡(a,b)=1\gcd(a,b) = 1gcd(a,b)=1 and a∣bca \mid bca∣bc then a∣ca \mid ca∣c; and if a∣ca \mid ca∣c, b∣cb \mid cb∣c and gcd⁡(a,b)=1\gcd(a,b) = 1gcd(a,b)=1 then ab∣cab \mid cab∣c