歐幾里德算法證明：（下述內(nèi)容僅做了解）
上面代碼使用的是歐幾里德算法，又稱輾轉(zhuǎn)相除法。
假設(shè)有非零正整數(shù) A、B，其中 A > B，將 A 減 B 記為 C，即 A - B = C。
最大公約數(shù)記為 GCD（greatest common divisor），例如 A、B 的最大公約數(shù)記為 GCD(A, B)。
求證：GCD(A, B) = GCD(B, R)
（其中 R 為 A 除以 B 的余數(shù)，或記為 R = A - n * B，n 為 A 除以 B 的商。即 R = A % B）
第一步：證明 GCD(A, B) 能夠整除 C
1.因為 GCD(A, B) 是 A 的公約數(shù)，存在整數(shù) X，使得 X * GCD(A, B) = A；
2.因為 GCD(A, B) 是 B 的公約數(shù)，存在整數(shù) Y，使得 Y * GCD(A, B) = B；
3.因為 A - B = C，即
X * GCD(A, B) - Y * GCD(A, B) = C
(X - Y) * GCD(A, B) = C
使用圖片表示即：
所以有結(jié)論：
GCD(A, B) 不僅是 A 和 B 的最大公約數(shù)，同時也是 C 的約數(shù)。
第二步：證明 GCD(B, C) 能夠整除 A
1.因為 GCD(B, C) 是 B 的公約數(shù)，存在整數(shù) M，使得 M * GCD(B, C) = B；
2.因為 GCD(B, C) 是 C 的公約數(shù)，存在整數(shù) N，使得 N * GCD(B, C) = C；
3.因為 B + C = A，即
M * GCD(B, C) + N * GCD(B, C) = A
(M + N) * GCD(B, C) = A
使用圖片表示即：
所以有結(jié)論：
GCD(B, C) 不僅是 B 和 C 的最大公約數(shù)，同時也是 A 的約數(shù)。
第三步：證明 GCD(A, B) = GCD(B, C)
1.因為 GCD(A, B) 是 A 和 B 的最大公約數(shù)，同時也是 C 的約數(shù)，所以 GCD(A, B) 一定也是 B 和 C 的約數(shù)。由于 GCD(B, C) 是 B 和 C 的最大公約數(shù)，所以存在
GCD(A, B) <= GCD(B, C)
2.因為 GCD(B, C) 是 B 和 C 的最大公約數(shù)，同時也是 A 的約數(shù)，所以 GCD(B, C) 一定也是 A 和 B 的約數(shù)。由于 GCD(A, B) 是 A 和 B 的最大公約數(shù)，所以存在
GCD(B, C) <= GCD(A, B)
3.由上可得 GCD(A, B) = GCD(B, C)
使用圖片表示即：
第四步：證明 GCD(A, B) = GCD(B, R)
1.因為 GCD(A, B) = GCD(B, C)，即 GCD(A, B) = GCD(B, A - B)
2.上式也可記為 GCD(A, B) = GCD(A - B, B)
3.重復(fù)上一步，即有
GCD(A, B) = GCD(A - B, B) = GCD(A - 2B, B) = ... = GCD(A - n * B, B)
4.所以 GCD(A, B) = GCD(B, R)
————————————————
版權(quán)聲明：本文為CSDN博主「阿飛」的原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/afei/article/details/80216247
