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