以前可能看過，不過真的記不得了，特記錄一下，可能不嚴密，僅供自己理解。
　　求gcd(a, b)，欲證gcd(a, b) = gcd(b, a % b)
　　設d1 = gcd(a, b), d2 = gcd(b, a % b), a > b且a = qb + r
　　只需證d1 | d2并且d2 | d1。
　　因為d2 | b, d2 | r, 因此d2 | (b + qr) = a，根據d2 | b且d2 | a有d2 | gcd(a, b)，即d2 | d1。
　　因為d1 | a, d1 | b, 因此d1 | (a - qb) = r，根據d1 | b且d1 | r有d1 | gcd(b, r)，即d1 | d2。
　　根據Euclid算法執行過程，gcd(a, b) = gcd(b, r) = gcd(r, b % r) = ... = gcd(rn, rn-1 % rn)，如果rn-1 % rn = 0，根據gcd(a, 0) = a，有gcd(a, b) = rn，證畢。

　　貌似偏序關系上證a = b很多都是利用反對稱性，比如a >= b并且b >= a則a = b，或者a | b并且b | a則a = b，一個很常用且強大的方法。