如何用一个23升的水桶和一个16升的水桶“制造”1升水？

有一个水龙头，一个水箱（假设可以装任意多的水），一个23升的大桶和一个16升的小桶。目标是在水箱中正好放进1升水，你将如何做到这一点？这有可能吗？

如果想在水箱里放7升水，那就很容易了，把大桶装满23升水，倒进水箱，然后把小桶倒满。

但我们的目标恰恰是1升。

裴蜀等式（Bézout’s Identity）

裴蜀等式说，如果a和b是整数，最大公约数为d，那么存在整数x和y，使ax+by=d。最大公除数是指能同时除a和b的最大数字，例如，如果a=33，b=44，那么d=11。

在我们上面的水桶例子中，a=23，b=16，d=1。根据裴蜀等式，一定有一些整数x和y使得23x+16y=1。这就是说，上述问题有一个解，但它是什么？

欧几里得算法

欧几里德算法是计算两个整数a和b的最大公约数d的一种有效方法。我们用gcd(a,b)代替d。

你可能会想，既然我们已经知道gcd(23,16)=1，为什么还要用欧几里得算法？事实证明，该算法将回答我们的上述问题，即得到x和y的值，使23x+16y=1。

下面是计算某些数字a和b的gcd(a,b)的步骤(假设a≥b)：

• 获取a除以b的余数，称之为r
• 如果r=0，那么gcd(a, b)=b. 如果r≠0，则执行b除以r，得到一个新的余数，称其为r^
• 如果r^=0，则gcd(a, b)=r，如果r^≠0，则执行r除以r^，得到一个新的余数，称为r^^
• 如果r^^=0，那么gcd(a,b)=r^，如果r^^≠0，那么....

继续这样做，直到余数为零得到的最后一个非零余数就是最大公约数。

例子：gcd(23, 16)=1

• 23 = 1*16 + 7（这里r=7）
• 16 = 2*7 + 2 （这里r^=2）
• 7 = 3*2 + 1（这里r^^=1，最后一个非零余数）
• 2 = 2*1 + 0 （这里r^^=0）

这里的*表示乘法。最后一个非零余数是1，所以这是23和16的最大公约数。在处理更大的数字时，这个算法会很有用。

现在我们可以按照上面的步骤进行倒推。这里的想法是保持余数为1，并尝试得到一个只有16和23的方程。

我们可以用上面的第二个等式乘以3，然后代入第三个等式，去除余数2。这样我们就可以得到：

3*16 = 6*7 + (7 - 1) = 7*7 - 1

现在用第一个等式乘以7，再代入上面的方程，得到：

7*23 + (-10)*16 = 1

因此我们问题的答案是x=7和y=10。

答案

我们可以先在水箱中装7大桶水，然后再倒出10小桶。