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

considering input given a=21, b=36 , gcd (a,b) d=3.

if supposed achieve gcd solving equation a * x + b * y = d. how can evaluate numerous combinations of positive , negative integers x & y in equation fetch result satisfies equation.

eg: a=21, b=36, (gcd) d=3 21 * x + 36 * y = 3 x = ? , y = ? sample answer: x=-5,y=3 

how can in java?

you can extended euclidean algorithm. implementation here

public class extendedeuclid {     //  return array [d, a, b] such 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 = 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