拡張ユークリッド互除法は，$a, b$を整数，$g=\gcd(a,b)$とするとき，次の1次不定方程式 \[ax + by = g\] の解の1つ$(x_0, y_0)$求めるアルゴリズムである。解の1つが得られれば，全ての解は \[x=x_0+k\cdot\frac{b}{g},\ y=y_0-k\cdot\frac{a}{g}, \ \ \ \mbox{（$k$は整数）}\] である。
また，不定方程式$ax + by = c$は$c$が$g$の倍数のときに限り解を持つ。$c=dg$，$ax + by = g$の解の1つを$(x_0,y_0)$とすれば，$ax+by=c$の解は， \[x=dx_0+k\cdot\frac{b}{g},\ y=dy_0-k\cdot\frac{a}{g}, \ \ \ \mbox{（$k$は整数）}\] となる。
モジュラ逆数を求める際に利用できる。
下のサイトなどを参照のこと
次の「油わけ算」：
5合のマスと7合のマスを使って1合の油を量れを解くプログラムを作れ。
5合，7合のマスを使う回数をそれぞれ$x,y$とする。$\gcd(5,7)=1$なので$5x+7y=\gcd(5,7)$を解けばよい。解が正なら量って加え，負の値なら量って捨てることを意味する。
class Main {
/**
* ax + by = gcd(a,b)を解く
*/
static long[] xgcd(long a, long b) {
long r0 = a, r1 = b;
long x0 = 1, x1 = 0;
long y0 = 0, y1 = 1;
while (r1 != 0) {
long q = r0 / r1;
long u = r1;
r1 = r0 - q * r1;
r0 = u;
long v = x1;
x1 = x0 - q * x1;
x0 = v;
long w = y1;
y1 = y0 - q * y1;
y0 = w;
}
// gcd(a,b)が必要ならr0を返せばよい
return new long[]{x0, y0};
}
public static void main(String args[]) {
int a = 5, b = 7;
long[] r = xgcd(a, b);
System.out.printf("%d合のマスで%d回すくう\n", a, r[0]);
System.out.printf("%d合のマスで%d回すくう\n", b, r[1]);
}
}
def xgcd(a, b):
"""ax + by = gcd(a,b)を解く
"""
r0, r1 = a, b
x0, x1 = 1, 0
y0, y1 = 0, 1
while r1 != 0:
q = r0 // r1
r0, r1 = r1, r0 - q * r1
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
# gcd(a,b)が必要ならr0も返せばよい
return (x0, y0)
a = 5
b = 7
r = xgcd(a, b)
print("%d合のマスで%d回すくう" % (a, r[0]))
print("%d合のマスで%d回すくう" % (b, r[1]))