import javax.swing.JOptionPane;
import java.util.StringTokenizer;

public class TestEculid {
	public TestEculid() {
		while(true) {
			String input = JOptionPane.showInputDialog("Enter number and mod");
			if( input == null ) return;
			StringTokenizer t = new StringTokenizer(input);
			int number = Integer.parseInt(t.nextToken());
			int mod =  Integer.parseInt(t.nextToken());
			JOptionPane.showMessageDialog(null,"inverse is "+eculidInverse(number,mod));
		} // end while
	}
	
	public static void main(String[] a) {
		new TestEculid();
		System.exit(0);
	}

	int eculidInverse(int n,int mod) {
		int x = mod;
		int y = 1;
		int a = mod;
		int b = n;
		while( b > 1) {
			System.out.println(a+" "+x+"\n"+b+" "+y+"\n");
			int q = a/b;
			int save = b;
			b = a%b;
			a = save;
			save = y;
			y = x-q*y;
			x = save;
		} // end while
		System.out.println(b+" "+y);
		while( y < 0 ) y+=mod;
		return (b==1)?y%mod:0;
	}
	
}