水平壺拿壺手法（如何用兩個杯子把水舀出來）

2023-04-15 21:50:08

先來考大家一個問題。下面是一個大水缸，和一個8升的小杯子還有一個13升的大杯子。問：能否用這兩個杯子剛好舀出2升的水。

如果要你舀出5升的水就簡單了，我先用大杯子舀出13升水，再倒入小杯子，小杯子倒滿的時候，我把小杯子水倒入水缸，而這時大杯子的水剛好是5升，小杯子空了。

寫出等式就是 5=13－8＝13＋8×(－1)。

舀2升水稍稍有點複雜，接著上面的做法，這時：

小杯子 大杯子

0升 5升

我把這5升水再倒入小杯子中，再用大杯子舀13升水。這時

小杯子 大杯子

5升 13升

把大杯子的水再倒入小杯子。倒3升後小杯子滿了，再把小杯子水倒入水缸，這時

小杯子 大杯子

0升 10升

接著，再把大杯子中的水倒入小杯子中，小杯子滿的時候，我再把小杯子水倒入水缸，而這時大杯子的水剛好剩下2升。

小杯子 大杯子

0升 2升

注意整個過程中，小杯子倒了3次滿水到水缸中，大杯子舀了2次滿杯水，寫出等式就是 2=13×2＋8×(－3)。

讀者可以嘗試一下如何剛好舀出3升水。相應的等式是3=13×(－1)＋8×2。

從1到13中任意選一個整數n， 我們都可以問能否用這兩個杯子剛好舀出n升的水。我們把上面的三種做法推廣，就可以得到下面的結論：

只有當(x,y)方程 13x 8y=n

有整數解的時候，用這兩個杯子才能剛好舀出n升的水。

整數，是指……－7，－6，－5，－4，－3，－2，－1，0，1，2，3，4，5，6，7……

正整數，是指1，2，3，4，5，6，7，8，9，10，11，12……

其實還有許多問題也可以導出這類方程，比如給你兩把長度分別是8釐米和13釐米的無刻度尺子，你能用這兩個尺子在直線上量出哪些長度。這個問題同樣要依賴於上面的方程是否有整數解，而我們今天要講的裴蜀引理(Bézout's lemma)會告訴我們，上面這個方程什麼時候有解！

Étienne Bézout (1730－1783)法國數學家

在欣賞裴蜀引理和它的證明之前，大家只需要接受四個非常簡單的預備知識。

一，約數和倍數：如果一個整數a能被正整數b整除，也就是說存在另一個整數p使得a=bp或者a/b=p，那麼我們就稱b是數a的約數或因數，a是數b的倍數。

比如15 的約數有四個：1，3，5，15。17的約數只有兩個：1，17。注意每個正整數都只有有限個約數，

再比如－5，0，5，10，15 都是5的倍數；－7，0，7，14，21 都是7的倍數。每個數都有無限多個倍數。

注意倍數可以是負數，但約數只能是正數

二，正整數a的兩個倍數的和或差還是a的倍數。

接下來我們可以介紹最大公約數的概念了。

三，公約數和最大公約數，如果正整數p同時是兩個整數a，b的約數，我們就稱p為a和b的公約數。a和b的所有公約數中最大的那個數稱為a和b的最大公約數。

四，帶餘除法：給定一個整數a和一個正整數q，總能找到一個整數b使得

其中0≤ r＜q。我們稱 r 為a被q除的餘數。

如何找到這個b呢？我們用q的所有倍數將數軸割成相等的線段，

而整數a要麼是q的某個倍數bq，要麼落在某兩個相鄰的倍數bq和(b 1)q之間，寫成不等式就是 bq≤ a＜(b 1)q，所以這個b就是我們所要找的。

比如取a=9，q=2，4×2≤ 9＜5×2，帶餘除法就是 9=4×2 1；

比如取a=－10，q=3，(－4)×3≤－10＜(－3)×3，帶餘除法就是－10=(－4)×3 2；

再比如取a=－15，q=5，(－5)×3≤－15＜(－4)×3，帶餘除法就是－15=(－5)×3＋0=(－5)×3。

理解了這四個預備知識，我們就可以開始欣賞下一節的優美證明。

三、裴蜀引理的證明

裴蜀引理：給定兩個整數a和b，假設他們的最大公約數是p，那麼下面(x,y)方程有整數解若且唯若n是p的倍數

xa yb=n

使得這個方程有整數解的那些n就是能寫成xa yb(x,y是整數)的那些數。我們把這些xa yb型的數統統「抓」到下面來

裴蜀引理是說這些數剛好構成了最大公約數p的所有倍數。所以如果裴蜀引理是正確的，那麼在上圖中的所有正數裡面，p是最小的。而我們的證明就是從這個「最小」入手。

證明：上圖中的所有正整數裡面，一定有個最小的數，我們把這個數記做q。而且注意了選出這個最小的正數是整個證明過程中最關鍵的一步！！

這裡可能會有人抗議：你怎麼知道這個正整數集合裡面一定有個最小的。說不定沒有最小的數。有沒有這種可能呢？其實是不可能的。先從這個正整數集合裡面任意選一個正整數 k，如果沒有最小的數，那我們可以從這個集合中選出一個比k小的正整數k',接著又可以選出一個比k'小的正整數k'',緊接著又可以選出一個比k''小的正整數k'''......一直選下去，我們可以找到無窮多個比k小的正整數。

但是，比一個正整數 k小的正整數只有有限個，比如比100小的正整數只有99個，這就導致矛盾了。

好了繼續我們的證明。同時要記住q是下圖中的所有正整數裡面最小的！

我們現在要證明的是下圖中所有的數都是(最小正數)q的倍數。

假設其中某個數sa tb不是q的倍數，那麼根據帶餘除法我們可以把它寫成：

其中h 和 r 都是整數，0＜r＜q。強調一遍：0＜r＜q

注意了q是xa yb型的數，不妨設q＝ma nb，其中m和n是整數。那麼

也是xa yb型的數。

所以 r 也是下圖中的一個正整數，而且比q還小。但這和q的最小性質矛盾了。所以之前的假設不成立，下面這個圖中所有的數正是q的所有倍數。

那麼a和b，因為也在圖中，自然也是q的倍數，所以q是a和b的公約數。我們接下來只需證明q是a和b的最大公約數，就完成了整個證明。先隨便給出一個a和b的公約數 q'，那麼a和b都是q'的倍數，而q是xa yb型的數，所以根據第二個預備知識，q也是q'的倍數。所以在a和b的所有公約數中，q 是最大的！

證明完畢

最後我們再回到舀水問題：用一個8升的小杯子和一個13升的大杯子能否剛好舀出n升水？

第一節講過這類問題依賴於方程13x 8y=n是否有整數解。現在裴蜀引理告訴我們只有當n是8和13的最大公約數的倍數的時候，方程才有解，而8和13的最大公約數是1，

因此方程總是有整數解。

所以 由裴蜀引理，我們可以直接知道用一個8升的小杯子和一個13升的大杯子能剛好舀出1升水，2升水，3升水，........13升水，不用像在第一節中那樣挨個試過去(比如舀出1升水就需要倒許多次)，這就是數學抽象證明的力量。

裴蜀引理有兩個非常重要的推論，這兩個推論在基礎數論中佔據非常基礎，非常核心的地位，比裴蜀引理本身更重要。在講這兩個推論之前，我們要介紹兩個概念：

一個大於1的正整數，如果只有1和它本身兩個約數，就稱它為素數。

比如2，3，5，7，11都是素數。

兩個整數的最大公約數如果為1，就稱這兩個數是互素的。

比如8和9，12和25都是互素的。

推論一：兩個整數a和b互素若且唯若下面(x,y)方程有整數解，xa yb=1。

推論二：如果素數p整除兩個整數a和b的乘積ab，則p必然會整除a或b。

考考你，能否從裴蜀引理出發證明這兩個推論？

本文轉載自微信公眾號職業數學家在民間