import java.util.Scanner;

public class ExtendedEuclidean {

    static int extendedGCD(int a, int b, int[] x, int[] y) {
        if (b == 0) {
            x[0] = 1;
            y[0] = 0;
            return a;
        }

        int[] x1 = new int[1];
        int[] y1 = new int[1];

        int gcd = extendedGCD(b, a % b, x1, y1);

        x[0] = y1[0];
        y[0] = x1[0] - (a / b) * y1[0];

        return gcd;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter first number: ");
        int a = sc.nextInt();

        System.out.print("Enter second number: ");
        int b = sc.nextInt();

        int[] x = new int[1];
        int[] y = new int[1];

        int gcd = extendedGCD(a, b, x, y);

        System.out.println("\nGCD = " + gcd);
        System.out.println("x = " + x[0]);
        System.out.println("y = " + y[0]);
        System.out.println("\nFinal Equation:");
        System.out.println(a + "(" + x[0] + ") + " + b + "(" + y[0] + ") = " + gcd);

        sc.close();
    }
}