学习笔记：证明裴蜀定理

chenxi797 · 2025-08-25 14:39:32 · 算法·理论

什么是裴蜀定理？

如果有 d = \gcd(a,b)，则一定有 d \mid (ax + by)，且 ax + by = k \times \gcd(a,b)。

对于任意 (a,b)，有最小的 (x,y) 使得 ax + by = \gcd(a,b)

证明

集合

设 d = ax_0 + by_0 为集合中最小正值。

我们需要证明 d = \gcd(a,b)。

首先要证明 d \mid a 且 d \mid b。

对于整数除法 a \div b，使得存在商 q，余数 r (0 \le r < d)，有：

将 d = ax_0 + by_0 代入，得：

注意到 r 竟然也是 ax + by 的形式。

由于 0 \le r < d，d 为集合最小正值且 d > 0，那么 r 只能为 0。

那么 a = qd，即 d \mid a。

同理可证，d \mid b。

我们已经证明 d 为 a,b 公约数，接下来需要证明 d 为 a,b 的最大公约数。

设 c = \gcd(a,b)，则有 c \mid a 和 c \mid b。

又因为 a = c \times m,b = c \times n，那么：

当 x 取 x_0 值，y 取 y_0 值时：

由于 c = \gcd(a.b) 且 d \mid a,d \mid b，那么 c \ge d。

又因为 c \mid d，那么 c \le d。

由此得出 c = d，即：

证毕。