An integer a divides b if b = a · k for some integer k. From this single relation flow the division algorithm, the GCD, and the Euclidean algorithm that computes it.
The divides relation
We write a | b ("a divides b") when there exists an integer k such that b = a k. Divisibility is reflexive (a | a) and transitive (if a | b and b | c then a | c), but not symmetric.
Scheme
; Divisibility: a | b iff b = a * k for some integer k
(define (divides? a b)
(= 0 (modulo b a)))
(display "3 | 12? ") (display (divides? 312)) (newline)
(display "3 | 7? ") (display (divides? 37)) (newline)
(display "5 | 0? ") (display (divides? 50)) (newline)
; Transitivity: if a|b and b|c then a|c
(display "2|6 and 6|18, so 2|18? ")
(display (and (divides? 26) (divides? 618) (divides? 218)))
Python
# Divisibilitydef divides(a, b):
return b % a == 0print(f"3 | 12? {divides(3, 12)}")
print(f"3 | 7? {divides(3, 7)}")
print(f"5 | 0? {divides(5, 0)}")
print(f"2|6 and 6|18, so 2|18? {divides(2,6) and divides(6,18) and divides(2,18)}")
The division algorithm
For any integers a and b with b > 0, there exist unique integers q (quotient) and r (remainder) such that a = b q + r and 0 ≤ r < b. This is not really an algorithm but an existence theorem. The algorithm is just long division.
Scheme
; Division algorithm: a = b*q + r, 0 <= r < b
(define (div-algorithm a b)
(let ((q (quotient a b))
(r (remainder a b)))
(display a) (display " = ")
(display b) (display " * ")
(display q) (display " + ")
(display r) (newline)))
(div-algorithm 175) ; 17 = 5*3 + 2
(div-algorithm 1007) ; 100 = 7*14 + 2
(div-algorithm 2323) ; 23 = 23*1 + 0
GCD and the Euclidean algorithm
The greatest common divisor gcd(a, b) is the largest positive integer dividing both a and b. The Euclidean algorithm computes it by repeated division: gcd(a, b) = gcd(b, a mod b), bottoming out at gcd(d, 0) = d. It is one of the oldest known algorithms.
Scheme
; Euclidean algorithm: gcd(a, b) = gcd(b, a mod b)
(define (gcd a b)
(if (= b 0)
a
(gcd b (modulo a b))))
(display "gcd(48, 18) = ") (display (gcd 4818)) (newline)
(display "gcd(100, 75) = ") (display (gcd 10075)) (newline)
(display "gcd(17, 5) = ") (display (gcd 175)) (newline)
; Trace the steps for gcd(48, 18):; gcd(48, 18) -> gcd(18, 12) -> gcd(12, 6) -> gcd(6, 0) = 6
(display "Steps: 48->18->12->6->done")
Python
# Euclidean algorithmdef gcd(a, b):
while b != 0:
a, b = b, a % b
return a
print(f"gcd(48, 18) = {gcd(48, 18)}")
print(f"gcd(100, 75) = {gcd(100, 75)}")
print(f"gcd(17, 5) = {gcd(17, 5)}")
Bezout's identity
Bezout's identity: for any integers a and b, there exist integers x and y such that a x + b y = gcd(a, b). The extended Euclidean algorithm finds these coefficients by working backwards through the GCD computation.
Scheme
; Extended Euclidean algorithm; Returns (gcd, x, y) such that a*x + b*y = gcd
(define (extended-gcd a b)
(if (= b 0)
(list a 10)
(let* ((result (extended-gcd b (modulo a b)))
(g (car result))
(x (cadr result))
(y (caddr result)))
(list g y (- x (* (quotient a b) y))))))
(let ((result (extended-gcd 4818)))
(display "gcd(48,18) = ") (display (car result)) (newline)
(display "x = ") (display (cadr result))
(display ", y = ") (display (caddr result)) (newline)
(display "Check: 48*") (display (cadr result))
(display " + 18*") (display (caddr result))
(display " = ") (display (+ (* 48 (cadr result)) (* 18 (caddr result)))))
Python
# Extended Euclidean algorithmdef extended_gcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = extended_gcd(b, a % b)
return g, y, x - (a // b) * y
g, x, y = extended_gcd(48, 18)
print(f"gcd(48,18) = {g}")
print(f"x = {x}, y = {y}")
print(f"Check: 48*{x} + 18*{y} = {48*x + 18*y}")
Neighbors
→ Algorithms Ch.2 — recursion: the Euclidean algorithm is a classic recursive procedure
Euclidean algorithm computes it by repeated division: gcd(a, b) = gcd(b, a mod b), bottoming out at gcd(d, 0) = d. It is one of the oldest known algorithms.