歐幾裡得算法證明（輾轉相處法）

證明：gcd(m,n) = gcd(n,m mod n).

證明如下：設m和n的最大公約數為k，即gcd(m,n) = k，則有m = i*k，n = j*k；再設a = m / n = i / j, b = m mod n，則b = m - a * n = 

i*k-a *j*k = (i-a*j)*k.因(i-a*j) = i mod j，而 i 和 j 互質，故(i-a*j)和 j 互質，進而 n 和 b 的最大公約數為 k 。

當遞歸出現 gcd(w,0)中的w即為最大公約數k，其原因是在上一次疊代裡gcd(u,w)裡u mod w值為0，說明u能被w整除。

綜上所述，gcd(m,n) = gcd(n,m mod n).