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

  [
[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

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 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:

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 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/ 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, 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

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. Prove that every common divisor of two integers divides their greatest common divisor. (Hint: look over the proof of proposition 4.)

5. Benchmark gcd vs naive_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 second-to-last 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 and b, we want to find integers x and y such that a * x + b * y == gcd(a, b). Initially set prev = [1, 0] and curr = [0, 1].

1. If b == 0, return prev.
2. Calculate q, r = div_rem(a, b).
3. Calculate x = prev - curr * q and y = prev - curr * q.
4. Replace a, b with b, r.
5. Replace prev, curr with curr, [x, y].

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:

1. when the algorithm returns immediately, ie, when the original b is zero.
2. when the algorithm returns after one iteration, ie, when the first remainder r is zero.
3. 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.

1. Let a = -10 and b = 0. Since b == 0, we return the original prev = [1, 0] immediately. Notice that 1 * -10 + 0 * 0 == -10 while gcd(-10, 0) == 10. In this case, we need to return the original prev but with negated values, ie, [-1, 0].

2. Let a = 10 and b = -5. Since b != 0, we calculate q = -2 and r = 0. When we return to Step 1, we have new_b = r == 0, so we return new_prev = curr == [0, 1]. Notice that 0 * 10 + 1 * -5 = -5 while gcd(10, -5) == 5. In this case, we need to return the new_prev but with negated values, ie, [0, -1].

The conclusion is that Step 1 requires the following adjustment:

1. If b == 0, return prev if a > 0, otherwise return prev with negated values.

exercise. Write a bezout function that takes integer inputs (a, b) and produces integers (x, y) such that a * 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 the gcd 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$$.

1. Compute gcd(322, 70) ~> 14.

2. Compute div_rem(126, 14) ~> [9, 0] and conclude that a solution exists since $$126 = 14 \cdot 9$$.

3. Compute bezout(322, 70) ~> [2, -9] to get the equation $$322(2) + 70(-9) = 14$$.

4. 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 slope-intercept 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 left-hand 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) to a * 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 non-trivial divisor is a divisor strictly between $$1$$ and $$n$$. So, an integer greater than 1 is prime if it has no non-trivial 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 returns true if it is prime and false 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 speed-up to our primality test above.

exercise. Write an improved is_prime_naive? function that takes an integer input and returns true if it is prime and false 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.