定理内容

对于任意不全为 $0$ 的整数 $a,b$，方程 $ax+by=\gcd(a,b)$ 一定有整数解 $x,y$。

证明

引理 $1$

对于两个正整数 $a,b$ 满足 $a>b$ 可以推出 $\gcd(a,b)=\gcd(b,a\bmod b)$。

设 $a=kb+c,d\mid\gcd(a,b)$，那么一定有 $d\mid a,d\mid b$。

通过移项可以得到 $c=kb-a$，将两边同除 $d$ 得到 $\dfrac{c}{d}=k\cdot\dfrac{b}{d}-\dfrac{a}{d}$，因为 $d\mid a,d\mid b$ 所以等式右侧为整数，这就证明了 $d\mid c$。

将 $a=kb+c$ 变形可以得到 $c=b\bmod a$，可以推出 $d\mid b\bmod a$，因为所有的因数都是相同的，所以自然有 $\gcd(a,b)=\gcd(b,a\bmod b)$。

定理证明

对于任意一个 $a,b$ 为 $0$ 的情况有 $\gcd(a,b)=\max(a,b)$，此时 $x=1,y=1$ 就是一组解，定理显然满足。

设 $d=\gcd(a,b)$，那么将等式两侧同乘 $\dfrac{1}{d}$ 可以得到 $\dfrac{a}{d}\cdot x+\dfrac{b}{b}\cdot y=1$，不妨设 $a'=\dfrac{a}{d},b'=\dfrac{b}{d}$。

所以只需要证明 $a'x+b'y=1$ 即可。

根据引理 $1$ 可以得到辗转相除法 $\gcd(a,b)=\gcd(b,a\bmod b)=\cdots$。

我们记录出每一取模，具体的 $a=q_i\cdot b+r_i$，其中 $r_i$ 就是 $a\bmod b$ 的值。

在辗转相除法进行到最后一步时一定有 $r_n=1$，将取模操作反向的带回原式可以得到：$r_{n-2}=x_nr_{n-1}+1,1=r_{n-2}-x_nr_{n-1},\cdots$。

通过这样的不断代换就可以得到 $a'x+b'y=1$。

拓展

多个元素

裴蜀定理可以拓展到多个数的情况，也就是对于不全为 $0$ 的整数 $a_1,a_2,\cdots ,a_n$ 的方程 $\sum\limits_{i=1}^{n}a_i\cdot x_i=\gcd\limits_{i=1}^{n} a_i$ 一定可以找到整数解 $x_1,x_2,\cdots,x_n$。

一般应是否有解

对于更一般的方程 $\sum\limits_{i=1}^{n}a_i\cdot x_i=m$，如果 $m\mid \gcd\limits_{i=1}^{n} a_i$ 那么方程有解，否则一定无解。

证明很简单，因为 $\sum\limits_{i=1}^{n}a_i\cdot x_i=\gcd\limits_{i=1}^{n} a_i$ 有解，那么将所有的元素除以 $m$ 就得到一组解了。

应用

题目

假设长度为 $a_i$ 的连续的序列的第一项为 $x_i$，那么因为易得 $s_i=\cfrac{a_i\cdot[x_i+(x_i+a_i-1)]}{2}$ 。

因为题目要求 $\sum_{i=1}^{m} s_i=0$，所以可以得到 $\sum_{i=1}^{m} \cfrac{a_i\cdot[x_i+(x_i+a_i-1)]}{2}=0$。

即 $\sum_{i=1}^{m} \cfrac{a_i\cdot[2\cdot x_i+a_i-1]}{2}=0$。

也就是 $(\sum_{i=1}^{m} \cfrac{a_i\cdot(a_i-1)}{2})+(\sum_{i=1}^{m} a_i\cdot x_i)=0$。

通过移项可以得到 $\sum_{i=1}^{m} \cfrac{a_i\cdot(a_i-1)}{2}=-\sum_{i=1}^{m} a_i\cdot x_i$，所以左边就是一个常数。

根据贝祖定理，当且仅当 $\gcd(a_1,a_2,\cdots,a_{m})\mid \sum_{i=1}^m \cfrac{a_i\cdot(a_i-1)}{2}$ 时有解，通过移项可以得到 $2\mid \sum_{i=1}^m \cfrac{a_i\cdot(a_i-1)}{\gcd(a_1,a_2,\cdots,a_{m})}$。

假设 $\gcd(a_1,a_2,\cdots,a_{m})=2^t\cdot (2k+1)$ 其中 $t$ 尽可能大且 $k$ 为整数，那么设 $c_i=\cfrac{a_i}{2^t}$。

将上式代入，得到 $2\mid \sum_{i=1}^m \cfrac{2^t\cdot c_i\cdot(2^t\cdot c_i-1)}{2^t\cdot(2k+1)}$，由于这个式子是由 $\sum_{i=1}^m \cfrac{a_i\cdot(a_i-1)}{\gcd(a_1,a_2,\cdots,a_{m})}$ 变形来的，所以一定是一个整数。

因为一个偶数除以一个奇数并不影响奇偶性，所以 $2k+1$ 直接不看，即得到 $2\mid \sum_{i=1}^m c_i\cdot(2^t\cdot c_i-1)$。

当 $t=0$ 时，等式恒成立，否则需满足 $2\mid \sum_{i=1}^m c_i$。

因为 $t=0$ 只会发生在选择的 $m$ 个数中出现奇数，所以将奇数的情况单独讨论。

假设奇数有 $a$ 个，偶数有 $b$ 个，那么因为只要有奇数就可以，所以方案数为 $(2^a-1)\cdot 2^b$。

对于 $t\ne 0$ 的情况，假设有 $a$ 个 $a_i$ 没有多余的 $2$，$b$ 个有多余的 $2$，那么贡献为 $2^b\cdot \sum_{i=0}^{\lfloor a/2\rfloor }C^{2i}_{a}$。

因为 $C^i_a=C^i_{a-1}+C_{a-1}^{i-1}$，所以贡献为 $2^b\cdot\sum_{i=1}^{a-1}C^i_{a-1}$，也就是 $a$ 个元素的非空子集数量 $2^b\cdot (2^{a-1}-1)$。