/**
* Rozszerzony algorytm Euklidesa
*
* www.algortym.org
* (c)2006 Tomasz Lubinski
*/

public class Euklides_rozsz {


	/**
	 * @param args
	 */
	public static void main(String[] args) {
		   int r, a, q, b;
		   int x, x1, x2;
		   int y, y1, y2;
		   int nwd_a, nwd_b, nwd;

		   //get all data
		   System.out.println("Podaj pierwsza liczbe");
		   nwd_a = Console.readInt("?");

		   System.out.println("Podaj druga liczbe");
		   nwd_b = Console.readInt("?");

                   // a must be greater than b
		   if (nwd_b > nwd_a)
		   {
		      nwd = nwd_b;
		      nwd_b = nwd_a;
		      nwd_a = nwd;
		   }

   
		   //initialize a and b
		   a = nwd_a;
		   b = nwd_b;

		   //initialize r and nwd
		   q = a/b;
		   r = a - q*b;
		   nwd = b;
	   
		   //initialize x and y
		   x2 = 1;
		   x1 = 0;
		   y2 = 0;
		   y1 = 1;
		   x = 1;
		   y = y2 - (q-1)*y1;
   
		   while (r != 0)
		   {
		      a = b;
		      b = r;
      
		      x = x2 - q*x1;
		      x2 = x1;
		      x1 = x;
		
		      y = y2 - q*y1;
		      y2 = y1;
		      y1 = y;      
		
		      nwd = r;
		      q = a/b;
		      r = a - q*b; 
		   }

		   //present results
		   System.out.println("NWD("+nwd_a+", "+nwd_b+") = "+nwd+" = "+x+" * "+nwd_a+" + "+y+" * "+nwd_b);

		   if (nwd == 1)
		     System.out.println(nwd_b+" * "+y+" mod "+nwd_a+" = 1");
	}
}