GCD / LCM of two numbers to be evaluated from the input numbers itself

Question

Considering the input given to us as a=21, b=36 and GCD (a,b) is d=3.

If we were supposed to achieve the GCD by solving the equation a * x + b * y = d. How can we evaluate the numerous combinations of positive and negative integers for x & y in this equation to fetch the result that satisfies this equation.

Eg: a=21, b=36, (GCD) d=3
21 * x + 36 * y = 3
x = ? and y = ?
Sample answer: x=-5,y=3

How can I do it in JAVA?

Answer 1

You can do it by Extended Euclidean algorithm. The implementation is here

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]);
      int vals[] = gcd(p, q);
      System.out.println("gcd(" + p + ", " + q + ") = " + vals[0]);
      System.out.println(vals[1] + "(" + p + ") + " + vals[2] + "(" + q + ") = " + vals[0]);
   }
}

Input: int vals[] = gcd(21, 36);

Output:

gcd(21,36) = 3
-5(21) + 3(36) = 3