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 integers b and a and returns true if b divides a and false 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

  1. Prove that any nonzero integer divides 0.

  2. Prove that 1 and -1 divide any integer.

  3. Prove that any nonzero integer divides itself.

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

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

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

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

  8. Disprove the converse of the previous exercise by producing a counter-example.

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

  10. Disprove the converse of the previous exercise by producing a counter-example.

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 non-empty, since \( a \) itself is nonnegative. By the well-ordering 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.

aba / ba % b
7120311
71-20-4-9
-7120-49
-71-203-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.

aba / ba % b
7120311
71-20-311
-7120-3-11
-71-203-11

exercise: Write a div_rem function that takes a dividend a and a nonzero divisor b as inputs, and outputs a quotient q and a remainder r 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:

  1. \( 345 \) by \( 14 \)

  2. \( -872 \) by \( 77 \)

  3. \( 7373 \) by \( -205 \)

  4. \( -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/ remaindersimplifed 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) \)

  1. If \( b = 0, \) return \( \vert a \vert \).

  2. 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 operatorsimplified 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)

  1. If b == 0 return abs(a).

  2. 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

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

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

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

  4. Benchmark gcd vs naive_gcd to convince yourself of the stated time complexity.