歐幾里得算法
公式表述：
證明：
a 可以表示為 a = kb + r姻乓，r = a%b
假設(shè) d 是 (a,b) 的一個公約數(shù)，則有
d|a眯牧，d|b蹋岩，而 r = a – kb，因此 d|r
所以 d 也是 (b,a%b) 的公約數(shù).
除了上面這個經(jīng)典算法炸站，還有 stein 算法用來求解最大公約數(shù)星澳，只有整數(shù)的移位和加減法，比歐幾里得算法在大整數(shù)上更有優(yōu)勢旱易，可以去了解一下禁偎。
擴展歐幾里得算法求解貝祖等式
貝祖定理（一般形式）
對于不全為 0 的自然數(shù) a，b阀坏，則必然存在整數(shù) x 如暖， y （不唯一）滿足等式
上面的等式就稱做貝祖等式。
擴展歐幾里得算法能夠求解貝祖等式的正確性證明
設(shè) a > b
- 當 b = 0 時忌堂，gcd(a,b) = a
貝祖等式即 ax = a盒至，解得 x = 1，y 可以取 y = 0 - 當 b > 0 時士修，
假設(shè) a枷遂，b 的貝祖等式的解為棋嘲，即
b酒唉，a%b 的貝祖等式的解為沸移，即
由歐幾里得算法可知
故
即
由恒等關(guān)系可得即貝祖等式 1 的解可以由 貝祖等式 2 的解得到痪伦，這是一個遞歸求解的過程侄榴，并且隨著對 a，b 進行輾轉(zhuǎn)相除网沾，貝祖等式的系數(shù)會越來越小癞蚕，直至變?yōu)榍闆r1，而情況1貝祖等式的解是有具體的值的辉哥，即 x = 1桦山，y = 0。然后進行回溯計算证薇，最終可以得到
C++代碼如下：
\\exGcd函數(shù)返回a浑度，b最大公約數(shù)。貝祖等式的整數(shù)解為引用參數(shù)x鸦概，y
int exGcd(int a, int b, int& x, int& y){
if(b == 0){
x = 1;
y = 0;
return a;
}
int r = exGcd(b,a%b,x,y);
int t = x;
x = y;
y = t - a/b*y;
return r;
}
貝祖定理（更原始形式）的證明
若整數(shù) a箩张，b 互質(zhì)，則存在整數(shù)解 x窗市，y 滿足 ax + by = 1
證明：
設(shè)分別是使得
的整數(shù)集合，
令咨察，假設(shè)此時
則有
假設(shè) 除以
的商為
，余數(shù)為
則有
但是因為其中摄狱，所以必須有
否則與假設(shè)
矛盾
故脓诡，同理可得
即 為
的公約數(shù)媒役，又
互質(zhì)
所以有
即存在整數(shù)使得
成立酣衷。
