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.
DIVIDES_TEST_INPUTS = [
[25, 0],
[31, 432],
[87, 87*58],
[99, 9900],
[9900, 99],
]
DIVIDES_TEST_INPUTS.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 and its terminal output.
DIV_REM_TEST_INPUTS = [
[6723, 220],
[2392, 183],
[788, 93],
[5853, 11],
[46 * 82, 82],
]
class TestDivRem < Test::Unit::TestCase
def test_div_rem
DIV_REM_TEST_INPUTS.each do (a, b)
quo, rem = div_rem(a, b)
assert 0 <= rem
assert rem < b.abs
assert_equal a, b*quo + rem
puts "#{a} == #{b} * #{quo} + #{rem}"
end
end
end
6723 == 220 * 30 + 123
2392 == 183 * 14 + 170
788 == 93 * 8 + 44
5853 == 11 * 533 + 10
3772 == 82 * 46 + 0
1 tests, 15 assertions, 0 failures, 0 errors
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 \( 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.