裴蜀定理

先說一下什麼是裴蜀定理吧

在數論中，裴蜀定理是一個關於最大公約數（或最大公約式）的定理，裴蜀定理得名於法國數學家艾蒂安·裴蜀。 ——引自百度百科

定理的具體內容：

若 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