LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)

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.

$\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ for all integers $a, b, c$ , the identity holding at $c = 0$ and at $(a, b) = (0, 0)$ as well

Statement

For all $a, b, c \in Z$ ,

$\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$

(Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , The absolute value $∣ a ∣$ of an integer). The identity is asserted for every triple, including $c = 0$ and $(a, b) = (0, 0)$ , where both sides are $0$ .

Facts & Assumptions

Given: Integers $a, b, c$ , and $g : = \gcd (a, b)$ , $h : = \gcd (c a, c b)$ .

[L1]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x \cdot 0 = 0$ , $x \cdot 1 = x$ , $x \cdot (- 1) = - x$ , multiplication distributes over addition, and every $x$ has an additive inverse, with $- (- x) = x$ (The integers form a commutative ring, Arithmetic on the integers).

[L2]

The order on $Z$ is total, antisymmetric and transitive, and positives are closed under multiplication; $x < y$ means $x \leq y$ together with $x \neq y$ (The integers form a totally ordered ring, Order on the integers).

[L3]

$\gcd (u, v) \geq 0$ always, with $\gcd (u, v) \geq 1$ when $(u, v) \neq (0, 0)$ and $\gcd (0, 0) = 0$ by convention; $\gcd (u, v)$ is a common divisor of $u$ and $v$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L4]

Every common divisor of $u$ and $v$ divides $\gcd (u, v)$ (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).

[L5]

For $(u, v) \neq (0, 0)$ there are $x_{0}, y_{0}$ with $u x_{0} + v y_{0} = \gcd (u, v)$ (Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution).

[L6]

If $d ∣ u$ and $d ∣ v$ then $d ∣ u x + v y$ for all $x, y$ ; and $d ∣ u$ implies $d ∣ u w$ and $- d ∣ u$ (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 $d ∣ u$ and $u \neq 0$ then $∣ d ∣ \leq ∣ u ∣$ (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 ∣$ ); $d ∣ u$ means $u = d q$ for some $q$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L8]

$∣ x ∣ \geq 0$ ; $∣ x ∣ = 0$ exactly when $x = 0$ ; $∣ x ∣ = x$ when $x \geq 0$ ; and $x$ is $∣ x ∣$ or $- ∣ x ∣$ (The absolute value $∣ a ∣$ of an integer, Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

[L9]

A product of two nonzero integers is nonzero (The integers have no zero divisors; multiplicative cancellation).

Proof

technique · cases

1.1

If $0 \leq u$ and $0 \leq v$ then $0 \leq u v$ : for $u = 0$ or $v = 0$ the product is $0$ , and otherwise $0 < u$ and $0 < v$ , so $0 < u v$ .

L1L2

1.2

Case $c = 0$ : then $c a = c b = 0$ , so the left side is $\gcd (0, 0) = 0$ ; and $∣ c ∣ = ∣ 0 ∣ = 0$ , so the right side is $0 \cdot g = 0$ .

assume-case zeroL1L3L8

1.3

Case $(a, b) = (0, 0)$ : then $c a = c b = 0$ , so the left side is $\gcd (0, 0) = 0$ ; and $g = \gcd (0, 0) = 0$ , so the right side is $∣ c ∣ \cdot 0 = 0$ .

assume-case originL1L3

1.4

Case $c \neq 0$ and $(a, b) \neq (0, 0)$ . Then $g \geq 1$ , and one of $a, b$ is nonzero, say $a \neq 0$ ; so $c a \neq 0$ by [L9] and hence $(c a, c b) \neq (0, 0)$ and $h \geq 1$ . Also $∣ c ∣ \neq 0$ , and $∣ c ∣ g \neq 0$ by [L9].

assume-case genericL3L8L9

2.1

In the case of step 1.4, $∣ c ∣ g$ is a common divisor of $c a$ and $c b$ . Indeed $g ∣ a$ , say $a = g a_{1}$ ; then $c a = c g a_{1}$ , and $c$ is $∣ c ∣$ or $- ∣ c ∣$ by [L8], so $c a = ∣ c ∣ g a_{1}$ or $c a = ∣ c ∣ g (- a_{1})$ , and in either case $∣ c ∣ g ∣ c a$ . The same argument with $b$ gives $∣ c ∣ g ∣ c b$ .

step 1.4L1L3L7L8

2.2

Conversely, by [L5] fix $x_{0}, y_{0}$ with $a x_{0} + b y_{0} = g$ ; multiplying by $c$ gives $(c a) x_{0} + (c b) y_{0} = c g$ . Since $h ∣ c a$ and $h ∣ c b$ , [L6] gives $h ∣ c g$ ; and $∣ c ∣ g$ is $c g$ or $- c g$ , because $∣ c ∣$ is $c$ or $- c$ , so $h ∣ ∣ c ∣ g$ as well.

step 1.4L1L3L5L6L8

3.1

Hence $∣ c ∣ g ∣ h$ by [L4].

step 2.1L4

4.1

Both $h$ and $∣ c ∣ g$ are nonzero by step 1.4, and both are nonnegative, $h$ by [L3] and $∣ c ∣ g$ by step 1.1 and [L8]. From $h ∣ ∣ c ∣ g$ and $∣ c ∣ g \neq 0$ , [L7] gives $∣ h ∣ \leq ∣ ∣ c ∣ g ∣ = ∣ c ∣ g$ , that is $h \leq ∣ c ∣ g$ ; from $∣ c ∣ g ∣ h$ and $h \neq 0$ , [L7] gives $∣ c ∣ g \leq ∣ h ∣ = h$ .

step 1.1step 1.4step 3.1step 2.2L3L7L8

5.1

By antisymmetry $h = ∣ c ∣ g$ in the case of step 1.4.

step 4.1L2

6.1

The three cases of steps 1.2, 1.3 and 1.4 exhaust the possibilities, since either $c = 0$ , or $(a, b) = (0, 0)$ , or neither; so $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ for all $a, b, c$ .

step 1.2step 1.3step 5.1cases-exhaustive∎

Remarks

The boundary cases are the point, not an aside. The convention $\gcd (0, 0) = 0$ is the only value under which this identity extends to $(a, b) = (0, 0)$ : it would read $\gcd (0, 0) = ∣ c ∣ \gcd (0, 0)$ for every $c$ , and taking $∣ c ∣ = 1 + 1$ gives $\gcd (0, 0) = 0$ . That is a constraint on the choice, not a derivation from this lemma — steps 1.2 and 1.3 above read the boundary value off the convention rather than proving it. The choice is made where the convention is fixed (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ) and instantiated on the companion page ( $\gcd$ at the boundary: $\gcd (a, 0) = ∣ a ∣$ , $\gcd (0, 0) = 0$ , and the convention $\gcd (0, 0) = 0$ is exactly what makes $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ true at $c = 0$ ↗).
Why $∣ c ∣$ and not $c$ . $\gcd$ is nonnegative by construction, so the right side must be too; with $c < 0$ and $g > 0$ the product $c g$ is negative and could not be a greatest common divisor.

Depends on

Used by

Dependency tree · two levels

36 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

Greatest common divisor (Wikipedia) (standard reference, not scraped)

gcd⁡(ca,cb)=∣c∣ gcd⁡(a,b)gcd(ca,cb)=∣c∣gcd(a,b) for all integers a,b,ca,b,c, the identity holding at c=0c=0 and at (a,b)=(0,0)(a,b)=(0,0) as well