divisibility
This study of integers begins with the notion of divisibility: whether the division of two integers results in an integer. Because of the volatile nature of division, we frame this question in terms of integer multiplication.
A nonzero integer \( b \) divides an integer \( a \) if there exists some integer \( n \) such that \( a = bn \).
Here are a few examples:
 15 divides 45 since \( 45 = 15 \cdot 3 \)
 9 divides 45 since \( 45 = 9 \cdot 5 \)
 10 does not divide 45 since 45 is between \( 40 = 10 \cdot 4 \) and \( 50 = 10 \cdot 5 \)
The above definition is synonymous with saying that \( b \) may be expressed as a multiple of \( a \). In fact, the following statements are equivalent and mean that \( a \) is can be expressed as \( bn \).
 \( b \) divides \( a \)
 \( b \) is a divisor of \( a \)
 \( a \) is divisible by \( b \)
 \( a \) is a multiple of \( b \)
The notation for this concept is \( b \mid a \), which reads "\( b \) divides \( a \)". Using this notation, the examples above become:
 \( 15 \mid 45 \) since \( 45 = 15 \cdot 3 \)
 \( 9 \mid 45 \) since \( 45 = 9 \cdot 5 \)
 \( 10 \nmid 45 \) since \( 10 \cdot 4 < 45 < 10 \cdot 5 \)
Be careful! This notation may sometimes be confused with the division operation. If you see \( 15 / 45 \), it is the operation that returns the rational number \( 1/3 \). If you see \( 15 \mid 45 \), it is the statement that \( 45 \) is divisible by \( 15 \), ie, that \( 45 / 15 \) is an integer.
exercise. Using only addition, multiplication, and comparison, write a
divides
function that takes as input two positive integersb
anda
and returnstrue
ifb
dividesa
andfalse
otherwise.
With such a divides?
function in ruby, the following code should yield the
terminal output below.
[
[25, 0],
[31, 432],
[87, 87*58],
[99, 9900],
[9900, 99],
].each do (b, a)
if divides?(b, a)
puts "#{b} divides #{a}"
else
puts "#{b} does not divide #{a}"
end
end
25 divides 0
31 does not divide 432
87 divides 5046
99 divides 9900
9900 does not divide 99
Click the button below to show an implementation of a simple divides?
function in ruby.
linear combinations
An integer linear combination of integers \( a \) and \( b \) is an integer of the form \( ax + by \) where \( x \) and \( y \) are integers.
For example, 11 through 15 can all be expressed as linear combinations of 5 and 6. Here are two examples of each.
\[\begin{align} 5(1) + 6(1) &= 11 = 5(7) + 6(4) \\ 5(0) + 6(2) &= 12 = 5(6) + 6(3) \\ 5(1) + 6(3) &= 13 = 5(5) + 6(2) \\ 5(2) + 6(4) &= 14 = 5(4) + 6(1) \\ 5(3) + 6(5) &= 15 = 5(3) + 6(0) \\ \end{align}\]
The following proposition about integer linear combinations will be used often.
proposition 1. If \( d \) is a common divisor of \( a \) and \( b \), then \( d \) divides any integer linear combination of \( a \) and \( b \).
proof: Suppose that \( d \) divides \( a \) and \( b \). By definition, there exist integers \( m, n \) such that \( a = dm \) and \( b = dn \). Let \( c = ax + by \) be an integer linear combination of \( a \) and \( b \). For any linear combination \( ax + by \), \[ ax + by = (dm)x + (dn)y = d(mx + ny). \] Since \( mx + ny \) is an integer, the linear combination is divisible by \( d \).
exercises

Prove that any nonzero integer divides 0.

Prove that 1 and 1 divide any integer.

Prove that any nonzero integer divides itself.

If \( a \) and \( b \) are positive integers and \( b \) divides \( a \), prove that \( b \le a \).

Prove that two positive integers that divide each other must be equal.

Prove that the divides relation is transitive: if \( c \mid b \) and \( b \mid a \), prove that \( c \mid a \).

If \( d \) divides both \( a \) and \( b \), prove that \( d \) divides their sum \( a + b \).

Disprove the converse of the previous exercise by producing a counterexample.

If \( d \) divides either \( a \) or \( b \), prove that \( d \) divides their product \( ab \).

Disprove the converse of the previous exercise by producing a counterexample.
division with remainder
In the divides function from the last
section, we employed a while
loop. The eventual termination of the loop
depends on the following principle.
Archimedes' principle. For an integer \( a \) and a nonzero integer \( b \), there exists a multiple of \( b \) which is greater than or equal to \( a \).
This principle is equivalent to the division algorithm, which we will prove.
proposition 2 (division algorithm). For an integer \( a \) and a nonzero integer \( b \), there are unique integers \( q \) and \( r \) such that \( a = bq + r \) and \( 0 \le r < b. \)
Terminology:
 \( a \) is called the dividend.
 \( b \) is called the divisor.
 \( q \) is called the quotient.
 \( r \) is called the remainder.
Before proving the division algorithm, here are a few examples.
 Dividing \( 71 \) by \( 20 \) gives \( 71 = 20(3) + 11 \)
 Dividing \( 71 \) by \( 20 \) gives \( 71 = 20(3) + 11 \)
 Dividing \( 71 \) by \( 20 \) gives \( 71 = 20(4) + 9 \)
 Dividing \( 71 \) by \( 20 \) gives \( 71 = 20(4) + 9 \)
proof of division algorithm: If \( a \ge 0 \), consider the set \( S \), consisting of integers of the form \( a  bn \) where \( n \) is an integer, ie, \[ S = { a  bn: n \in \mathbf{Z} }. \] The intersection of \( S \) the with nonnegative integers is nonempty, since \( a \) itself is nonnegative. By the wellordering principle, there must be a unique smallest nonnegative element of \( S \), say \( r = a  bq \). Since \( r  b \) is a smaller element of \( S \), it must be negative, hence \( r < b \).
If \( a < 0 \), then \( a \) is positive, which was proven above to be expressable as \( a = bQ + R. \) If \( R = 0 \), set \( q = Q \) and \( r = 0. \) Otherwise, set \( r = R + b \) and \( q = Q  b / b. \) In either case, we have \[ a = bQ  R = bq + r \] with \( 0 \le r < b. \)
in code
In most programming languages, the implementation of a division and remainder (modulus) operator likely will not match the specification given by the division algorithm: when the dividend or divisor is negative, it may result in a negative remainder.
In ruby, for example, integer division is floor division, so the quotient
a / b
is computed by rounding down the rational number \( a / b \).
Therefore, the sign of the remainder a % b
is the same as the sign of the
divisor b
.
a  b  a / b  a % b 

71  20  3  11 
71  20  4  9 
71  20  4  9 
71  20  3  11 
In rust, on the other hand, integer division is truncation, so the quotient
a / b
is computed by rounding the rational number \( a / b \) toward zero.
Therefore, the sign of the remainder a % b
is the same as the sign of the
dividend a
.
a  b  a / b  a % b 

71  20  3  11 
71  20  3  11 
71  20  3  11 
71  20  3  11 
exercise: Write a
div_rem
function that takes a dividenda
and a nonzero divisorb
as inputs, and outputs a quotientq
and a remainderr
satisifying the division algorithm.
The division algorithm itself gives the specifications to validate that
div_rem
is implemented correctly. Following is a test in ruby that asserts
the properties from the division algorithm for some test inputs. Note that I
am specifically suppressing test inputs where the arguments could be zero since
div_rem(a, b)
is undefined when b == 0
.
def test_div_rem
test_inputs(:include_zero => false).each do (a, b)
quo, rem = div_rem(a, b)
assert 0 <= rem
assert rem < b.abs
assert_equal a, b*quo + rem
end
end
Click the expand button to see an implementation of div_rem
in ruby.
divisibility and remainders
The division algorithm is an extension of the idea of divisibility, as this proposition makes clear.
proposition 3. A nonzero integer \( b \) divides an integer \( a \) if and only if the division of \( a \) by \( b \) yields a remainder of \( 0 \).
proof: If the division algorithm gives \( a = bq + r \) with \( r = 0\), then \( a = bq \), which implies the \( b \mid a \).
Conversely, if \( b \mid a \), then \( a = bn \) for some \( n \). Since the division algorithm produces a unique quotient and remainder, it must be true that \( q = n \) and \( r = 0 \).
exercises
Compute by hand the quotient and remainder when dividing:

\( 345 \) by \( 14 \)

\( 872 \) by \( 77 \)

\( 7373 \) by \( 205 \)

\( 762 \) by \( 11 \)
greatest common divisor
A common divisor of two integers is an integer that divdes both integer. The greatest common divisor of two integers 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, nil
is returned when the inputs are both zero. You may opt
to do some error handling instead a null return value.
def test_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)
[[10, 0], [10, 0]].each do (a, b)
assert_equal 10, gcd(a, b)
assert_equal 10, gcd(b, a)
end
[[6, 3], [6, 3], [6, 3], [6, 3]].each do (a, b)
assert_equal 3, gcd(a, b)
assert_equal 3, gcd(b, a)
end
[[322, 70], [322, 70], [322, 70], [322, 70]].each do (a, b)
assert_equal 14, gcd(a, b)
assert_equal 14, gcd(b, a)
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 \).

Prove that every common divisor of two integers divides their greatest common divisor. (Hint: look over the proof of proposition 4.)

Benchmark
gcd
vsnaive_gcd
to convince yourself of the stated time complexity.
bezout's identity
proposition 6 (Bezout's identity). The greatest common divisor can always be expressed as a linear combination of the two integers. In other words, given two integers \( a \) and \( b \), there exist integers \( x \) and \( y \) such that \( ax + by = \gcd(a, b) \).
The proof of this is constructive and most easily understood through a few examples.
example 1
For example, if \( a = 322 \) and \( b = 70 \), Bezout's identity implies that \( 322x + 70y = 14 \) for some integers \( x \) and \( y \). Such integers might be found by brute force. In this case, a brute force search might arrive at the solution \( (x, y) = (2, 9) \). However, the Euclidean algorithm provides an efficient way to find a solution.
The first division yields \( 322 = 70(4) + 42 \) with a quotient of \( q_0 = 4 \) and a remainder of \( r_0 = 42 \). Solving for \( r_0 \) gives \( 42 = 322  70(4) \). In particular, we have shown that the remainder \( r_0 \) can be expressed as a linear combination of \( 322 \) and \( 70 \), namely \( r_0 = 322(1) + 70(4) \).
The second division yields \( 70 = 42(1) + 28 \) with a quotient of \( q_1 = 1 \) and a remainder of \( r_1 = 28 \). Solving for \( r_1 \) gives \( 28 = 70  42(1) \). The linear combination for \( r_0 = 42 \) may be substituted here and simplified to \( 28 = 322 + 70(5) \). Therefore, the remainder \( r_1 = 322(1) + 70(5) \) is also a linear combination of the original two integers.
The third division gives \( 42 = 28(1) + 14 \) with a quotient of \( q_2 = 1 \) and a remainder of \( r_2 = 28 \). The linear combinations for \( r_0 = 42 \) and \( r_1 = 28 \) may be substituted into this expression. Then solving for the new remainder, it will simplify to \( 14 = 322(2) + 70(9) \), which is the solution to Bezout's identity that was listed above.
These computations are summarized in the table below. In each of the first three rows, the last column is how to express each remainder \( r \) as a linear combination of the original \( a = 322 \) and \( b = 70 \), namely, \( r = 322x + 70y \). The last row verifies that the algorithm has terminated, ie, that the gcd of \( 322 \) and \( 70 \) is the secondtolast remainder \( 14 \).
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 322 \)  \( 70 \)  \( 42 \)  \( 4 \)  \( (1, 4) \) 
\( 70 \)  \( 42 \)  \( 28 \)  \( 1 \)  \( (1, 5) \) 
\( 42 \)  \( 28 \)  \( 14 \)  \( 1 \)  \( (2, 9) \) 
\( 28 \)  \( 14 \)  \( 0 \)  \( 2 \) 
We would like a programatic way to compute the \( (x, y) \) pairs as we go. Suppose that on some row we have \( a' = b'q + r \) and that we have already calculated that \( a' = 322 x_0 + 70 y_0 \) and \( b' = 322 x_1 + 70 y_1 \). We can substitute these expressions into the division algorithm equation to get \[ 322 x_0 + 70 y_0 = (322 x_1 + 70 y_1)q + r. \] Solving for \( r \) and rearranging, we get \[ r = 322 (x_0  x_1 q) + 70(y_0  y_1 q). \]
This is great news, because we can compute the the next \( (x, y) \)
pair from the previous two pairs. The recursive relation for both \( x \)
and \( y \) can be expressed as
\[ u_2 = u_0  u_1 \cdot q. \]
In other words, the next_value = previous_value  current_value * quotient
.
To see this in action, we observe first that \( a = a(1) + b(0) \) and \( b = a(0) + b(1) \), so the initial values for the \( (x, y) \) pairs are \( (1, 0) \) and \( (0, 1) \).
The first quotient is \( q = 4 \), so the first \( (x, y) \) pair is \[ (1, 0)  (0, 1) \cdot 4 = (1  0, 0  4) = (1, 4). \] (Note that we used vector addition and scalar multiplication to express this succinctly.) The second quotient is \( q = 1 \), so the second pair is \[ (0, 1)  (1, 4) \cdot 1 = (0  1, 1 + 4) = (1, 5). \] The third quotient is \( q = 1 \), so the third pair is \[ (1, 4)  (1, 5) \cdot 1 = (1 + 1, 4  5) = (2, 9). \] Since the following remainder is \( 0 \), the algorithm terminates.
example 2
Here is another example to illustrate this process. Suppose we want to find a solution to \( 5831 x + 482 y = \gcd(5831, 482) \). We seed our table with the initial \( (x, y) \) pairs and with \( a \) and \( b \) as the first "remainders".
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 5831 \)  \( (1, 0) \)  
\( 482 \)  \( (0, 1) \) 
The division of \( 5381 \) by \( 482 \) yields \( 5831 = 482(12) + 47 \). Since the quotient is \( q = 12 \), we calculate the next \( (x, y) \) pair to be \[ (1, 0)  (0, 1) \cdot 12 = (1  0, 0  12) = (1, 12) \] and we fill in the new row on the table.
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 5831 \)  \( (1, 0) \)  
\( 482 \)  \( (0, 1) \)  
\( 5831 \)  \( 482 \)  \(47 \)  \( 12 \)  \( (1, 12) \) 
The division of \( 482 \) by \( 47 \) yields \( 482 = 47(10) + 12 \). Since the quotient is \( q = 10 \), we calculate the next \( (x, y) \) pair to be \[ (0, 1)  (1, 12) \cdot 10 = (0  10, 1 + 120) = (10, 121) \] and we fill in the new row on the table.
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 5831 \)  \( (1, 0) \)  
\( 482 \)  \( (0, 1) \)  
\( 5831 \)  \( 482 \)  \(47 \)  \( 12 \)  \( (1, 12) \) 
\( 482 \)  \( 47 \)  \(12 \)  \( 10 \)  \( (10, 121) \) 
The division of \( 47 \) by \( 12 \) yields \( 47 = 12(3) + 11 \). With a quotient of \( q = 3 \), the next \( (x, y) \) pair is \[ (1, 12)  (10, 121) \cdot 3 = (1 + 30, 12  363) = (31, 375) \] and we fill in the new row on the table.
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 5831 \)  \( (1, 0) \)  
\( 482 \)  \( (0, 1) \)  
\( 5831 \)  \( 482 \)  \(47 \)  \( 12 \)  \( (1, 12) \) 
\( 482 \)  \( 47 \)  \(12 \)  \( 10 \)  \( (10, 121) \) 
\( 47 \)  \( 12 \)  \(11 \)  \( 3 \)  \( (31, 375) \) 
The division of \( 12 \) by \( 11 \) yields \( 12 = 11(1) + 1 \). With a quotient of \( q = 1 \), the next pair is \[ (10, 121)  (31, 375) \cdot 1 = (10  31, 121 + 375) = (41, 496) \] and we fill in the new row.
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 5831 \)  \( (1, 0) \)  
\( 482 \)  \( (0, 1) \)  
\( 5831 \)  \( 482 \)  \(47 \)  \( 12 \)  \( (1, 12) \) 
\( 482 \)  \( 47 \)  \(12 \)  \( 10 \)  \( (10, 121) \) 
\( 47 \)  \( 12 \)  \(11 \)  \( 3 \)  \( (31, 375) \) 
\( 12 \)  \( 11 \)  \(1 \)  \( 1 \)  \( (41, 496) \) 
The final division of \( 11 \) by \( 1 \) yields \( 11 = 1(11) + 0 \). With a remainder of \( 0 \), the algorithm has terminated. The greatest common divisor is \( \gcd(5831, 482) = 1 \) and \( (41, 496) \) is a solution to \( 5831 x + 482 y = 1 \).
in code
The examples above can be generalized into a constructive proof of Bezout's identity  the proof is an algorithm to produce a solution.
Bezout algorithm for positive integers. Given positive integers
a
andb
, we want to find integersx
andy
such thata * x + b * y == gcd(a, b)
. Initially setprev = [1, 0]
andcurr = [0, 1]
.
 If
b == 0
, returnprev
. Calculate
q, r = div_rem(a, b)
. Calculate
x = prev[0]  curr[0] * q
andy = prev[1]  curr[1] * q
. Replace
a, b
withb, r
. Replace
prev, curr
withcurr, [x, y]
. Return to Step 1.
The algorithm needs to be adjusted slightly for zero or negative values. Run
the algorithm described for various combinations of positive, negative, and
zero values, checking whether each resulting pair x, y
actually satisfies
a * x + b * y == gcd(a, b)
.
While exploring zero/negative values, there are 3 cases to consider:
 when the algorithm returns immediately, ie, when the original
b
is zero.  when the algorithm returns after one iteration, ie, when the first remainder
r
is zero.  when the algorithm returns after two or more iterations.
We seeded the algorithm initially with prev = [1, 0]
and curr = [0, 1]
.
We did this in order to express a
and b
in terms of themselves, ie,
a == 1 * a + 0 * b
and b == 0 * a + 1 * b
. With two or more iterations,
the division algorithm guarantees that the remainder is positive, so the
calculated pair at that point gives a positive number a * x + b * y
.
However, if the algorithm terminates during the first or second iteration, we
would return either [1, 0]
or [0, 1]
, in which case we may end up with
a * x + b * y
as a negative value, which would be incorrect since the
greatest common divisor is always positive.
To account for this, we may need to negate the values of prev
in Step 1
before returning. Consider these two examples.

Let
a = 10
andb = 0
. Sinceb == 0
, we return the originalprev = [1, 0]
immediately. Notice that1 * 10 + 0 * 0 == 10
whilegcd(10, 0) == 10
. In this case, we need to return the originalprev
but with negated values, ie,[1, 0]
. 
Let
a = 10
andb = 5
. Sinceb != 0
, we calculateq = 2
andr = 0
. When we return to Step 1, we havenew_b = r == 0
, so we returnnew_prev = curr == [0, 1]
. Notice that0 * 10 + 1 * 5 = 5
whilegcd(10, 5) == 5
. In this case, we need to return thenew_prev
but with negated values, ie,[0, 1]
.
The conclusion is that Step 1 requires the following adjustment:
 If
b == 0
, returnprev
ifa > 0
, otherwise returnprev
with negated values.
exercise. Write a
bezout
function that takes integer inputs(a, b)
and produces integers(x, y)
such thata * x + b * y = gcd(a, b)
.
Testing this function is very simple: regardless of the inputs, Bezout's identity must be satisfied. Make sure you include test inputs for the special cases discussed above.
def test_bezout
test_inputs.each do (a, b)
x, y = bezout(a, b)
assert_equal gcd(a, b), a * x + b * y
end
end
def test_bezout_explicit
assert_nil bezout(0, 0)
end
applications of bezout's identity
Bezout's identity is a powerful tool since it gives a relationship between integers to their greatest common divisor. Some proofs can be vastly simplified by leveraging this new capability. Here are a few propositions that can be proved using Bezout's identity.
proposition 9. The greatest common divisor of two integers is divisible by any common divisor.
proof: Let \( k \) be a common divisor of \( a, b \) and let \( d \) be their greatest common divisor. Bezout's lemma allows us to write \( ax + by = d \) for some integers \( x, y \). Since \( k \) divides both \( a \) and \( b \), it divides the linear combination \( ax + by \), which is equal to \( d \).
proposition 10. If an integer \( c \) divides a product \( ab \) and \( \gcd(a, c) = 1 \), then \( c \) divides \( b \).
proof: Since \( \gcd(a, c) = 1 \), then we can write \( ax + cy = 1 \) for some integers \( x, y \). Multiplying both sides by \( b \), we get \[ abx + bcy = b. \] The first term is divisible by \( c \), since \( c \) is assumed to divide the product \( ab \). The second term is divisible by \( c \) since \( c \) occurs in that term. Therefore, their sum is divisible by \( c \), which proves that \( b \) is divisible by \( c \).
least common multiple
A common multiple of two integers is an integer divisible by both integers. The least common multiple of two integers is the smallest positive common multiple.

The notation for the least common multiple of \( a \) and \( b \) is \( \operatorname{lcm}(a, b) \).

By definition, the least common multiple of two integers is independent of the sign of the two integers  the \( \operatorname{lcm} \) is the same if you replace \( a \) with \( a \) or \( b \) with \( b \).

The definition of \( \operatorname{lcm} \) does not make sense if either \( a \) or \( b \) are is equal to \( 0 \).

For the remainder of the section, we will assume integers to be nonzero.
The existence of a least common multiple stems from the fact that the absolute value of the product \( ab \) is a positive common multiple of \( a \) and \( b \).
naive computation
The least common multiple can be computed naively by checking every multiple of one of them up to their product to see if it is divisible by the other. For example, to compute \( \operatorname{lcm}(154, 56) \)

start with \( 154 \) and keep adding \( 154 \) until it is divisible by \( 56 \)

\( 56 \) does not divide \( 154 \), \( 154(2) \), or \(154(3) \)

however, \( 154(4) = 616 = 56(11) \) is divisible by \( 56 \)

the least common multiple is \( \operatorname{lcm}(154, 56) = 616 \)
exercise. Write a
naive_lcm
function that returns the least common multiple of two nonzero integer inputs. It should only rely on divisibility checks.
The time complexity of this algorithm, similar to the naive gcd algorithm, grows linearly in the smaller of the two arguments.
a property of the lcm
proposition 7. Every common multiple of two integers is a multiple of their least common multiple.
proof: Let \( k \) be a common multiple of \( a \) and \( b \) and let \( m \) be their least common multiple. Dividing \( k \) by \( m \) yields \( k = mq + r \), where \( 0 \le r < m \). Since \( r = k  mq \) is a linear combination of \( k \) and \( m \), then \( r \) must be divisible by both \( a \) and \( b \), ie, \( r \) must be a common multiple of \( a \) and \( b \). If \( r \) were nonzero, then it would be a smaller positive common multiple than the least common multiple, a contradiction. Therefore, \( r = 0 \) and \( m \mid k \).
relation to greatest common divisor
In order to compute the least common multiple efficiently, we need to prove an identity involving the greatest common divisor.
proposition 8. If \( a \) and \( b \) are nonzero integers, then \( \gcd(a, b) \cdot \operatorname{lcm}(a, b) = \vert ab \vert \).
proof: For simplicity, we may assume that \( a \) and \( b \) are positive, since both the gcd and the lcm are independent of sign. Define \( d = \gcd(a, b) \) and \( m = \operatorname{lcm}(a, b) \). The goal is to prove that \( md = ab \).
Since \( d \) is a common divisor of \( a, b\), the integer \( ab/d \) can be expressed as \( (a/d) \cdot b \) or as \( a \cdot (b/d) \). This implies that \( ab/d \) must be a common multiple of \( a \) and \( b \). By proposition 7, \( ab/d \) must be a multiple of \( m \), hence \[ ab/d = mk \quad\implies\quad ab = mdk \quad\implies\quad md \mid ab. \]
Next, using Bezout's identity, there exist integers \( x, y \) such that \( d = ax + by \). Multiplying both sides by \( m \) yields \[ md = amx + bmy. \] Since \( b \mid m \), it follows that \( ab \mid am \), so it divides the first term. Since \( a \mid m \), it follows that \( ab \mid bm \), so it also divides the second term. Therefore, \( ab \) divides the whole expression, which implies that \( ab \mid md \).
Since each of \( md \) and \( ab \) is positive and divides the other, they must be equal.
in code
exercise. Write an
lcm
function that returns the least common multiple of two nonzero integer inputs. It should use thegcd
function and proposition 8.
For testing, we can compare the result to the naive_lcm
result. Be careful
to limit this type of test to just a few positive values since the naive
function is slow and restricted. For more general test cases, we'll use the
proposition, even though we also rely on the proposition for the
implementation.
def test_lcm_against_naive
test_inputs(
:include_zero => false,
:include_negative => false,
:include_reverse => false
).each do (a, b)
assert_equal naive_lcm(a, b), lcm(a, b)
end
end
def test_lcm
test_inputs(:include_zero => false).each do (a, b)
assert_equal (a * b).abs, gcd(a, b) * lcm(a, b)
end
end
def test_lcm_explicit
[[5, 0], [0, 5], [0, 0]].each do (a, b)
assert_nil lcm(a, b)
end
end
linear equations
In this section, we discuss finding integer solutions to integer linear equations. An integer linear equation in two variables \( x, y \) is of the form \[ ax + by = c \] where \( a, b, c \) are given integers. We are interested in finding, if possible, integers \( x, y \) that satisfy the equation.
The linear equation \( ax + by = c \) defines a line in the plane. As such, there are infinitely many real solutions, for example \( (x, y) = (\frac{c}{a}, 0) \). It is not readily apparent under what conditions there exist points on the line with integer coordinates.
existence of a solution
proposition 11. Given integers \( a, b, c \), there exist integers \( x, y \) such that \( ax + by = c \) if and only if \( c \) is divisible by \( \gcd(a, b) \).
proof: Suppose that \( ax + by = c \) for some integers \( x, y \). Since \( c \) is a linear combination of \( a \) and \( b \), then proposition 1 implies that \( c \) is divisible by any common divisor of \( a, b \). In particular, \( c \) is divisible by their greatest common divisor.
On the other hand, suppose that \( c \) is divisible by \( d = \gcd(a, b) \). Then \( c = k d \) for some integer \( k \). By Bezout's identity, there exist integers \( u, v \) such that \( au + bv = d \). Multiplying both sides by \( k \), we have \[ a(ku) + b(kv) = k d = c, \] hence \( (x, y) = (ku, kv) \) is an integer solution to \( ax + by = c \).
This is a constructive proof: if a solution exists, it gives a mechanism to find a solution.
example
Suppose we want to solve \( 322 x + 70 y = 126 \).

Compute
gcd(322, 70) ~> 14
. 
Compute
div_rem(126, 14) ~> [9, 0]
and conclude that a solution exists since \( 126 = 14 \cdot 9 \). 
Compute
bezout(322, 70) ~> [2, 9]
to get the equation \( 322(2) + 70(9) = 14 \). 
Scale this equation by a factor of \( 9 \) to get \( 322(18) + 70(81) = 126 \).
Therefore, one solution is \( (x, y) = (18, 81) \).
parametrization of solutions
proposition 12. Given integers \( a, b, c \), if there exists an integer solution to the linear equation \( ax + by = c \), then there exist infinitely many solutions. Moreover, the set of all solutions may be obtained from a single solution \( (x_0, y_0) \) by taking all pairs of the form \[ x = x_0 + \tfrac{b}{d} k, \quad y = y_0  \tfrac{a}{d} k \] where \( k \) is any integer and \( d = \gcd(a, b) \).
Before giving a formal proof, let's talk about the intuition behind these additional solutions. As mentioned above, the equation \( ax + by = c \) identifies a line in the plane. Solving for \( y \), we get \[ y = \tfrac{a}{b}x + c, \] so the slope of this line is the rational number \( \tfrac{a}{b} \). If \( d = \gcd(a, b) \), then the reduced form of the slope is \( \tfrac{ a/d }{ b/d } \). If there is an integer point \( (x_0, y_0) \) on the line, then we can use this slope to find the "next" integer point. Since the slope is the change in \( y \) divided by the change in \( x \), that means we can add \( \tfrac{b}{d} \) to the \( x \)value and subtract \( \tfrac{a}{d} \) from the \( y \)value to get the "next" integer point. To get all integer points, we apply this same process in both directions indefinitely.
example
Continuing the example from above of \( 322 x + 70 y = 126 \), the corresponding line in slopeintercept form is \[ y = \tfrac{322}{70} x + \tfrac{126}{70} = \tfrac{23}{5} x + \tfrac{9}{5}. \] We already found a base solution of \( (18, 81) \). So, according to this proposition, every solution is of the form \[ x = 18 + 5k, \quad y = 81  23k \] where \( k \) can be any integer. For instance, the solutions closest to the origin occur when \( k = 3, 4 \), ie, at \[ (3, 12) \quad \text{ and } \quad (2, 11). \]
proof of proposition 12: Supposing we have two solutions to \( ax + by = c \), say \( (x_0, y_0) \) and \( (x_1, y_1) \), then \[ a x_1 + b y_1 = c = a x_0 + b y_0. \] Moving the \( x \)'s and \( y \)'s to opposite sides, we get \[ a (x_1  x_0) = b (y_0  y_1). \] Both sides are divisible by \( d = \gcd(a, b) \), therefore \[ \tfrac{a}{d} (x_1  x_0) = \tfrac{b}{d} (y_0  y_1) \] is an integer equation. This means that the integer \( \tfrac{b}{d} \) must divide the product \( \tfrac{a}{d} (x_1  x_0) \). By proposition 5, we know that \( \gcd(\tfrac{a}{d}, \tfrac{b}{d}) = 1 \). Therefore, proposition 10 guarantees that the integer \( \tfrac{b}{d} \) must divide \( x_1  x_0 \). In other words, there is an integer \( k \) such that \[ x_1  x_0 = \tfrac{b}{d} k \quad \implies \quad x_1 = x_0 + \tfrac{b}{d} k. \] Plugging the first version of this equation into the lefthand side above, we get \[ \tfrac{a}{d} \cdot \tfrac{b}{d} k = \tfrac{b}{d} (y_0  y_1) \] which simplifies to \[ \tfrac{a}{d} k = y_0  y_1 \quad \implies \quad y_1 = y_0  \tfrac{a}{d} k. \] This proves that any additional solution \( (x_1, y_1) \) is of the form prescribed by the proposition.
To finish the proof, it remains to show that pairs of that form are always solutions. Let \( k \) be any integer and define \( x_1 = x_0 + \tfrac{b}{d} k \) and \( y_1 = y_0  \tfrac{a}{d} k \). Then, \[ a x_1 + b y_1 = a(x_0 + \tfrac{b}{d} k) + b(y_0  \tfrac{a}{d} k) = a x_0 + b y_0. \] Therefore, if \( (x_0, y_0) \) is a solution, then so is \( (x_1, y_1) \).
in code
exercise. Write some code that takes integer inputs
(a, b, c)
and computes integer solutions(x, y)
toa * x + b * y = gcd(a, b)
.
I opted to write a LinearEquationSolver
class in ruby. Perhaps your solution
will have very different structure. With the syntax I chose, the computations
from the examples could be accomplished as follows.
solver = LinearEquationSolver.new(322, 70, 126)
solver.base_solution
# ~> [18, 81]
solver.solution(3)
# ~> [3, 12]
solver.solution(4)
# ~> [2, 11]
I have two tests: one for when there are solutions, and one for when there are no solutions.
def test_solvable_equation
a, b, c = 12, 15, 99
solver = LinearEquationSolver.new(a, b, c)
# solvable since gcd(12, 15) == 3 && 99 % 3 == 0
assert solver.solvable?
x, y = solver.base_solution
assert_equal c, a*x + b*y
(10..10).each do k
x, y = solver.solution(k)
assert_equal c, a*x + b*y
end
end
def test_unsolvable_equation
a, b, c = 12, 15, 100
solver = LinearEquationSolver.new(a, b, c)
# not solvable since gcd(a, b) == 3 && 100 % 3 == 1
assert !solver.solvable?
assert_nil solver.base_solution
(10..10).each { k assert_nil solver.solution(k) }
end
prime numbers
An integer \( n \ge 2 \) is prime if its only positive divisors are \( 1 \) and \( n \) and composite otherwise.

The positive integer \( 1 \) is considered neither prime nor composite.

The divisors \( 1 \) and \( n \) are called the trivial divisors of \( n \). A nontrivial divisor is a divisor strictly between \( 1 \) and \( n \). So, an integer greater than 1 is prime if it has no nontrivial divisors and composite if it has a trivial divisor.
There are 25 primes up to 100, listed below.
PRIMES_UP_TO_100 = [
2, 3, 5, 7, 11,
13, 17, 19, 23, 29,
31, 37, 41, 43, 47,
53, 59, 61, 67, 71,
73, 79, 83, 89, 97,
]
We will use this list to test the primality testing methods we write later on.
def assert_correct_primality_using(method)
(100..1).each { x assert !send(method, x) }
primes, composites = (2..100).partition { x PRIMES_UP_TO_100.include? x }
primes.each { prime assert send(method, prime) }
composites.each { composite assert !send(method, composite) }
end
naive primality testing
exercise. Write an
is_prime_naive_v1?
function that takes an integer input and returnstrue
if it is prime andfalse
otherwise. It should only use only the definition.
def test_is_prime_naive_v1
assert_correct_primality_using :is_prime_naive_v1?
end
an improvement to naive primality testing
proposition 13. If an integer \( n \ge 2 \) is composite, then it has a divisor \( d \le \sqrt{n} \).
proof: We will prove this by contradiction. Suppose that a number \( n \) is composite and taht is has no divisor less than or equal to its square root. Since it is composite, it may be expressed as \( n = ab \) for some pair of integers \( a, b \). By hypothesis, both of these integers must be greater than \( \sqrt{n} \). Then \[ n = a \cdot b > \sqrt{n} \cdot \sqrt{n} = n, \] which is a contradiction since an integer cannot be greater than itself.
The proposition may also be restated in its contrapositive form.
proposition 13. If an integer \( n \ge 2 \) has no divisor less than or equal to its square root, then it is prime.
This rephrasing results in a substantial speedup to our primality test above.
exercise. Write an improved
is_prime_naive?
function that takes an integer input and returnstrue
if it is prime andfalse
otherwise. It should use both the definition and the proposition.
def test_is_prime_naive
assert_correct_primality_using :is_prime_naive?
end
This algorithm is still quite slow. Its time complexity grows as the square root of the input. We will develop some probabilistic methods that are very fast in a later section.