Alphabeta MathDivisibility and Greatest Common Divisors: Examples and Counterexamples
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.
✓ 9 results · all verified · 5 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
2 · Logical flowchart
3 · Items
Example
gcd(1071, 462) = 21 by the Euclidean algorithm, with the back-substitution giving 21 = 7 · 462 - 3 · 1071
Example
Bézout coefficients are not unique: 1071 · (-3) + 462 · 7 = 21 and 1071 · 19 + 462 · (-44) = 21, and for nonzero a, b every solution has the form (x₀ + t b/d, y₀ - t a/d)
Example
gcd at the boundary: gcd(a,0) = |a|, gcd(0,0) = 0, and the convention gcd(0,0) = 0 is exactly what makes gcd(ca,cb) = |c|gcd(a,b) true at c = 0
Example
ax + by = c has an integer solution exactly when gcd(a,b) ∣ c: 6x + 15y = 9 is solvable and 6x + 15y = 7 is not
Example
12ℤ + 18ℤ = 6ℤ and 12ℤ ∩ 18ℤ = 36ℤ, the arithmetic of gcd and lcm read off the subgroups of (ℤ,+)
Example
Consecutive Fibonacci numbers are coprime, and for every m ∈ ℕ the Euclidean algorithm on (Fₘ₊₃, Fₘ₊₂) takes exactly m+1 divisions, with quotient 1 in the first m of them and quotient 2 in the last
Counterexample
6 ∣ 4 · 9 while 6 ∤ 4 and 6 ∤ 9: dividing a product does not force dividing a factor, and the coprimality hypothesis is what fails
Counterexample
The common divisors of (0,0) are all of ℤ and have no greatest element in the order of ℤ, so gcd(0,0) cannot be defined as a maximum and is fixed by convention
False statement