8.3 巴歇的转换公式解法
狄克逊《数论史》提供了早期学者巴歇对二元一次不定方程的奇妙解法。
巴歇（Bachet，Claude-Gaspar，1581—1638），法国数学家，生于法国布雷斯地区布尔格，卒于布尔格，曾在帕多瓦等地学习，其后任教于米兰或科莫的教会学校。他是数学游戏的先驱之一，对数学、历史、诗歌等富有创见，被誉为17世纪最有才华的人。
1621年，巴歇把丢番图《算术》的希腊文本译成拉丁文出版，其中还补充了自己对数论和丢番图分析的研究成果[3]。这部著作对费马影响很大，为费马创立费马大定理奠定了基础。他于1635年被选为法国科学院成员。
1 原文
巴歇第一个提出，不定方程Ax=By+J的解依赖于Ax=By+1的解。这里A和B是任何互素的整数。引文第一句就强调了解的依赖性。
如果A和B是任何互素的整数，我们能够找到A的最小整倍数，它比B多已知整数J。[即，要解Ax=By+J]，只要解出Ax=By+1就可以了。
1624年的论文，现在只留下一个具体的算例[4]：67x=60y+1。
两系数67和60，辗转相除，得到四个带余除法，余数分别是7，4，3和1。对最后一个带余除法4=3×1+1，常数为1。巴歇设计了一个转换公式：“a=mb+1，那么ab+l-a是b的最小倍数，比a的倍数多1”，得到3×3=2×4+1。以此为基础，从辗转相除式中，反向消去余数3，4，7，要避免负数。
狄克逊《数论史》[5]是这样介绍的：
如果A和B是任何互素的整数，我们能够找到A的最小整倍数，它比B多已知整数J。[即，要解Ax=By+J]，只要解出Ax=By+1就可以了。巴歇1624年文章18—24页给出证明。足以解出Ax=By+1。巴歇原先对18个量分别标记字母的叙述法，较难记住它们之间的关系，以便于对他的处理，得到一个明确的印象。因此，我们这里利用他的数字例子A=67，B=60，采取比较明确的叙述形式。从较大数A中尽可能多次地减去较小数B，得数C。如果C=1，A本身就是比B的倍数多1的A所需要的倍数。下一步，令C＞1，从B中减去足够多次，直至得到余数1。
(1)
从最后一个式子中，根据“如果a=mb+1，那么ab+l-a是b的最小倍数，比a的倍数多1”的法则，我们得到
(2) 3×3=2×4+1。
用（2）中第一个系数3乘上（1）的第三个式子，并利用（2）消去项3×3，我们得到
(3) 3×7=5×4+1。
用（3）中系数5乘上（1）的第二个式子，并利用（3）消去项5×4，我们得到
(4) 43×7=5×60+1。
最后，用（4）中系数43乘上（1）的第一个式子，并利用（4）消去项43×7，我们得到
(5) 43×67=48×60+1,
使得最小的x是43，而相应的y是48。
巴歇导致（1）诸式的第一步，是求A，B最大公约数的欧几里得算法。他的下一步是，分别从（1）诸式中消去3，4，7的项，采取了一种保证不出现负值的特殊方式。
在辗转相除式和不定方程这两种不同结构之间，巴歇设立了进行过渡的转换公式：“如果a=mb+1，那么ab+l-a是b的最小倍数，比a的倍数多1”。
我们整理成表（表8.1），辗转相除法从（1a）编到（1d）。回代四个式子编成（2）到（5）。
表8.1 巴歇辗转相除与回代释意
互素整数对67和60辗转相除，得到有自然余数1的（1d）：4（a或r2）=3（b或r3）×1+1，即记作a=mb+1。
要保证1，再保证含有被除数4（a或r2）和除数3（b或r3），记作s×3=t×4+l，即s×b=t×a+l。这就是回代式（2）。
巴歇的巧妙在于取a，b构成ab+l-a。计算ab+l-a=r2r3+1-r2=4×3-4+1=9。这个9扣去1得8，是a（r2）（4）的2倍，这个9又是b（r3）（3）的3倍，即s×3=t×4+l。于是有3×3=2×4+1，成为右列的式（2）。有3×3=2×4+1。
于是归纳成：取s和t为整数，采用不定方程组形式sb=ta+l，有：
如果a=mb+1，那么ab+l-a=sb=ta+l。
再找式（3）。要保证1，再保证含有被除数7和除数4。导出不定方程：式（3）3×7=5×4+1。
循此思路，找出式（4）43×7=5×60+1和式（5）43×67=48×60+1。
把式（5）与原不定方程67x=60y+1比较，知：待定系数得x=43，y=48。