import java.math.BigInteger;
import java.util.Vector;

public class ExtendedEuclid {

	public static BigInteger[] gcde(BigInteger a, BigInteger b) {
	
		/*
		 * Euclids' algorithm
		 * 
		 * gcd(9,140) = 1 (greatest common divisor)
		 * 
		 *  a		b 	c	 d 
		 *  140 = 	9 * 15 + 5
		 * 
		 *  a=b		b=d   c=a/b		a-b*c 
		 *  9	=	5   * 1			 + 4
		 *  5   =   4   * 1  		 + 1 <-- gcd(9,140)
		 *  4   =   1   * 4  		 + 0
		 * 
		 */
		
		Vector myvector = new Vector();
		
		BigInteger c = new BigInteger("0");
		BigInteger d = new BigInteger("0");
		BigInteger gcd_a_b = new BigInteger("0");
	
		BigInteger q = new BigInteger("0");
		BigInteger r = new BigInteger("0");
		BigInteger s = new BigInteger("0");
		BigInteger t = new BigInteger("0");

		BigInteger previous_q = new BigInteger("0");
		BigInteger previous_s = new BigInteger("0");
		BigInteger previous_previous_s = new BigInteger("0");
		BigInteger previous_t = new BigInteger("0");
		BigInteger previous_previous_t = new BigInteger("0");
		BigInteger minus_one = new BigInteger("-1");
		
		BigInteger mr_x = new BigInteger("0");
		BigInteger mr_y = new BigInteger("0");
		
		/*
		System.out.print("a	b	c	d");
		System.out.print("	");
		System.out.println("q	r	s	t");
		*/

		int ctr = 0;
		
		do {
			
			if (ctr == 0) {
				
				s = BigInteger.ONE;
				t = BigInteger.ZERO;
			
			}

			if (ctr == 1) {
				
				s = BigInteger.ZERO;
				t = BigInteger.ONE;
			
			}
			
			if (ctr > 1) {
				
				s = minus_one.multiply(previous_q);
				s = s.multiply(previous_s);
				s = s.add(previous_previous_s);

				t = minus_one.multiply(previous_q);
				t = t.multiply(previous_t);
				t = t.add(previous_previous_t);

			}

			q = c;
						
			c = a.divide(b);
			d = a.subtract(b.multiply(c));

			r = a;
			
			/*
			System.out.print(a);
			System.out.print("	");
			System.out.print(b);
			System.out.print("	");
			System.out.print(c);
			System.out.print("	");
			System.out.print(d);
			System.out.print("	");
			System.out.print(q);
			System.out.print("	");
			System.out.print(r);
			System.out.print("	");
			System.out.print(s);
			System.out.print("	");
			System.out.print(t);
			System.out.print(" ");
			System.out.println(" ");
			*/
			
			a = b;
			b = d;
			ctr++;
			previous_q = q;
			previous_previous_s = previous_s;
			previous_s = s;
			previous_previous_t = previous_t;
			previous_t = t;

		} while (d.compareTo(BigInteger.ZERO) == 1);
		
		gcd_a_b = a;
		
		q = c;
		r = a;

		s = minus_one.multiply(previous_q);
		s = s.multiply(previous_s);
		s = s.add(previous_previous_s);

		t = minus_one.multiply(previous_q);
		t = t.multiply(previous_t);
		t = t.add(previous_previous_t);
		
		mr_x = s;
		mr_y = t;
		
		/*
		System.out.print("			 	");
		System.out.print(q);
		System.out.print("	");
		System.out.print(r);
		System.out.print("	");
		System.out.print(s);
		System.out.print("	");
		System.out.print(t);
		System.out.print(" ");
		System.out.println(" ");
		System.out.println(" ");
		System.out.println(gcd_a_b);
		System.out.println(mr_x);
		System.out.println(mr_y);
		*/
						
		myvector.add(gcd_a_b);
		myvector.add(mr_x);
		myvector.add(mr_y);
		
		return (BigInteger[]) myvector.toArray(new BigInteger[] {});		
		
}
	
	public static void main(String[] args) {

		BigInteger bigIntA = new BigInteger("703");
		BigInteger bigIntB = new BigInteger("494");
		
		BigInteger proof = new BigInteger("0");
		
		//gcde(bigIntA,bigIntB);
		
		BigInteger result[] = new BigInteger[] {BigInteger.ZERO,BigInteger.ZERO,BigInteger.ZERO};
		
		result = ExtendedEuclid.gcde(bigIntA,bigIntB);
		
		proof = bigIntA.multiply(result[1]).add(bigIntB.multiply(result[2]));
		
		System.out.print("GCDE of "+bigIntA+" and "+bigIntB+" is: ");
		System.out.println("");
		
		System.out.println("GCD: " +result[0]);
		System.out.println("x: " +result[1]);
		System.out.println("y: " +result[2]);
		System.out.println("");
		System.out.println("gcd(a,b) = g = a * x + b * y = gdc(a,b)");
		System.out.println("=> gcd("+bigIntA+","+bigIntB+") = g = "+bigIntA+" * "+result[1]+" + "+bigIntB+" * "+result[2]+" = "+proof);
			
	}

}