// xgcd.java
import javax.swing.JOptionPane;
 
public class xgcd {

	private long a, b;
    private class gcd {
    	public long g,c,d;
    	gcd(long g, long c, long d) {this.g = g; this.c=c; this.d=d;}; 
    }
 
    public xgcd() {}
 
    public static void main(String[] args) {
        xgcd XGCD = new xgcd();
        XGCD.showDialog();
    }
 
    public void showDialog() {
        try {
            a = Long.parseLong(JOptionPane.showInputDialog("Please Enter The First Number, a:"));
            b = Long.parseLong(JOptionPane.showInputDialog("Please Enter The Second Number, b:"));
        } catch (NumberFormatException e) {
            JOptionPane.showMessageDialog(null, "Invalid input!", "ERROR", JOptionPane.ERROR_MESSAGE);
            return;
        }
        gcd GCD = calculate(a,b);
        JOptionPane.showMessageDialog(null, GCD.g + " = " + GCD.c + " * " + a + " + " + GCD.d + " * " + b,"Result",JOptionPane.INFORMATION_MESSAGE);
    }

    private gcd calculate(long a, long b) {
        if (b == 0) {
        	if (a < 0) {
        		return new gcd(-a,(long) -1,(long) 0);
        	}
        	else { 
        		return new gcd(a, (long) 1, (long) 0); 
        	}
        } else {
            gcd TEMP = calculate(b, a % b);
            return new gcd(TEMP.g, TEMP.d, TEMP.c - TEMP.d * (a/b));
        }
    }
}