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

$\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) \geq 1$ unless $a = b = 0$

Statement

For all $a, b \in Z$ , with $\gcd$ as in Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ :

$\gcd (a, b) = \gcd (b, a)$ ;
$\gcd (a, b) = \gcd (∣ a ∣, ∣ b ∣)$ ;
$\gcd (a, 0) = ∣ a ∣$ , and in particular $\gcd (0, 0) = 0$ ;
$\gcd (a, 1) = 1$ ;
$\gcd (a, a) = ∣ a ∣$ ;
$\gcd (a, b) \geq 1$ unless $a = b = 0$ , in which case $\gcd (a, b) = 0$ .

Facts & Assumptions

Given: Integers $a$ and $b$ , and the set $D (a, b) = {d : d ∣ a and d ∣ b}$ of common divisors (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L1]

For $(a, b) \neq (0, 0)$ , $\gcd (a, b)$ is the unique greatest element of $D (a, b)$ and satisfies $\gcd (a, b) \geq 1$ ; and $\gcd (0, 0) = 0$ by convention (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L2]

$d ∣ a$ means $a = d q$ for some $q$ ; every $d$ satisfies $d ∣ 0$ ; $0 ∣ a$ only for $a = 0$ ; and $1 ∣ a$ , $a ∣ a$ for every $a$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L3]

$d ∣ a$ , $d ∣ - a$ , $- d ∣ a$ and $- d ∣ - a$ are equivalent (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$ ).

[L4]

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

[L5]

$u ∣ 1$ exactly when $u = 1$ or $u = - 1$ , and $1 \neq - 1$ ( $(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$ ).

[L6]

$∣ x ∣ = x$ when $x \geq 0$ and $∣ x ∣ = - x$ when $x \leq 0$ (The absolute value $∣ a ∣$ of an integer); $∣ x ∣ \geq 0$ and $∣ x ∣ = 0$ exactly when $x = 0$ (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$ ).

[L7]

$Z$ is a commutative ring with $x \cdot 1 = x$ , $x \cdot (- 1) = - x$ and $- (- x) = x$ ; its order is total, antisymmetric, transitive and compatible with addition, and positives are closed under multiplication (The integers form a commutative ring, Arithmetic on the integers, The integers form a totally ordered ring, Order on the integers).

Proof

technique · direct

1.1

$1 \neq 0$ and $- 1 \leq 0 \leq 1$ . If $1 = 0$ then $- 1 = - 0 = 0 = 1$ , contradicting $1 \neq - 1$ . By totality $0 \leq 1$ or $1 \leq 0$ ; in the second case adding $- 1$ gives $0 \leq - 1$ , and $- 1 \neq 0$ , so $0 < - 1$ and hence $0 < (- 1) (- 1) = 1$ , contradicting $1 \leq 0$ by antisymmetry. So $0 \leq 1$ , and adding $- 1$ gives $- 1 \leq 0$ .

L5L7

1.2

$∣ x ∣ ∣ x$ for every $x$ : by totality $x \geq 0$ , when $x = ∣ x ∣ = ∣ x ∣ \cdot 1$ , or $x \leq 0$ , when $∣ x ∣ = - x$ and so $x = - (- x) = - ∣ x ∣ = ∣ x ∣ \cdot (- 1)$ .

L6L7

1.3

For every $d$ and $x$ : $d ∣ x$ if and only if $d ∣ ∣ x ∣$ , because $∣ x ∣$ is $x$ or $- x$ and the two conditions $d ∣ x$ , $d ∣ - x$ are equivalent.

L3L6

1.4

Claim 1. The condition defining $D (a, b)$ is unchanged when $a$ and $b$ are interchanged, so $D (a, b) = D (b, a)$ ; and $(a, b) = (0, 0)$ exactly when $(b, a) = (0, 0)$ . Hence the two greatest elements coincide in the first case, and both values are $0$ in the second.

1.5

Claim 5. $D (a, a) = {d : d ∣ a} = D (a, 0)$ , and $(a, a) = (0, 0)$ exactly when $(a, 0) = (0, 0)$ , so $\gcd (a, a) = \gcd (a, 0)$ .

L1L2

1.6

Claim 6 is [L1] restated: for $(a, b) \neq (0, 0)$ the value $\gcd (a, b)$ is $\geq 1$ because $1$ is a common divisor and $\gcd (a, b)$ is greatest, and at $(0, 0)$ the value is $0$ by convention.

L1L2

2.1

Claim 2. By step 1.3, $D (a, b) = D (∣ a ∣, ∣ b ∣)$ ; and $∣ a ∣ = 0$ exactly when $a = 0$ , so $(a, b) = (0, 0)$ exactly when $(∣ a ∣, ∣ b ∣) = (0, 0)$ . Hence the values agree in both cases.

step 1.3L1L6

2.2

Claim 3. $D (a, 0) = {d : d ∣ a}$ , since every $d$ divides $0$ . If $a = 0$ this is $Z$ and $\gcd (0, 0) = 0 = ∣ 0 ∣$ by the convention. If $a \neq 0$ , then $∣ a ∣ \in D (a, 0)$ by step 1.2, and every $d \in D (a, 0)$ satisfies $d \leq ∣ a ∣$ by [L4], so $∣ a ∣$ is the greatest element of $D (a, 0)$ and $\gcd (a, 0) = ∣ a ∣$ .

step 1.2L1L2L4L6

2.3

Claim 4. Every $d \in D (a, 1)$ satisfies $d ∣ 1$ , hence $d = 1$ or $d = - 1$ ; and $1 \in D (a, 1)$ since $1 ∣ a$ and $1 ∣ 1$ . Also $(a, 1) \neq (0, 0)$ because $1 \neq 0$ . Since $- 1 \leq 1$ by step 1.1, the greatest element of $D (a, 1)$ is $1$ , so $\gcd (a, 1) = 1$ .

step 1.1L1L2L5L7

3.1

Claim 3's second half and claim 5 now read off: $\gcd (0, 0) = 0 = ∣ 0 ∣$ , and $\gcd (a, a) = \gcd (a, 0) = ∣ a ∣$ .

step 2.2step 1.5

4.1

Claims 1 to 6 are established.

step 1.4step 2.1step 2.2step 2.3step 3.1step 1.6∎

Remarks

Claim 2 is what lets every later argument assume the arguments are nonnegative, and claim 1 lets it assume they are in either order. Both are used without comment below.
Every clause is checked at the boundary. Claim 3 covers $a = 0$ , where it returns the convention $\gcd (0, 0) = 0$ rather than contradicting it; claim 4 holds at $a = 0$ , giving $\gcd (0, 1) = 1$ ; and claim 5 holds at $a = 0$ , giving $\gcd (0, 0) = 0$ . There is no pair at which a clause above is silent.

Depends on

Used by

Dependency tree · two levels

38 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⁡gcd is symmetric and unchanged by signs: gcd⁡(a,b)=gcd⁡(b,a)=gcd⁡(∣a∣,∣b∣)gcd(a,b)=gcd(b,a)=gcd(∣a∣,∣b∣); moreover gcd⁡(a,0)=∣a∣gcd(a,0)=∣a∣, gcd⁡(a,1)=1gcd(a,1)=1, gcd⁡(a,a)=∣a∣gcd(a,a)=∣a∣, and gcd⁡(a,b)≥1gcd(a,b)≥1 unless a=b=0a=b=0