Integer divisibility and the Euclidean algorithm
Repeated division computes a greatest common divisor.
Key knowledge
For positive integers a and b, Euclidean division a = qb + r, 0 ≤ r < b, preserves gcd(a,b) = gcd(b,r). When a remainder first reaches zero, the current divisor is the gcd. Integers u,v satisfy ua + vb = gcd(a,b).
Values and equations
a = qb + r; gcd(a,b) = gcd(b,r)
- a, b
- Positive integer inputs at a division step
- q
- Integer quotient
- r
- Remainder with 0 ≤ r < b
Conditions and scope
- The current divisor is positive; stop when the remainder is zero.
- This entry restricts inputs to positive integers.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Theorems 6.1–6.3: division/GCD/Bézout; Euclidean example; Theorem 6.7: prime factorization.
2026-10-10 · Integer division, Euclidean GCD and Bézout relation.
Entry details
Permanent link to this entry ↗- Record identity
- math-divisibility-gcd
- Revision
- university-reference.1
- Structured reference record
- University reference