greatest common divisor
A common divisor of two integers \( a \) and \( b \) is an integer \( d \) such that \( d \mid a \) and \( d \mid b. \) The greatest common divisor of \( a \) and \( b \) is their largest positive common divisor.

The notation for the greatest common divisor of \( a \) and \( b \) is \( \gcd(a, b) \).

By definition, the greatest common divisor of two integers is independent of the sign of the two integers  the gcd is the same if you replace \( a \) with \( a \) or \( b \) with \( b \).

The definition of gcd does not make sense if \( a \) and \( b \) are both equal to \( 0 \). The assumption for the rest of the section is that at least one of them is nonzero.
The existence of a greatest common divisor stems from the following fact: every pair of integers has 1 as a positive common divisor, and can only have finitely many positive common divisors since any positive divisor of an integer is less than or equal to its absolute value.
naive computation
The greatest common divisor can be computed naively by finding the positive divisors of each number and taking the intersection of the two sets. For example, to compute \( \gcd(322, 70) \)

the positive divisors of \( 322 \) are \( \{ 1, 2, 7, 14, 23, 46, 161, 322 \} \)

the positive divisors of \( 70 \) are \( \{ 1, 2, 5, 7, 10, 14, 35, 70 \} \)

the positive common divisors of \( 322 \) and \( 70 \) are \( \{ 1, 2, 7, 14 \} \)

therefore, the greatest common divisor is \( \gcd(322, 70) = 14 \)
exercise. Write a
naive_gcd
function that returns the greatest common divisor of two integer inputs. It should only rely on divisibility checks.
Euclidean algorithm
This naive gcd algorithm is slow, growing linearly in the size of the smaller of the two integers. The next proposition is instrumental in developing a more efficient algorithm to compute the gcd.
proposition 4. If \( a = bq + r \), then \( \gcd(a, b) = \gcd(b, r) \).
proof: Since \( a = bq + r \) is a linear combination of \( b \) and \( r \), any common divisor of \( b \) and \( r \) must also be a divisor of \( a \).
Additionally, since \( r = a  bq \) is a linear combination of \( a \) and \( b \), any common divisor of \( a \) and \( b \) must also be a divisor of \( r \).
Taken together, the set of common divisors of \( a, b \) must be equal to the set of common divisors of \( b, r \). Therefore, \( \gcd(a, b) \) must be equal to \( \gcd(b, r) \).
This proposition combined with the division algorithm gives an efficient method for computing the greatest common divisor. Each time we use the division algorithm, this proposition will give a smaller pair of numbers for computing the greatest common divisor, since the division algorithm guarantees that the remainder is smaller than the divisor in absolute value.
The Euclidean algorithm is repeated application of the division algorithm; at each stage, we replace \( a, b \) with \( b, r \) until we reach a remainder of \( 0 \). At that point the gcd is trivial to compute.
As an example, we will calculate \( \gcd(322, 70) \) again, this time using the Euclidean algorithm. The left side of the table has each of the division algorithm steps. The right side has the greatest common divisor simplification resulting from the division algorithm.
division w/ remainder  simplifed gcd 

\( \gcd(322, 70) \)  
\( 322 = 70(4) + 42 \)  \( = \gcd(70, 42) \) 
\( 70 = 42(1) + 28 \)  \( = \gcd(42, 28) \) 
\( 42 = 28(1) + 14 \)  \( = \gcd(28, 14) \) 
\( 28 = 14(2) + 0 \)  \( = \gcd(14, 0) \) 
\( = 14 \) 
In the Euclidean algorithm, the last nonzero remainder is the gcd of the original two integers. Of extreme importance is the fact that the gcd is computed without explicitly finding any of the divisors.
exercise. Write a
euclidean_algorithm
function that prints the division algorithm result from each step.
Running the following code should produce the output below.
euclidean_algorithm(239847, 95832)
239847 == 95832 * 2 + 48183
95832 == 48183 * 1 + 47649
48183 == 47649 * 1 + 534
47649 == 534 * 89 + 123
534 == 123 * 4 + 42
123 == 42 * 2 + 39
42 == 39 * 1 + 3
39 == 3 * 13 + 0
computation of gcd
As mentioned, the Euclidean algorithm gives an algorithm to compute the greatest common divisor. One formulation of this algorithm is the following:
To compute \( \gcd(a, b) \)
If \( b = 0, \) return \( \vert a \vert \).
If \( b \ne 0 \), compute \( a = bq + r \) and return to step 1, replacing the pair \( (a, b) \) with \( (b, r) \).
This gcd algorithm terminates after finitely many steps: since the remainders form a decreasing sequence of positive integers, there can only be finitely many of them.
As mentioned before, in some programming languages, the modulus operator may
return a negative remainder when dealing with negative values. However, the
result of a % b
is still smaller than \( b \) in absolute value, so
repeated applications of the modulus operator will also terminate after
finitely many steps. Since the proposition above applies regardless of whether
\( a = bq + r \) comes from the division algorithm, the greatest common
divisor algorithm may be implemented using only the modulus operator.
For example, here is the same table as above, but instead of performing the whole division algorithm at each stage, we use only the modulus operator.
modulus operator  simplified gcd 

\( \gcd(322, 70) \)  
322 % 70 ~> 42  \( = \gcd(70, 42) \) 
70 % 42 ~> 28  \( = \gcd(42, 28) \) 
42 % 28 ~> 14  \( = \gcd(28, 14) \) 
28 % 14 ~> 0  \( = \gcd(14, 0) \) 
\( = 14 \) 
Here is the same algorithm, rephrased.
To compute
gcd(a, b)
If
b == 0
returnabs(a)
.If
b != 0
, replace(a, b)
with(b, a % b)
and return to step 1.
in code
exercise. Write a
gcd
function that uses the modulus operator: it should take two integer inputs and produce their greatest common divisor. Remember that \( \gcd(0, 0) \) is undefined.
For testing, we will verify some of the essential properties of the greatest
common divisor as well as some specific examples. The last property in the
test is proved in proposition 5 below. In my ruby
implementation tested below, nil
is returned when the inputs are both zero.
You may opt to do some error handling instead a null return value.
GCD_TEST_INPUTS = [
[6723, 220],
[2392, 183],
[788, 93],
[5853, 11],
[46 * 82, 82],
]
class TestGcd < Test::Unit::TestCase
def test_gcd
GCD_TEST_INPUTS.each do (a, b)
d = gcd(a, b)
assert d > 0
assert a % d == 0
assert b % d == 0
assert_equal 1, gcd(a/d, b/d)
end
end
def test_gcd_explicit
assert_nil gcd(0, 0)
assert_equal 5, gcd(5, 0)
assert_equal 5, gcd(5, 0)
assert_equal 5, gcd(0, 5)
assert_equal 5, gcd(0, 5)
assert_equal 3, gcd(6, 3)
assert_equal 3, gcd(6, 3)
assert_equal 3, gcd(6, 3)
assert_equal 3, gcd(6, 3)
assert_equal 14, gcd(322, 70)
assert_equal 14, gcd(322, 70)
assert_equal 14, gcd(322, 70)
assert_equal 14, gcd(322, 70)
end
end
This new algorithm to find the greatest common divisor is extremely fast. It can be proved that it grows logarithmically in the size of the smaller of the two inputs, which is a vast improvement over the linear growth of the naive gcd function we wrote.
a property of the gcd
proposition 5. If \( d = \gcd(a, b) \), then \( \gcd({a \over d}, {b \over d} ) = 1. \)
proof: Let \( k = \gcd({a \over d}, {b \over d}) \). Then \( {a \over d} = km \) and \( {b \over d} = kn \). This implies that \( a = kdm \) and \( b = kdn \), so \( kd \) is a common divisor of \( a \) and \( b \). If \( k \) were larger than \( 1 \), then \( kd \) would be a larger common divisor than the greatest common divisor \( d \), a contradiction.
exercises

Explain why \( \gcd(0, 0) \) is undefined.

If \( a \) is nonzero, prove that \( \gcd(a, 0) = \vert a \vert \).

If \( b \mid a \), prove that \( \gcd(a, b) = \vert b \vert \).

Benchmark
gcd
vsnaive_gcd
to convince yourself of the stated time complexity.