定义
设 \(a,b\) 是不全为 \(0\) 的整数
1.对任意整数 \(x,y\)，满足 \(\gcd(a,b)|ax+by\)
2.存在整数 \(x,y\) 使得 \(ax+by=\gcd(a,b)\)
证明
第一条
理解一下即可，比较好理解
第二条
-
若任何一个等于 \(0\)，则 \(\gcd(a,b)=a\)，这时定理显然成立
-
若 \(a,b\) 均不等于 \(0\)
由于 \(\gcd(a,b)=\gcd(a,-b)\)，不妨设 \(a,b\) 均 \(>0，a\geq b\)，\(d=\gcd(a,b)\)
对于 \(ax+by=d\)，两边同时 \(\div d\)，可得 \(a_1x+b_1y=1\)，由于除以了 \(a,b\) 的最大公约数，所以此时 \(a,b\) 互质，转证 \(a_1x+b_1y=d\)
回顾 \(exgcd\) 中辗转相除的思想：
\(\gcd(a,b)→\gcd(b,a\bmod b)→…\)，将模出来的数称作 \(r\)，则：
\[\gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=…=\gcd(r_{n-1},r_n)=1 \]将上述式子转换为带余数的除法
\[a_1=q_1b_1+r_1 \]\[b_1=q_2r_1+r_2 \]\[r_1=q_3r_2+r_3 \]\[… \]\[r_{n-3}=q_{n-1}r_{n-2}+r_{n-1} \]\[r_{n-2}=q_{n}r_{n-1}+r_n \]\[r_{n-1}=q_{n+1}r_n \]当辗转相除法除到互质时，\(r_n=1\)，以 \(x\) 替换 \(q\)，则有：
\[r_{n-2}=x_nr_{n-1}+1 \]\[→1=r_{n-2}-x_nr_{n-1} \]将倒数第三个式子转化为 \(r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}\)，代入上式
\[1=r_{n-2}-x_n(r_{n-3}-x_{n-1}r_{n-2}) \]\[→1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3} \]然后通过同样方法消去 \(r_{n-2},…,r_1\)
可证得 \(1=a_1x+b_1y\) 是一般式中 \(d=1\) 的情况
同时乘以 \(d\)，得 \(ax+by=d\)
推广
逆定理
若 \(a,b\) 是不全为 \(0\) 的整数，\(d>0\) 是 \(a,b\) 的公因数，且存在整数 \(x,y\)，使得 \(ax+by=d\) 成立，则 \(d=\gcd(a,b)\)
特殊的，当上述的 \(d=1\) 时，则 \(a,b\) 互质
多个整数
\(n\) 个整数的情形：设 \(a_1,a_2,…,a_n\) 是不全为 \(0\) 的整数，则存在整数 \(x_1,x_2,…,x_n\) ，使得 $$\sum_{i=1}^{n}d_ia_i=\gcd(a_1,a_2,…,a_n)$$
其逆定理也成立：设\(a_1,a_2,…,a_n\) 是不全为 \(0\) 的整数，\(d>0\) 是她们的公因数，若存在整数 \(x_1,x_2,…,x_n\)，使得 $$\sum_{i=1}^{n}d_ia_i=\gcd(a_1,a_2,…,a_n)$$则 \(d=\gcd(a_1,a_2,…,a_n)\)
标签：全为,gcd,1y,定理,整数,ax,互质,裴蜀 From： https://www.cnblogs.com/Charlieljk/p/17935604.html