Bezout定理
Definition
设d=(a,b)
则存在两个整数x,y,满足：
a x + b y = d ax+by=d ax+by=d
Solution
首先带入下数据（随便两个整数）
例：14 10
不难看出，gcd(14,10)=2
辗转相除法：
(a,b)=(b,a mod b)
14 10 = 1...4 \cfrac{14}{10}=1...4 1014=1...4
10 4 = 2...2 \cfrac{10}4=2...2 410=2...2
4 2 = 2...0 \cfrac42=2...0 24=2...0
当(a mod b)=0时，结束，取最后一次的商
Formula
b = a q 1 + r 1 0 < r 1 < ∣ a ∣ a = r 1 q 2 + r 2 0 < r 2 < r 1 r 1 = r 2 q 3 + r 3 0 < r 3 < r 2 r 2 = r 1 q 4 + r 4 0 < r 4 < r 3 . . . r k − 3 = r k − 2 q k − 1 + r k − 1 0 < r k − 1 < r k − 2 r k − 2 = r k − 1 q k + r k 0 < r k < r k − 1 r k − 1 = r k q k + 1 r k m o d r k − 1 = r k m o d q k + 2 = 0 b=aq_1+r_1\ \ 0<r_1<|a| \\ a=r_1q_2+r_2\ \ 0<r_2<r_1 \\ r_1=r_2q_3+r_3\ \ 0<r_3<r_2 \\ r_2=r_1q_4+r_4\ \ 0<r_4<r_3 \\ ... \\ r_{k-3}=r_{k-2}q_{k-1}+r_{k-1}\ \ 0<r_{k-1}<r_{k-2} \\ r_{k-2}=r_{k-1}q_{k}+r_{k}\ \ 0<r_{k}<r_{k-1} \\ r_{k-1}=r_{k}q_{k+1} \\\ r_k \ mod\ r_{k-1}\ =\ r_k\ mod\ q_{k+2}\ =\ 0 b=aq1+r1 0<r1<∣a∣a=r1q2+r2 0<r2<r1r1=r2q3+r3 0<r3<r2r2=r1q4+r4 0<r4<r3...rk−3=rk−2qk−1+rk−1 0<rk−1<rk−2rk−2=rk−1qk+rk 0<rk<rk−1rk−1=rkqk+1 rk mod rk−1 = rk mod qk+2 = 0
∵ \because ∵ d=(a,b)
∴ \therefore ∴ d满足以下条件：
d ∣ r k d ∣ r k − 1 d ∣ r k − 2 . . . d ∣ r 1 d\mid r_k\ \ d\mid r_{k-1}\ \ d\mid r_{k-2}\ \ ...d\mid r_1 d∣rk d∣rk−1 d∣rk−2 ...d∣r1
从第k 个式子往前推导，又可以得出：
∵ \because ∵ r k ∣ r k − 1 r k ∣ r k − 2 r k ∣ r k − 3 r_k\mid r_{k-1}\ \ r_{k}\mid r_{k-2}\ \ r_{k}\mid r_{k-3} rk∣rk−1 rk∣rk−2 rk∣rk−3
∴ \therefore ∴ r k ∣ a r k ∣ b r_{k}\mid a\ \ r_k\mid b rk∣a rk∣b
∵ \because ∵ (a,b)=d， ∴ \therefore ∴ r k ⩽ r_k\leqslant rk⩽ d
又 ∵ \because ∵ (a,b)= r k r_k rk， ∴ \therefore ∴ r k = d r_k=d rk=d
解一下第k个式子：
r k − 2 = r k − 1 q k + r k r k − 2 = r k − 1 q k + d − d = r k + 2 q k − r k + 2 d = r k + 2 − r k + 2 q k r_{k-2}=r_{k-1}q_{k}+r_{k} \\ r_{k-2}=r_{k-1}q_{k}+d \\ -d=r_{k+2}q_k-r_{k+2} \\ d=r_{k+2}-r_{k+2}q_k rk−2=rk−1qk+rkrk−2=rk−1qk+d−d=rk+2qk−rk+2d=rk+2−rk+2qk
可以很轻易地得出
d = r k + 2 − r k + 2 q k d=r_{k+2}-r_{k+2}q_k d=rk+2−rk+2qk
解一下第 k − 1 k-1 k−1个式子：
r k − 3 = r k − 2 q k − 1 + r k − 1 − r k − 1 = r k − 2 q k − 1 − r k − 3 r k − 1 = r k − 3 − r k − 2 q k − 1 r_{k-3}=r_{k-2}q_{k-1}+r_{k-1} \\ -r_{k-1}=r_{k-2}q_{k-1}-r_{k-3} \\ r_{k-1}=r_{k-3}-r_{k-2}q_{k-1} rk−3=rk−2qk−1+rk−1−rk−1=rk−2qk−1−rk−3rk−1=rk−3−rk−2qk−1
∵ \because ∵ 假设 a ∣ b a\mid b a∣b 且 a ∣ c a \mid c a∣c ，则对于任意整数x,y，都有 a ∣ b x + c y a \mid bx\ +\ cy a∣bx + cy （线性组合）
∴ \therefore ∴ d可表示为 r k − 2 r_{k-2} rk−2与 r k − 3 r_{k-3} rk−3 的线性组合
∴ \therefore ∴ d = a x + b y d=ax+by d=ax+by
