public class GCD {

	// gcd(a, b) = ax + by
	static public int euclides(int a, int b, IntDoubleConsumer next)
	{
		  int x = 1;
		  int y = 0;
		  int r = 0;
		  int s = 1;

		  while(b != 0)
		  {
				  int c = a % b;
				  int q = a / b;
				  a = b;
				  b = c;

				  int pr = r;
				  int ps = s;
				  r = x - q*r;
				  s = y - q*s;
				  x = pr;
				  y = ps;
		  }
		  
		  next.accept(x, y);
		  return a;
		
	}
	
	static public int euclides(int a, int b)
	{
		return euclides(a, b, (x, y) ->  {});
	}
	
	static public int inverse(int a, int p)
	{
		Box<Integer> r = new Box<>();
		euclides(a, p, (x, y) -> {r.value = x;});
		return r.value;
	}
	
	public static void main(String[] args) {
		int a = 1989;
		int b = 867;
		
		int gcd = euclides(a, b);
		
		System.out.println("gcd = " + gcd);
		
		int inv = inverse(3, 7);
		
		System.out.println("3^-1 = " + inv);
		

	}

}