Algorithm to compute solution set of single simple equation with two variables

Question

Suppose I have a simple equation of the form:

7x + 4y = n

where n is chosen by us and x, y and n are all positive integers. This is the only equation which is given to us. Among the possible solutions we need the solution (x,y) in which x is the smallest. e.g.

7x + 4y = 14, then (2, 0) is the solution
7x + 4y = 15, then (1, 2) is the solution
7x + 4y = 32, then (4, 1) and (0, 8) are the possible solutions,
of which (0, 8) is the correct solution

I would like to design an algorithm to calculate it in the least possible running time. The current algorithm which I have in mind goes something like this:

Given an input n
Calculate max(x) = n/7
for i = 0 to max(x)
    If the equation 7*i + 4*y = n holds
        return value of i and y
    else
        continue

This algorithm, I presume, can have a running time of upto O(n) in worst case behaviour. Is there some better algorithm to compute the solution?

Answer 1

Let us consider the more general problem

• For two coprime positive integers a and b, given a positive integer n, find the pair (x,y) of nonnegative integers such that a*x + b*y = n with minimal x. (If there is one. There need not be, e.g. 7*x + 4*y = 5 has no solution with nonnegative x and y.)

Disregarding the nonnegativity for the moment, given any solution

a*x0 + b*y0 = n

all solutions have the form (x0 - k*b, y0 + k*a) for some integer k. So the remainder of x modulo b and of y modulo a is an invariant of the solutions, and we have

a*x ≡ n (mod b), and b*y ≡ n (mod a)

So we need to solve the equation a*x ≡ n (mod b) - the other one follows.

Let 0 < c be an integer with a*c ≡ 1 (mod b). You find it for example by the extended Euclidean algorithm, or (equivalently) the continued fraction expansion of a/b in O(log b) steps. Both algorithms naturally yield the unique c < b with that property.

Then the minimal candidate for x is the remainder x0 of n*c modulo b.

The problem has a solution with nonnegative x and y if and only if x0*a <= n, and then x0 is the minimal nonnegative x appearing in any solution with nonnegtaive x and y.

Of course, for small a and b like 7 and 4, the brute force is no slower than calculating the inverse of a modulo b.

Answer 2

We have

7(x-4)+4(y+7)=7x+4y

So if (x, y) is a solution, then (x-4,y+7) is also a solution. Hence if there is a solution then there is one with x<4. That's why you only need to test x=0..3 which runs in constant time.

This can be extended to any equation of the form ax+by=n, you only need to test x=0..b-1.