Greatest Common Divisors¶
Some cryptographic (computer security) systems rely on factoring large numbers into prime factors. Such systems are secure because prime factorization is computationally difficult. The greatest common divisor (GCD) of two integers, the largest integer that divides both, is a different story: it can be computed quickly without factoring either number. This makes the GCD one of the basic tools of cryptography.
The Division Algorithm¶
Let \(n\in\mathbb{Z}\). An integer \(d\in\mathbb{Z}\) is said to divide \(n\), written \(d | n\), if \(n = dq\) for some integer \(q\in\mathbb{Z}\). In this case, \(d\) is called the divisor and \(q\) the quotient. Given \(n\in\mathbb{Z}\) and a positive integer \(d\), the Division Algorithm states that there are unique integers \(q,r\in\mathbb{Z}\) such that
Here, \(q\) is called the quotient as before, and \(r\) is the remainder. Note that \(d | n\) if and only if \(r = 0\), that is, there is no remainder after the division. A consequence of this equation is
which reads “when \(n\) is divided by \(d\), the remainder is \(r\)”; equivalently, \(r\) is congruent to \(n\) modulo \(d\).
In Python, the quotient \(q\) is obtained from integer division with //, and the remainder \(r\) is the output of the mod operator %.
These operators also accept a negative divisor \(d\), in which case the remainder satisfies \(d < r \leq 0\) instead, but still \(n = qd + r\).
The divmod() function efficiently computes both the quotient and the remainder.
n = 1213
d = 29
q = n // d # Quotient.
r = n % d # Remainder.
print(q, r, q * d + r)
41 24 1213
# Quotient and remainder simultaneously.
q, r = divmod(n, d)
print(q, r, q * d + r)
41 24 1213
Common Divisors¶
A common divisor of two integers \(a,b\in\mathbb{Z}\) is an integer \(c\) that divides both \(a\) and \(b\), that is, \(c|a\) and \(c|b\). If \(a\) and \(b\) are not both zero, their greatest common divisor (GCD), written \(\operatorname{GCD}(a, b)\), is the largest positive integer that divides both \(a\) and \(b\); \(\operatorname{GCD}(0, 0)\) is undefined because \(0\) has no largest divisor. The GCD satisfies
\(\operatorname{GCD}(a, b) = \operatorname{GCD}(b, a)\),
\(\operatorname{GCD}(a, b) = \operatorname{GCD}(|a|, |b|)\), and
\(\operatorname{GCD}(a, 0) = |a|\) when \(a \neq 0\).
One way to compute the GCD is to find the set of all common divisors of \(a\) and \(b\) (see Lab 4 Problem 4). However, this strategy is slow for large integers. The Euclidean algorithm is a much faster alternative. It relies on one fact: if \(a \geq 0\), \(b > 0\), then
To see why, let \(a = qb + r\) with \(r = a \bmod b\). Any common divisor of \(a\) and \(b\) also divides \(r = a - qb\), and any common divisor of \(b\) and \(r\) also divides \(a = qb + r\). Therefore, \(c\) is a common divisor of \(a\) and \(b\) if and only if it is a common divisor of \(b\) and \(r\), so the greatest common divisors of each pair are equal.
An example of the Euclidean algorithm is computing \(\operatorname{GCD}(252, 105)\) as follows.
The second entry is now \(0\), so \(\operatorname{GCD}(252, 105) = \operatorname{GCD}(21, 0) = 21\).
Problem 1
Write a function named gcd() that accepts two integers \(a\) and \(b\), not both zero.
Compute the greatest common divisor of \(a\) and \(b\) with the Euclidean algorithm: for \(a, b \ge 0\), not both zero,
Use the property \(\operatorname{GCD}(a, b) = \operatorname{GCD}(|a|, |b|)\) to account for cases where \(a\) and/or \(b\) are negative.
Hint: Use either a loop or recursion.
Test Cases
print(gcd(21, 0))
print(gcd(0, 21))
print(gcd(252, 105))
print(gcd(105, 252))
print(gcd(252, -105))
21
21
21
21
21
print(gcd(12345, 67890))
print(gcd(-56, 98))
print(gcd(112233, 445566))
15
14
33
Common Multiples¶
A multiple of an integer \(n\in\mathbb{Z}\) is any integer of the form \(kn\) for some \(k\in\mathbb{Z}\). If \(a,b\in\mathbb{Z}\) are nonzero, their least common multiple (LCM), written \(\operatorname{LCM}(a, b)\), is the smallest positive integer that is a multiple of both \(a\) and \(b\). The LCM is related to the GCD by the simple formula
If exactly one of \(a\) and \(b\) is zero, then \(\operatorname{LCM}(a, b) = 0\); because \(\operatorname{GCD}(0, 0)\) is undefined, neither is \(\operatorname{LCM}(0, 0)\).
Problem 2
Write a function named lcm() that accepts two integers \(a\) and \(b\), not both zero.
Use the formula \(\operatorname{LCM}(a, b) = |ab| / \operatorname{GCD}(a, b)\) and the gcd() function from Problem 1.
Use integer division so the least common multiple is returned as an integer.
Test Cases
print(lcm(0, 6))
print(lcm(4, 6))
print(lcm(-12, 18))
print(lcm(123456789, 987654321))
0
12
36
13548070123626141