public static long gcd(long m, long n) {	while(n != 0) {		long rem = m%n;		m = n;		n = rem;		gcd(m,n);	}	return m;}

在一次迭代中余数并不按照一个常数因子递减，然而，我们可以证明，在两次迭代以后，余数最多是原始值的一半。这就证明了，迭代次数至多是2logN=O（logN）从而得到运行时间。

定理：如果M>N，则M mod N<M/2。

证明：如果N<= M/2，则由于余数小于N，固定理在这种情况下成立。另一种情形是N>M/2。但是此时M仅含有一个N从而余数为M-N<M/2，定理得证。