Alphabeta Math

Divisibility, Greatest Common Divisors and Bézout's Identity

About this page
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.

✓ 20 results · all verified · 16 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 4 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
Real Analysis
Set Theory
2 · Logical flowchart

3 · Items

Definition

The absolute value |a| of an integer

Lemma

Absolute value in ℤ: |a| ≥ 0; |a| = 0 exactly when a = 0; |-a| = |a|; |ab| = |a| |b|; -|a| ≤ a ≤ |a|; and |a| ≤ c exactly when -c ≤ a ≤ c

Definition

Divisibility in ℤ: d ∣ a when a = dq for some integer q

Corollary

Division with remainder for any nonzero divisor: for a ∈ ℤ and b ≠ 0 there are unique q, r ∈ ℤ with a = qb + r and 0 ≤ r < |b|

Lemma

Divisibility is reflexive and transitive on ℤ, and is linear: if d ∣ a and d ∣ b then d ∣ ax + by for all integers x, y; also d ∣ a implies d ∣ ac, -d ∣ a and d ∣ -a

Lemma

If d ∣ a and a ≠ 0 then d ≠ 0 and |d| ≤ |a|; hence the set of divisors of a nonzero integer is bounded above by |a|

Lemma

(ℤ, ·, 1) is a commutative monoid whose group of units is {1, -1}; equivalently u ∣ 1 holds exactly for u = 1 and u = -1

Definition

Associates in ℤ: integers each of which divides the other

Lemma

For integers a and b the following are equivalent: a ∣ b and b ∣ a; b = ua for a unit u; |a| = |b|. Being associates is an equivalence relation whose class of a is {a, -a}

Lemma

A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element

Definition

Common divisor, and the greatest common divisor gcd(a,b), with the convention gcd(0,0) := 0

Lemma

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) ≥ 1 unless a = b = 0

Theorem

Bézout's identity: for integers a, b not both zero, gcd(a,b) is the least positive element of { ax + by : x, y ∈ ℤ }; in particular ax + by = gcd(a,b) has an integer solution

Corollary

Every common divisor of a and b divides gcd(a,b); consequently d = gcd(a,b) exactly when d ≥ 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

Lemma

If a = qb + r then a, b and b, r have exactly the same common divisors, so gcd(a,b) = gcd(b,r)

Theorem

The Euclidean algorithm: for a ∈ ℤ and b > 0 the remainder descent from (a,b) terminates, and the last nonzero remainder is gcd(a,b)

Corollary

The extended Euclidean algorithm: the same descent produces integers x, y with ax + by = gcd(a,b), so Bézout coefficients are computed and not merely shown to exist

Definition

Coprime integers: gcd(a,b) = 1

Lemma

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

Lemma

If gcd(a,b) = 1 and a ∣ bc then a ∣ c; and if a ∣ c, b ∣ c and gcd(a,b) = 1 then ab ∣ c

Lemma

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

Corollary

If d = gcd(a,b) is nonzero then a/d and b/d are coprime

Definition

Common multiple, and the least common multiple lcm(a,b), taken to be 0 when a = 0 or b = 0

Theorem

Every common multiple of a and b is a multiple of lcm(a,b), and gcd(a,b) · lcm(a,b) = |ab|

Lemma

Every subgroup of (ℤ, +) is ⟨ n ⟩ = nℤ for exactly one natural number n

Theorem

aℤ + bℤ = gcd(a,b) ℤ and aℤ ∩ bℤ = lcm(a,b) ℤ; equivalently, in (ℤ,+) the subgroup generated by {a,b} is ⟨ gcd(a,b) ⟩ and ⟨ a ⟩ ∩ ⟨ b ⟩ = ⟨ lcm(a,b) ⟩

Sources