by Neal R. Wagner
Copyright © 2001 by Neal R. Wagner. All rights reserved.
NOTE: This site is obsolete. See book draft (in PDF):
For reference, here is the program again:
// ExtGCD: Extended GCD (long version)
public class ExtGCD {
public static long[] GCD(long x, long y) { // assumes not 0 or negative
long[] u = new long[3];
long[] v = new long[3];
long[] t = new long[3];
// at all stages, if w is any of the 3 vectors u, v or t, then
// x*w[0] + y*w[1] = w[2] (this is verified by "check" below)
// u = (1, 0, u); v = (0, 1, v);
u[0] = 1; u[1] = 0; u[2] = x; v[0] = 0; v[1] = 1; v[2] = y;
System.out.println("q\tu[0]\tu[1]\tu[2]\tv[0]\tv[1]\tv[2]");
while (v[2] != 0) {
long q = u[2]/v[2];
// t = u - v*q;
t[0] = u[0] -v[0]*q; t[1] = u[1] -v[1]*q; t[2] = u[2] -v[2]*q; check(x, y, t);
// u = v;
u[0] = v[0]; u[1] = v[1]; u[2] = v[2]; check(x, y, u);
// v = t;
v[0] = t[0]; v[1] = t[1]; v[2] = t[2]; check(x, y, v);
System.out.println(q + "\t"+ u[0] + "\t" + u[1] + "\t" + u[2] +
"\t"+ v[0] + "\t" + v[1] + "\t" + v[2]);
}
return u;
}
public static void check(long x, long y, long[] w) {
if (x*w[0] + y*w[1] != w[2]) {
System.out.println("*** Check fails: " + x + " " + y);
System.exit(1);
}
}
public static void main(String[] args) {
long[] u = new long[3];
long x = Long.parseLong(args[0]);
long y = Long.parseLong(args[1]);
u = ExtGCD.GCD(x, y);
System.out.println("\ngcd(" + x + ", " + y + ") = " + u[2]);
System.out.println("(" + u[0] + ")*" + x + " + " +
"(" + u[1] + ")*" + y + " = " + u[2]);
}
}
Here is a sample run (with a few extra tabs inserted by hand):
% java ExtGCD 123456789 987654321 q u[0] u[1] u[2] v[0] v[1] v[2] 0 0 1 987654321 1 0 123456789 8 1 0 123456789 -8 1 9 13717421 -8 1 9 109739369 -13717421 0 gcd(123456789, 987654321) = 9 (-8)*123456789 + (1)*987654321 = 9
% java ExtGCD 1122334455667788 99887766554433 q u[0] u[1] u[2] v[0] v[1] v[2] 11 0 1 99887766554433 1 -11 23569023569025 4 1 -11 23569023569025 -4 45 5611672278333 4 -4 45 5611672278333 17 -191 1122334455693 4 17 -191 1122334455693 -72 809 1122334455561 1 -72 809 1122334455561 89 -1000 132 8502533754 89 -1000 132 -756725504178 8502533754809 33 4 -756725504178 8502533754809 33 3026902016801 -34010135020236 0 gcd(1122334455667788, 99887766554433) = 33 (-756725504178)*1122334455667788 + (8502533754809)*99887766554433 = 33
% java ExtGCD 384736948574637 128475948374657 q u[0] u[1] u[2] v[0] v[1] v[2] 2 0 1 128475948374657 1 -2 127785051825323 1 1 -2 127785051825323 -1 3 690896549334 184 -1 3 690896549334 185 -554 660086747867 1 185 -554 660086747867 -186 557 30809801467 21 -186 557 30809801467 4091 -12251 13080917060 2 4091 -12251 13080917060 -8368 25059 4647967347 2 -8368 25059 4647967347 20827 -62369 3784982366 1 20827 -62369 3784982366 -29195 87428 862984981 4 -29195 87428 862984981 137607 -412081 333042442 2 137607 -412081 333042442 -304409 911590 196900097 1 -304409 911590 196900097 442016 -1323671 136142345 1 442016 -1323671 136142345 -746425 2235261 60757752 2 -746425 2235261 60757752 1934866 -5794193 14626841 4 1934866 -5794193 14626841 -8485889 25412033 2250388 6 -8485889 25412033 2250388 52850200 -158266391 1124513 2 52850200 -158266391 1124513 -114186289 341944815 1362 825 -114186289 341944815 1362 94256538625 -282262738766 863 1 94256538625 -282262738766 863 -94370724914 282604683581 499 1 -94370724914 282604683581 499 188627263539 -564867422347 364 1 188627263539 -564867422347 364 -282997988453 847472105928 135 2 -282997988453 847472105928 135 754623240445 -2259811634203 94 1 754623240445 -2259811634203 94 -1037621228898 3107283740131 41 2 -1037621228898 3107283740131 41 2829865698241 -8474379114465 12 3 2829865698241 -8474379114465 12 -9527218323621 28530421083526 5 2 -9527218323621 28530421083526 5 21884302345483 -65535221281517 2 2 21884302345483 -65535221281517 2 -53295823014587 159600863646560 1 2 -53295823014587 159600863646560 1 28475948374657 -384736948574637 0 gcd(384736948574637, 128475948374657) = 1 (-53295823014587)*384736948574637 + (159600863646560)*128475948374657 = 1