裴蜀定理（详解）

裴蜀定理

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

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

定理的具体内容：

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

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

证明如下：

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

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

我们设 a ≤ b ，由辗转相除法的过程（g c d ( x , y ) = g c d ( y , x % y ) .可以得到： 设b = a x₁ + r  ， 那么 b % a 后 b = r₁ 

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

b = a x₁ + r_{1 ,} a = r₁ x₂ + r₂ , r₁ = r₂ x₃ + r₃  …… r_k − 3 = r_k − 2 x_k − 1 + r_{k − 1} 

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

r k − 2 = r k − 1 x k + d  ( 2 )

移项一下，得到：

d = r k − 2 − r k − 1 x k  ( 3 )

将 ( 1 ) 式移项，得到：

r k − 1 = r k − 3 − r k − 2 x k − 1 ( 4 )

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

d = r k − 2 − ( r k − 3 − r k − 2 x k − 1 ) x k 

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

d = m 1 r k − 2 + n 1 r k − 3 

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

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

是不是有什么规律？

d = m r k − 1 + n r k − 2 , d = m 1 r k − 2 + n 1 r k − 3

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

d = m 2 r k − 3 + n 2 r k − 4 , d = m 3 r k − 4 + n 3 r k − 5 ,​ ⋯ ⋯ d = m k a + n k b 

显然，m k  一定是整数，故，a x + b y = d  一定有整数解。

得证。

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

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

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

证明

用一下反证法。

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

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

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

q x + p y = 1 gcd ⁡ ( a , b ) 

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

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

以及可以顺便得到

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

得证。

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

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

证明依然十分简单：

证明

设 d = gcd ⁡ ( a , b ) , z = d × q .

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

a x₁ + b y₁ = d 

两边同时乘上 q ，得到：

a x 1 × q + b y 1 × q = d × q 

qax1×q+by1×q=d×q

∵ z = d ∗ q  

∴ 方程 a x + b y = z，一定存在一组整数解为 x = x 1 × q , y = y 1 × q 

得证。

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

对于不定方程a 1 x 1 + a 2 x 2 + a 3 x 3 + . . . + a n x n = z ，满足gcd ⁡ ( a 1 , a 2 , . . . , a n ) ∣ z 时，方程才有整数解

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

以及还有另一条：

对于不定方程a₁ x₁ + a₂ x₂ + a₃ x₃ + . . . + a_n x_n = 1 ，只有所有系数a₁ , a₂ , . . . , a_n 的最大公约数为1时，方程才有整数解。

顺便也得到：

所有系数 a₁ , a₂ , . . . , a_n 的最大公约数为1的充要条件是：满足不定方程a 1 x 1 + a 2 x 2 + a 3 x 3 + . . . + a n x n = 1 

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

顺便提一句

裴蜀定理的应用——exgcd (扩展欧几里得)

exgcd