数论05_裴蜀定理

吴老师

2026-08-23 13:29:45

发布于：广东

6阅读

0回复

0点赞

05 裴蜀定理

1. 裴蜀定理说了什么

设 $a,b$ 是两个不同时为 0 的整数，并且：

$d=\gcd(a,b)$

那么一定存在两个整数 $x,y$ ，使得：

$\boxed{ax+by=d}$

也就是：

$\boxed{ax+by=\gcd(a,b)}$

换句话说：

两个整数的最大公约数，一定可以表示成这两个整数的整数倍之和。

这里的 $x,y$ 都是整数，可以是正整数、0，也可以是负整数。

1.1 一个简单例子

例如：

$a=12$

$b=5$

因为：

$\gcd(12,5)=1$

而：

$12\times(-2)+5\times5=1$

所以可以取：

$x=-2$

$y=5$

使得：

$12x+5y=\gcd(12,5)$

1.2 最大公约数不为 1 的例子

例如：

$a=18$

$b=12$

有：

$\gcd(18,12)=6$

而：

$18\times1+12\times(-1)=6$

所以可以取：

$x=1$

$y=-1$

得到：

$18x+12y=6$

也就是：

$18x+12y=\gcd(18,12)$

2. 什么是整数线性组合

形如：

$ax+by$

其中 $x,y$ 都是整数的式子，称为 $a,b$ 的一个整数线性组合。

例如：

$a=6$

$b=15$

如果取：

$x=1$

$y=1$

那么：

$6\times1+15\times1=21$

所以 21 是 6 和 15 的一个整数线性组合。

如果取：

$x=-2$

$y=1$

那么：

$6\times(-2)+15\times1=3$

所以 3 也是 6 和 15 的一个整数线性组合。

如果取：

$x=5$

$y=-1$

那么：

$6\times5+15\times(-1)=15$

所以 15 也是 6 和 15 的一个整数线性组合。

因此，同样的两个数 $a,b$ ，通过选择不同的整数 $x,y$ ，可以得到很多不同的整数线性组合。

裴蜀定理并不是说：

任意选择 $x,y$ ， $ax+by$ 都会等于最大公约数。

而是说：

一定能够找到某一组整数 $x,y$ ，恰好使 $ax+by=\gcd(a,b)$ 。

3. 所有 $ax+by$ 都一定是 $\gcd(a,b)$ 的倍数

设：

$d=\gcd(a,b)$

因为 $d$ 是 $a,b$ 的公约数，所以：

$d\mid a$

并且：

$d\mid b$

因为 $d\mid a$ ，所以对于任意整数 $x$ ：

$d\mid ax$

同理，因为 $d\mid b$ ，所以对于任意整数 $y$ ：

$d\mid by$

根据整除的加法性质，如果：

$d\mid ax$

并且：

$d\mid by$

那么：

$d\mid(ax+by)$

因此，对于任意整数 $x,y$ ：

$\boxed{d\mid(ax+by)}$

又因为：

$d=\gcd(a,b)$

所以：

$\boxed{\gcd(a,b)\mid(ax+by)}$

这说明：

无论怎样选择整数 $x,y$ ， $ax+by$ 都一定是 $\gcd(a,b)$ 的倍数。

3.1 用具体数字理解

例如：

$a=18$

$b=12$

那么：

$\gcd(18,12)=6$

因为：

$18=6\times3$

并且：

$12=6\times2$

所以：

$18x+12y=6\times3x+6\times2y$

把 6 提出来：

$18x+12y=6(3x+2y)$

因为 $x,y$ 都是整数，所以：

$3x+2y$

也一定是整数。

因此：

$18x+12y$

一定是 6 的倍数。

例如取：

$x=2$

$y=3$

得到：

$18\times2+12\times3=72$

而：

$72=6\times12$

所以 72 是 6 的倍数。

再例如取：

$x=5$

$y=-7$

得到：

$18\times5+12\times(-7)=6$

而：

$6=6\times1$

它仍然是 6 的倍数。

因此：

所有形如 $18x+12y$ 的整数，都一定是 6 的倍数。

一般地：

所有形如 $ax+by$ 的整数，都一定是 $\gcd(a,b)$ 的倍数。

3.2 到这里还没有证明裴蜀定理

这一点非常重要。

到目前为止，我们只是证明了：

$\gcd(a,b)\mid(ax+by)$

也就是说：

所有 $ax+by$ 都一定是 $\gcd(a,b)$ 的倍数。

但是这并不能直接说明：

$ax+by=\gcd(a,b)$

因为“是最大公约数的倍数”和“恰好等于最大公约数”是两件不同的事情。

例如：

$12$

是 6 的倍数，但：

$12\ne6$

所以接下来还必须证明：

一定可以选择一组合适的整数 $x,y$ ，使 $ax+by$ 恰好等于 $\gcd(a,b)$ 。

这才是裴蜀定理最关键的一步。

4. 为什么最大公约数本身一定能写成 $ax+by$

这里要使用上一章学习的欧几里得算法。

欧几里得算法不断使用带余除法：

$a=qb+r$

把余数单独写出来就是：

$r=a-qb$

我们还知道：

欧几里得算法中最后一个非零余数，就是 $\gcd(a,b)$ 。

现在真正需要解决的问题是：

为什么最后这个余数一定能够写成最开始的 $a,b$ 的整数倍之和？

为了解决这个问题，我们要证明一个更强的结论：

欧几里得算法产生的每一个余数，都能够写成最开始的 $a,b$ 的整数线性组合。

只要这一点成立，那么最后一个非零余数当然也具有这种形式。

4.1 第一个余数可以写成 $ax+by$

第一次带余除法：

$a=q_1b+r_1$

把 $r_1$ 单独写出来：

$r_1=a-q_1b$

也就是：

$r_1=1\cdot a+(-q_1)\cdot b$

因此 $r_1$ 已经可以写成：

$r_1=ax_1+by_1$

其中可以取：

$x_1=1$

$y_1=-q_1$

所以：

第一个余数 $r_1$ 可以写成最开始的 $a,b$ 的整数线性组合。

4.2 第二个余数为什么仍然可以写成最开始的 $a,b$

第二次带余除法为：

$b=q_2r_1+r_2$

把 $r_2$ 单独写出来：

$r_2=b-q_2r_1$

上一小节已经证明：

$r_1=ax_1+by_1$

把这个式子代入：

$r_2=b-q_2(ax_1+by_1)$

展开括号：

$r_2=b-q_2ax_1-q_2by_1$

把含 $a$ 的项和含 $b$ 的项分别整理：

$r_2=(-q_2x_1)a+(1-q_2y_1)b$

因为 $q_2,x_1,y_1$ 都是整数，所以：

$-q_2x_1$

和：

$1-q_2y_1$

也都是整数。

因此，可以把它们分别记作：

$x_2=-q_2x_1$

$y_2=1-q_2y_1$

于是：

$r_2=ax_2+by_2$

所以：

第二个余数 $r_2$ 虽然是由 $b$ 和 $r_1$ 得到的，但是因为 $r_1$ 本身已经能写成最开始的 $a,b$ 的整数线性组合，所以把 $r_1$ 代回去以后， $r_2$ 仍然能够写成最开始的 $a,b$ 的整数线性组合。

4.3 为什么后面的每一个余数也都可以

现在考虑欧几里得算法进行到中间的某一步。

假设前面的两个余数已经能够写成最开始的 $a,b$ 的整数线性组合：

$r_{k-2}=ax_1+by_1$

$r_{k-1}=ax_2+by_2$

下一次带余除法为：

$r_{k-2}=q_kr_{k-1}+r_k$

把 $r_k$ 单独写出来：

$r_k=r_{k-2}-q_kr_{k-1}$

把：

$r_{k-2}=ax_1+by_1$

和：

$r_{k-1}=ax_2+by_2$

代入：

$r_k=(ax_1+by_1)-q_k(ax_2+by_2)$

展开括号：

$r_k=ax_1+by_1-q_kax_2-q_kby_2$

把含 $a$ 的项放在一起，把含 $b$ 的项放在一起：

$r_k=(x_1-q_kx_2)a+(y_1-q_ky_2)b$

因为：

$x_1-q_kx_2$

和：

$y_1-q_ky_2$

仍然都是整数，所以可以分别记作：

$x_k=x_1-q_kx_2$

$y_k=y_1-q_ky_2$

于是：

$r_k=ax_k+by_k$

因此：

如果前面的两个余数都能够写成最开始的 $a,b$ 的整数线性组合，那么由它们计算出的下一个余数，也一定能够写成最开始的 $a,b$ 的整数线性组合。

所以这个性质能够随着欧几里得算法不断传递下去。

4.4 为什么最后能够得到 $\gcd(a,b)=ax+by$

现在把前面的结论连起来。

第一个余数可以写成：

$r_1=ax_1+by_1$

因此第二个余数也可以写成：

$r_2=ax_2+by_2$

再根据 4.3 的结论，第三个余数也可以写成：

$r_3=ax_3+by_3$

同样的过程不断重复。

因此：

欧几里得算法产生的每一个余数，都能够写成最开始的 $a,b$ 的整数线性组合。

设欧几里得算法最后一个非零余数为 $d$ 。

因为 $d$ 也是算法产生的一个余数，所以一定存在整数 $x,y$ ，使得：

$d=ax+by$

另一方面，根据欧几里得算法：

$d=\gcd(a,b)$

所以把 $d$ 替换成 $\gcd(a,b)$ ：

$\gcd(a,b)=ax+by$

也就是：

$\boxed{ax+by=\gcd(a,b)}$

这就证明了：

最大公约数本身一定能够写成最开始的 $a,b$ 的整数线性组合。

5. 裴蜀定理的证明总结

现在把整个证明整理一下。

设：

$d=\gcd(a,b)$

首先，因为：

$d\mid a$

并且：

$d\mid b$

所以对于任意整数 $x,y$ ：

$d\mid(ax+by)$

因此：

所有整数线性组合 $ax+by$ 都一定是 $\gcd(a,b)$ 的倍数。

接下来，通过欧几里得算法可以证明：

算法产生的每一个余数，都能够写成最开始的 $a,b$ 的整数线性组合。

而欧几里得算法的最后一个非零余数正好是：

$\gcd(a,b)$

所以一定存在整数 $x,y$ ，使：

$\boxed{ax+by=\gcd(a,b)}$

这就是裴蜀定理。

6. 小练习

练习 1

已知：

$\gcd(18,12)=6$

判断下面哪些数可能写成：

$18x+12y$

其中 $x,y$ 为整数。

练习 2

为什么任意的：

$18x+12y$

一定是 6 的倍数？

练习 3

欧几里得算法产生：

$a=q_1b+r_1$

为什么 $r_1$ 一定可以写成 $a,b$ 的整数线性组合？

练习 4

如果已经知道：

$r_1=ax_1+by_1$

$r_2=ax_2+by_2$

并且：

$r_1=qr_2+r_3$

证明 $r_3$ 也能够写成：

$ax+by$

的形式。

7. 练习答案

练习 1

6、12、18 都可能。

7 不可能。

因为所有：

$18x+12y$

都必须是：

$\gcd(18,12)=6$

的倍数。

练习 2

因为：

$18=6\times3$

并且：

$12=6\times2$

所以：

$18x+12y=6(3x+2y)$

因为 $3x+2y$ 是整数，所以 $18x+12y$ 一定是 6 的倍数。

练习 3

因为：

$a=q_1b+r_1$

所以：

$r_1=a-q_1b$

也就是：

$r_1=1\cdot a+(-q_1)\cdot b$

因此 $r_1$ 是 $a,b$ 的整数线性组合。

练习 4

由：

$r_1=qr_2+r_3$

得到：

$r_3=r_1-qr_2$

代入：

$r_1=ax_1+by_1$

和：

$r_2=ax_2+by_2$

得到：

$r_3=(ax_1+by_1)-q(ax_2+by_2)$

整理：

$r_3=(x_1-qx_2)a+(y_1-qy_2)b$

因为：

$x_1-qx_2$

和：

$y_1-qy_2$

都是整数，所以 $r_3$ 仍然可以写成：

$ax+by$

的形式。

有帮助，赞一个

去预览

0/2000

这里空空如也

05 裴蜀定理

1. 裴蜀定理说了什么

1.1 一个简单例子

1.2 最大公约数不为 1 的例子

2. 什么是整数线性组合

3. 所有 ax+byax+byax+by 都一定是 gcd⁡(a,b)\gcd(a,b)gcd(a,b) 的倍数

3.1 用具体数字理解

3.2 到这里还没有证明裴蜀定理

4. 为什么最大公约数本身一定能写成 ax+byax+byax+by

4.1 第一个余数可以写成 ax+byax+byax+by

4.2 第二个余数为什么仍然可以写成最开始的 a,ba,ba,b

4.3 为什么后面的每一个余数也都可以

4.4 为什么最后能够得到 gcd⁡(a,b)=ax+by\gcd(a,b)=ax+bygcd(a,b)=ax+by

5. 裴蜀定理的证明总结

6. 小练习

练习 1

练习 2

练习 3

练习 4

7. 练习答案

练习 1

练习 2

练习 3

练习 4

热门讨论

3. 所有 $ax+by$ 都一定是 $\gcd(a,b)$ 的倍数

4. 为什么最大公约数本身一定能写成 $ax+by$

4.1 第一个余数可以写成 $ax+by$

4.2 第二个余数为什么仍然可以写成最开始的 $a,b$

4.4 为什么最后能够得到 $\gcd(a,b)=ax+by$