package 數學包;

public class 擴展歐幾里得算法 {

	public static void main(String[] args) {
		int m, n, a, b, c, d, t;
		int ap, bp;
		int q, r;

		m = 13;
		n = 53;
		ap = b = 1;
		a = bp = 0;
		c = m;
		d = n;

		while (d != 0) {
			q = c / d;
			r = c % d;
			c = d;
			d = r;
			t = ap;
			ap = a;
			a = t - q * a;
			t = bp;
			bp = b;
			b = t - q * b;
		}
		// ap*m+bp*n=c
		System.out.print(ap + "*" + m + "+" + bp + "*" + n + "=" + c);
	}
}