## 裴蜀定理 丢番图方程 $ax+by=c$ 有整数解**当且仅当** $\gcd(a,b)\mid c$ ，因此，裴蜀等式有整数解时必然有无穷多个整数解。 ### 证明 当 $a,b$ 当中有一者为 $0$，等式显然成立，以下只考虑均不为 $0$ 的情况。 由于 $\gcd(a,b)=\gcd(a,-b)$，我们不妨设 $a\ge b>0$，$\gcd(a,b)=d$. 我们把 $ax+by=d$ 两边同时除以 $d$，得 $a_1x+b_1y=1$. 转证 $a_1x+b_1y=1$. 我们考虑辗转相除法的过程： $$ \\begin{aligned}a_1 &= q_1b_1+r_1 &(0\\leq r_1<b_1) \\\\b_1 &= q_2r_1+r_2 &(0\\leq r_2<r_1) \\\\r_1 &= q_3r_2+r_3 &(0\\leq r_3<r_2) \\\\&\\cdots\\\\r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \\\\r_{n-2} &= q_nr_{n-1}+r_n \\\\r_{n-1} &= q_{n+1}r_n\\end{aligned} $$ 有 $(a_1,b_1)=(b_1,r_1)=(r_1,r_2)=\cdots=(r_{n_1},r_n)=1$ 由最后一个式子和倒数第二个式子可推出：$r_{n-2}-q_nr_{n-1}=1$ 再代入第三个式子，得：$(1+q_nq_{n-1})r_{n-2}-q_nr_{n-3}=1$ 用同样的方法可以消去 $r_{n-2},\cdots,r_1$，可证得 $a_1x+b_1y=1$，这样等于一般式中 $d=1$ 的情况 ## 推广 $a_1x_1+a_2x_2+\cdots+a_nx_n=m$ 有解，当且仅当 $\gcd(a_1,a_2,\cdots,a_b)|m$。 $a$,$b$互质的充分必要条件是存在整数 $x$,$y$ 使 $ax+by=1$. ## 例题 ### [Luogu P4549 【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549) 裴蜀定理模板，最小值即为所有 $a$ 的 $\gcd$. #### 代码 ```c++ #include <cstdio> #include <cctype> #include <cmath> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } int n, ans; int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); } int main() { n=read(); ans=read(); for (int i=2; i<=n; i++) { int x=abs(read()); ans=gcd(ans, x); } printf("%d\n", ans); return 0; } ``` ## 参考 - [裴蜀定理 - OI Wiki](https://oi-wiki.org/math/number-theory/bezouts/) - [裴蜀定理_百度百科](https://baike.baidu.com/item/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86/5186593) Loading... ## 裴蜀定理 丢番图方程 $ax+by=c$ 有整数解**当且仅当** $\gcd(a,b)\mid c$ ，因此，裴蜀等式有整数解时必然有无穷多个整数解。 ### 证明 当 $a,b$ 当中有一者为 $0$，等式显然成立，以下只考虑均不为 $0$ 的情况。 由于 $\gcd(a,b)=\gcd(a,-b)$，我们不妨设 $a\ge b>0$，$\gcd(a,b)=d$. 我们把 $ax+by=d$ 两边同时除以 $d$，得 $a_1x+b_1y=1$. 转证 $a_1x+b_1y=1$. 我们考虑辗转相除法的过程： $$ \\begin{aligned}a_1 &= q_1b_1+r_1 &(0\\leq r_1<b_1) \\\\b_1 &= q_2r_1+r_2 &(0\\leq r_2<r_1) \\\\r_1 &= q_3r_2+r_3 &(0\\leq r_3<r_2) \\\\&\\cdots\\\\r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \\\\r_{n-2} &= q_nr_{n-1}+r_n \\\\r_{n-1} &= q_{n+1}r_n\\end{aligned} $$ 有 $(a_1,b_1)=(b_1,r_1)=(r_1,r_2)=\cdots=(r_{n_1},r_n)=1$ 由最后一个式子和倒数第二个式子可推出：$r_{n-2}-q_nr_{n-1}=1$ 再代入第三个式子，得：$(1+q_nq_{n-1})r_{n-2}-q_nr_{n-3}=1$ 用同样的方法可以消去 $r_{n-2},\cdots,r_1$，可证得 $a_1x+b_1y=1$，这样等于一般式中 $d=1$ 的情况 ## 推广 $a_1x_1+a_2x_2+\cdots+a_nx_n=m$ 有解，当且仅当 $\gcd(a_1,a_2,\cdots,a_b)|m$。 $a$,$b$互质的充分必要条件是存在整数 $x$,$y$ 使 $ax+by=1$. ## 例题 ### [Luogu P4549 【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549) 裴蜀定理模板，最小值即为所有 $a$ 的 $\gcd$. #### 代码 ```c++ #include <cstdio> #include <cctype> #include <cmath> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } int n, ans; int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); } int main() { n=read(); ans=read(); for (int i=2; i<=n; i++) { int x=abs(read()); ans=gcd(ans, x); } printf("%d\n", ans); return 0; } ``` ## 参考 - [裴蜀定理 - OI Wiki](https://oi-wiki.org/math/number-theory/bezouts/) - [裴蜀定理_百度百科](https://baike.baidu.com/item/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86/5186593) 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏