裴蜀定理
Definition
设d=(a,b)
则存在两个整数x,y,满足：
\[ax+by=d \]Solution
首先带入下数据（随便两个整数）
例：14 10
不难看出，gcd(14,10)=2
辗转相除法：
(a,b)=(b,a mod b)
\(\cfrac{14}{10}=1...4\)
\(\cfrac{10}4=2...2\)
\(\cfrac42=2...0\)
当(a mod b)=0时，结束，取最后一次的商
Formula
\[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 \]$\because $ d=(a,b)
\(\therefore\) d满足以下条件：
\[d\mid r_k\ \ d\mid r_{k-1}\ \ d\mid r_{k-2}\ \ ...d\mid r_1 \]从第k 个式子往前推导，又可以得出：
$\because $ \(r_k\mid r_{k-1}\ \ r_{k}\mid r_{k-2}\ \ r_{k}\mid r_{k-3}\)
\(\therefore\) \(r_{k}\mid a\ \ r_k\mid b\)
\(\because\) (a,b)=d，\(\therefore\) \(r_k\leqslant\) d
又\(\because\) (a,b)=\(r_k\)，\(\therefore\) \(r_k=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 \]可以很轻易地得出
\[d=r_{k+2}-r_{k+2}q_k \]解一下第\(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} \]\(\because\) 假设\(a\mid b\) 且 \(a \mid c\) ，则对于任意整数x,y，都有\(a \mid bx\ +\ cy\) （线性组合）
\(\therefore\) d可表示为\(r_{k-2}\)与\(r_{k-3}\) 的线性组合
\(\therefore\) \(d=ax+by\)