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.

show solutions

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 \).

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

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.

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.

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.

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.

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.

  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

def bezout(a, b)
  return if a == 0 && b == 0

  prev, curr = [[1, 0], [0, 1]]

  while b != 0
    quo, rem = div_rem(a, b)
    nxt = [0, 1].map { |i| prev[i] - curr[i] * quo }

    a, b = b, rem
    prev, curr = curr, nxt
  end

  a < 0 ? prev.map { |u| -u } : prev
end

def naive_lcm(a, b)
  return if a == 0 || b == 0

  smaller, larger = [a, b].map(&:abs).sort

  multiple = larger
  while multiple % smaller != 0
    multiple += larger
  end

  multiple
end

  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

def lcm(a, b)
  return if a == 0 || b == 0

  ((a / gcd(a, b)) * b).abs
end

solver = LinearEquationSolver.new(322, 70, 126)

solver.base_solution
# ~> [18, -81]

solver.solution(-3)
# ~> [3, -12]

solver.solution(-4)
# ~> [-2, 11]

  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

  # class to find integer solutions [x, y] to a*x + b*y == c

  def initialize(a, b, c)
    @a = a
    @b = b
    @c = c

    @d = gcd(a, b)
    @delta_x = b / @d
    @delta_y = -a / @d
    @multiplier, @remainder = div_rem(c, @d)
  end

  def solvable?
    @remainder == 0
  end

  # solution from bezout's identity, if it exists
  def base_solution
    @base_solution ||= bezout(@a, @b).map { |z| z * @multiplier } if solvable?
  end

  # solutions parametrized by an integer k
  def solution(k)
    if solvable?
      x, y = base_solution
      [x + @delta_x * k, y + @delta_y * k]
    end
  end
end

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

  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

  def test_is_prime_naive_v1
    assert_correct_primality_using :is_prime_naive_v1?
  end

def is_prime_naive_v1?(number)
  return false if number < 2
  (2...number).none? { |x| number % x == 0 }

  def test_is_prime_naive
    assert_correct_primality_using :is_prime_naive?
  end

def is_prime_naive?(number)
  return false if number < 2
  (2..).take_while { |x| x**2 <= number }.none? { |x| number % x == 0 }
end