Extended Euclidean Algorithm
Bézout's identity states that there are integers such that
The extended Euclidean algorithm finds the GCD together with these coefficients. The coefficients may be negative even when are nonnegative.
If , choose and . Then .
Otherwise, recursively solve the pair . Suppose the call returns satisfying
Let . Substituting gives
Therefore, the coefficients for are
The base case and this recurrence construct Bézout coefficients, proving the identity.
An inverse modulo is a value satisfying
An inverse exists exactly when .
If an inverse exists, for some integer . Any common divisor of must divide , so their GCD is .
Conversely, when the GCD is , extended Euclid finds . Reducing this identity modulo shows that its coefficient is an inverse. Normalize it to the range .
A linear Diophantine equation asks for integer solutions to
First handle : every pair is a solution if , and no solution exists otherwise.
For the remaining cases, let . A solution exists exactly when .
Necessity follows because divides both terms on the left. For sufficiency, take Bézout coefficients and multiply them by . This produces one solution .
All solutions are
Substitution shows that every such pair works. To prove that these are all solutions when , subtract the equations for two solutions:
Since and are coprime, divides . Write , which forces .
If exactly one coefficient is zero, the other fixes one variable and leaves the second arbitrary. The same formula describes those solutions.
The function returns the GCD and writes its Bézout coefficients into using references. For the stated input range, these coefficients and recurrence updates fit in .
The function requires and returns the inverse in , or if none exists.
The function accepts any signed 64-bit . It returns whether a solution exists and, on success, writes one solution into . Scaling can exceed , so this helper uses , the GNU C++17 signed 128-bit integer type.
Extended Euclid follows the same remainder steps as Euclid's algorithm. It takes time and recursive stack space. Finding one equation solution has the same bound. Computing a modular inverse takes time and stack space.
#include <bits/stdc++.h>
using namespace std;
using i128 = __int128_t;
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long x1, y1;
long long g = ext_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
long long inverse(long long a, long long m) {
long long x, y;
if (ext_gcd(a % m, m, x, y) != 1) {
return -1;
}
x %= m;
if (x < 0) {
x += m;
}
return x;
}
bool find_solution(long long a, long long b, long long c, i128 &x, i128 &y) {
if (a == 0 && b == 0) {
x = y = 0;
return c == 0;
}
long long x0, y0;
long long g = ext_gcd(a, b, x0, y0);
if (c % g != 0) {
return false;
}
i128 k = (i128)c / g;
x = (i128)x0 * k;
y = (i128)y0 * k;
return true;
}