[04 & 05] Greatest Common Divisors and Least Common Multiples; The Euclidean Algorithm

common divisors

A positive integer can be a factor of two positive integers, a and b. Such factors are called

greatest common divisor

Let ab ∈ Z, with at least one of them nonzero. The ___________ of a and b is the (positive) integer d satisfying

(1) d | a and d | b; and

(2) if c | a and c | b, then c ∈ d

Theorem 4.3: B ́ezout’s Identity

Let a, b Z, not both zero. Then there exist integers x and y

such that

d = gcd(a, b) = ax + by.

relatively prime/coprime

Two integers a and b, not both zero, are said to be _________ whenever gcd(a, b)=1.

Euclid’s Lemma

If a | bc with gcd(a, b)=1, then a | c.

Least Common Multiple

The ___________ of two nonzero integers a and b, de-

noted by lcm(a, b) is the (positive) integer m satisfying

(1) a | m and b | m; and

(2) if a | n and b | n, then n ≤ m.

Euclidean Algorithm

A more efficient process, involving the repeated application of the Division Algorithm, is given in Book VII of The Elements and is now referred to as the