ExtendedEuclid.java

Below is the syntax highlighted version of ExtendedEuclid.java from §5.6 Cryptography.

/******************************************************************************
 *  Compilation:  javac ExtendedEuclid.java
 *  Execution:    java ExtendedEuclid p q
 *  
 *  Reads two positive command-line arguments p and q and compute the greatest
 *  common divisor of p and q using the extended Euclid's algorithm.
 *  Also prints out integers a and b such that a(p) + b(q) = gcd(p, q).
 *
 *  Sample execution:
 * 
 *     % java ExtendedEuclid 36163 21199
 *     gcd(36163, 21199) = 1247
 *     -7(36163) + 12(21199) = 1247
 *
 *     % java ExtendedEuclid 36163 1058
 *     gcd(36163, 1058) = 1
 *     493(36163) + -16851(1058) = 1
 *
 *
 ******************************************************************************/

public class ExtendedEuclid {

   //  return array [d, a, b] such that d = gcd(p, q), ap + bq = d
   static int[] gcd(int p, int q) {
      if (q == 0)
         return new int[] { p, 1, 0 };

      int[] vals = gcd(q, p % q);
      int d = vals[0];
      int a = vals[2];
      int b = vals[1] - (p / q) * vals[2];
      return new int[] { d, a, b };
   }

   public static void main(String[] args) {
      int p = Integer.parseInt(args[0]);
      int q = Integer.parseInt(args[1]);
      if (p <= 0 || q <= 0) throw new IllegalArgumentException("p and q must be positive integers");
      int vals[] = gcd(p, q);
      StdOut.println("gcd(" + p + ", " + q + ") = " + vals[0]);
      StdOut.println(vals[1] + "(" + p + ") + " + vals[2] + "(" + q + ") = " + vals[0]);
   }
}