水平壶拿壶手法（如何用两个杯子把水舀出来）

一、舀水问题

先来考大家一个问题。下面是一个大水缸，和一个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。

考考你，能否从裴蜀引理出发证明这两个推论？

本文转载自微信公众号职业数学家在民间

,