Linear Diophantine Equation¶
A Linear Diophantine Equation (in two variables) is an equation of the general form:
where
In this article, we consider several classical problems on these equations:
- finding one solution
- finding all solutions
- finding the number of solutions and the solutions themselves in a given interval
- finding a solution with minimum value of
The degenerate case¶
A degenerate case that need to be taken care of is when
Analytic solution¶
When
Without loss of generality, assume that
where
When
By the definition of
Algorithmic solution¶
Bézout's lemma (also called Bézout's identity) is a useful result that can be used to understand the following solution.
Let
. Then there exist integers such that . Moreover,
is the least such positive integer that can be written as ; all integers of the form are multiples of .
To find one solution of the Diophantine equation with 2 unknowns, you can use the Extended Euclidean algorithm. First, assume that
If
Now supposed that
Therefore one of the solutions of the Diophantine equation is:
The above idea still works when
Finally, we can implement this idea as follows (note that this code does not consider the case
int gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int x1, y1;
int d = gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) {
g = gcd(abs(a), abs(b), x0, y0);
if (c % g) {
return false;
}
x0 *= c / g;
y0 *= c / g;
if (a < 0) x0 = -x0;
if (b < 0) y0 = -y0;
return true;
}
Getting all solutions¶
From one solution
Let
Now, we should see that adding
Obviously, this process can be repeated again, so all the numbers of the form:
are solutions of the given Diophantine equation.
Since the equation is linear, all solutions lie on the same line, and by the definition of
Finding the number of solutions and the solutions in a given interval¶
From previous section, it should be clear that if we don't impose any restrictions on the solutions, there would be infinite number of them. So in this section, we add some restrictions on the interval of
Let there be two intervals:
Note that if
First, we can find a solution which has minimum value of
Similarly, we can find the maximum value of
Similarly, we can find the minimum value of
The final solution is all solutions with x in intersection of
Following is the code implementing this idea.
Notice that we divide
void shift_solution(int & x, int & y, int a, int b, int cnt) {
x += cnt * b;
y -= cnt * a;
}
int find_all_solutions(int a, int b, int c, int minx, int maxx, int miny, int maxy) {
int x, y, g;
if (!find_any_solution(a, b, c, x, y, g))
return 0;
a /= g;
b /= g;
int sign_a = a > 0 ? +1 : -1;
int sign_b = b > 0 ? +1 : -1;
shift_solution(x, y, a, b, (minx - x) / b);
if (x < minx)
shift_solution(x, y, a, b, sign_b);
if (x > maxx)
return 0;
int lx1 = x;
shift_solution(x, y, a, b, (maxx - x) / b);
if (x > maxx)
shift_solution(x, y, a, b, -sign_b);
int rx1 = x;
shift_solution(x, y, a, b, -(miny - y) / a);
if (y < miny)
shift_solution(x, y, a, b, -sign_a);
if (y > maxy)
return 0;
int lx2 = x;
shift_solution(x, y, a, b, -(maxy - y) / a);
if (y > maxy)
shift_solution(x, y, a, b, sign_a);
int rx2 = x;
if (lx2 > rx2)
swap(lx2, rx2);
int lx = max(lx1, lx2);
int rx = min(rx1, rx2);
if (lx > rx)
return 0;
return (rx - lx) / abs(b) + 1;
}
Once we have
Find the solution with minimum value of ¶
Here,
The idea is similar to previous section: We find any solution of the Diophantine equation, and then shift the solution to satisfy some conditions.
Finally, use the knowledge of the set of all solutions to find the minimum:
Note that
If