設(shè)a與b的公約數(shù)集合為A, b與a%b的公約數(shù)集合為B
要證明gcd(a,b) = gcd(b, a%b)，
即證max(A) = max(B)

?d ∈ A, 則有 d|a, d|b, 那么
∵ a%b = a - kb = k'd - k''d
∴ d|a%b
∴ d ∈ B

?d ∈ B, 則有 d|b, d|a%b, 那么
∵ a%b = kd = a - k'b
∴ a = kd + k'b
∴ d|a
∴ d ∈ A

那么就有A=B
所以max(A) = max(B)
即gcd(a,b) = gcd(b, a%b)