裴蜀定理

先说一下什么是裴蜀定理吧

在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理，裴蜀定理得名于法国数学家艾蒂安·裴蜀。 ——引自百度百科

定理的具体内容：

若 a , b a,ba,b 是整数,且 gcd ⁡ ( a , b ) = d \gcd(a,b)=dgcd(a,b)=d，那么对于任意的整数 x , y , a x + b y x,y,ax+byx,y,ax+by 都一定是 d dd 的倍数，特别地，一定存在整数 x , y x,yx,y，使 a x + b y = d ax+by=dax+by=d 成立。 ——引自百度百科

简单来说，我们设 d = gcd ⁡ ( a , b ) d=\gcd(a,b)d=gcd(a,b)，那么对于方程 a x + b y = d ax+by=dax+by=d，一定存在一组整数解。并且对于方程 a x + b y = z ax+by=zax+by=z，如果满足 d ∣ z d|zd∣z，那么方程一定有整数解，否则无整数解。 首先证明一下 a x + b y = d ax+by=dax+by=d 一定有整数解：

证明如下：

抛开那条式子，先考虑模拟一下求 gcd ⁡ ( a , b ) \gcd(a,b)gcd(a,b) 的过程。

求 gcd ⁡ \gcdgcd 肯定是用辗转相除法嘛！

我们设 a ≤ b a\leq ba≤b，由辗转相除法的过程（g c d ( x , y ) = g c d ( y , x % y ) gcd(x,y)=gcd(y,x\%y)gcd(x,y)=gcd(y,x%y)）可以得到： 设b = a x 1 + r 1 b=ax_1+r_1b=ax1​+r1​ ， 那么 b % a b\%ab%a 后 b = r 1 b=r_1b=r1​

重复此过程，可以得到以下式子：

b = a x 1 + r 1 b=ax_1+r_1b=ax1+r1 a = r 1 x 2 + r 2 a=r_1x_2+r_2a=r1​x2​+r2​ r 1 = r 2 x 3 + r 3 r_1=r_2x_3+r_3r1​=r2​x3​+r3​ …… r k − 3 = r k − 2 x k − 1 + r k − 1 ( 1 ) r{k-3}=r{k-2}x{k-1}+r{k-1}(1)rk−3​=rk−2​xk−1​+rk−1​ (1) r k − 2 = r k − 1 x k + r k ( 2 ) r{k-2}=r{k-1}x_k+r_k~~~(2)rk−2​=rk−1​xk​+rk​ (2) r k − 1 = r k x k + 1 + r k + 1 r{k-1}=r_kx{k+1}+r_{k+1}rk−1​=rk​xk+1​+rk+1​

因为辗转相除法除到最后余数为 0 00，在这里，我们设 r k + 1 = 0 r_{k+1}=0rk+1=0，那么，r k r_krk 就是 a aa 和 b bb 的最大公约数，即 r k = d r_k=drk=d。将 r k = d r_k=drk=d 带入 ( 2 ) (2)(2) 式中得到：

r k − 2 = r k − 1 x k + d r{k-2}=r{k-1}x_k+drk−2=rk−1xk+d

移项一下，得到：

d = r k − 2 − r k − 1 x k ( 3 ) d=r{k-2}-r{k-1}x_k~~~(3)d=rk−2−rk−1xk (3)

将 ( 1 ) (1)(1) 式移项，得到：

r k − 1 = r k − 3 − r k − 2 x k − 1 ( 4 ) r{k-1}=r{k-3}-r{k-2}x{k-1}~~~(4)rk−1=rk−3−rk−2xk−1 (4)

将 ( 4 ) (4)(4)式带入 ( 3 ) (3)(3)式得到：

d = r k − 2 − ( r k − 3 − r k − 2 x k − 1 ) x k d=r{k-2}-(r{k-3}-r{k-2}x{k-1})x_kd=rk−2−(rk−3−rk−2xk−1)xk

把式子展开之后，可以表示成

d = m 1 r k − 2 + n 1 r k − 3 d=m_1r{k-2}+n_1r{k-3}d=m1rk−2+n1rk−3

显然，我们上面用到的数都是整数，所以，m 1 m_1m1，n 1 n_1n1也一定是整数。

如果我们将原来的 ( 3 ) (3)(3) 式表示成：d = m r k − 1 + n r k − 2 d=mr{k-1}+nr{k-2}d=mrk−1+nrk−2的话……

是不是有什么规律？

d = m r k − 1 + n r k − 2 d=mr{k-1}+nr{k-2}d=mrk−1+nrk−2 d = m 1 r k − 2 + n 1 r k − 3 d=m_1r{k-2}+n_1r{k-3}d=m1​rk−2​+n1​rk−3​

当我们将这两个式子一直像上面的做法一样一直搞下去，就可以得到：

d = m 2 r k − 3 + n 2 r k − 4 d=m_2r{k-3}+n_2r{k-4}d=m2rk−3+n2rk−4 d = m 3 r k − 4 + n 3 r k − 5 d=m_3r{k-4}+n_3r{k-5}d=m3​rk−4​+n3​rk−5​ ⋯ \cdots⋯ d = m k a + n k b d=m_ka+n_kbd=mk​a+nk​b

显然，m k m_kmk 和 n k n_knk 一定是整数，故，a x + b y = d ax+by=dax+by=d 一定有整数解。

得证。

于是，还有个重要的推论：

对于方程a x + b y = 1 ax+by=1ax+by=1，只有当整数a , b a,ba,b互质时，方程才有整数解。

有了上面的证明，这个很容易证。

证明

用一下反证法。

设 a , b a,ba,b 不互质，那么 a , b a,ba,b 可以表示成 a = q × gcd ⁡ ( a , b ) , b = p × gcd ⁡ ( a , b ) a=q\times\gcd(a,b),b=p\times\gcd(a,b)a=q×gcd(a,b),b=p×gcd(a,b)，带入上面的式子，得到：

q × gcd ⁡ ( a , b ) × x + p × gcd ⁡ ( a , b ) ∗ y = 1 q\times\gcd(a,b)\times x+p\times\gcd(a,b)*y=1q×gcd(a,b)×x+p×gcd(a,b)∗y=1

两边同时除以 gcd ⁡ ( a , b ) \gcd(a,b)gcd(a,b)，得到：

q x + p y = 1 gcd ⁡ ( a , b ) qx+py=\dfrac 1 {\gcd(a,b)}qx+py=gcd(a,b)1

显然，如果此时 a , b a,ba,b 不互质，那么等式的右边已经变成了一个小数，那么，该方程一定不存在整数解。

故只有当整数 a , b a,ba,b 互质时，该方程才有整数解

以及可以顺便得到

a , b a,ba,b 互质的充要条件是，满足方程 a x + b y = 1 ax+by=1ax+by=1 有整数解

得证。

然后，判断二元不定方程是否有整数解的方法出现了：

对于方程 a x + b y = z ax+by=zax+by=z，只有满足 gcd ⁡ ( a , b ) ∣ z \gcd(a,b)|zgcd(a,b)∣z，方程才有整数解。

证明依然十分简单：

证明

设 d = gcd ⁡ ( a , b ) , z = d × q d=\gcd(a,b),z=d\times qd=gcd(a,b),z=d×q。

对于方程 a x + b y = d ax+by=dax+by=d，我们设有一组解为 x 1 , y 1 x_1,y_1x1,y1，那么就有：

a x 1 + b y 1 = d ax_1+by_1=dax1+by1=d

两边同时乘上 q qq，得到：

a x 1 × q + b y 1 × q = d × q ax_1\times q+by_1\times q=d\times qax1×q+by1×q=d×q ∵ z = d ∗ q \because z=d*q∵z=d∗q ∴ \therefore∴ 方程 a x + b y = z ax+by=zax+by=z，一定存在一组整数解为 x = x 1 × q , y = y 1 × q x=x_1\times q,y=y_1\times qx=x1​×q,y=y1​×q

得证。

然后……裴蜀定理还可以扩展到n nn元不定方程上。

对于不定方程a 1 x 1 + a 2 x 2 + a 3 x 3 + . . . + a n x n = z a_1x_1+a_2x_2+a_3x_3+...+a_nx_n=za1x1+a2x2+a3x3+...+anxn=z，满足gcd ⁡ ( a 1 , a 2 , . . . , a n ) ∣ z \gcd(a_1,a_2,...,a_n)|zgcd(a1,a2,...,an)∣z时，方程才有整数解

证明嘛……太麻烦了不写了，参考上面的二元不定方程的证明自己意会一下就好了。

以及还有另一条：

对于不定方程a 1 x 1 + a 2 x 2 + a 3 x 3 + . . . + a n x n = 1 a_1x_1+a_2x_2+a_3x_3+...+a_nx_n=1a1x1+a2x2+a3x3+...+anxn=1，只有所有系数a 1 , a 2 , . . . , a n a_1,a_2,...,a_na1,a2,...,an的最大公约数为1时，方程才有整数解。

顺便也得到：

所有系数a 1 , a 2 , . . . , a n a_1,a_2,...,a_na1,a2,...,an的最大公约数为1的充要条件是：满足不定方程a 1 x 1 + a 2 x 2 + a 3 x 3 + . . . + a n x n = 1 a_1x_1+a_2x_2+a_3x_3+...+a_nx_n=1a1x1+a2x2+a3x3+...+anxn=1

证明嘛……也不写了。。大家明白就好qwq

顺便提一句

裴蜀定理的应用——exgcd

exgcd