NOTE: This site is obsolete. See book draft (in PDF):

The Laws of Cryptography with Java Code.

// ExtGCDsimple: Extended GCD
public class ExtGCDsimple {

   public static long[] GCD(long x, long y) {
      long[] u = {1, 0, x}, v = {0, 1, y}, t = new long[3];
      while (v[2] != 0) {
         long q = u[2]/v[2];
         for (int i = 0; i < 3; i++) {
            t[i] = u[i] -v[i]*q; u[i] = v[i]; v[i] = t[i];
         }
      }
      return u;
   }

   public static void main(String[] args) {
      long[] u = new long[3];
      long x = Long.parseLong(args[0]);
      long y = Long.parseLong(args[1]);
      u = ExtGCDsimple.GCD(x, y);
      System.out.println("gcd(" + x + ", " + y + ") = " + u[2]);
      System.out.println("(" + u[0] + ")*" + x + " + " + 
                         "(" + u[1] + ")*" + y + " = " + u[2]);
   }
}

Here are several runs of this program:

%  java ExtGCDsimple 819 462
gcd(819, 462) = 21
(-9)*819 + (16)*462 = 21
% java ExtGCDsimple 40902 24140
gcd(40902, 24140) = 34
(337)*40902 + (-571)*24140 = 34