用户: Hbghlyj/Bézout 定理

裴蜀定理, 又称贝祖定理. 是一个关于最大公约数的定理.

定理 0.1. 设 $a, b$ 是不全为零的整数, 则存在整数 $x, y$ , 使得 $a x + b y = g cd (a, b)$ .

证明.

1.

若 $a, b$ 任何一个等于 0, 则 $g cd (a, b) = a$ . 这时定理显然成立.

2.

若 $a, b$ 不等于 0 . 由于 $g cd (a, b) = g cd (a, - b)$ , 不妨设 $a, b$ 都大于 $0, a \geq b, g cd (a, b) = d$ .

对 $a x + b y = d$ , 两边同时除以 $d$ , 可得 $a_{1} x + b_{1} y = 1$ , 其中 $(a_{1}, b_{1}) = 1$ . 转证 $a_{1} x + b_{1} y = 1$ .

我们先回顾一下辗转相除法是怎么做的, 由 $g cd (a, b) \to g cd (b, a mod b) \to \dots$ 我们把余数记作 $r$ . 于是, 有 $g cd (a_{1}, b_{1}) = g cd (b_{1}, r_{1}) = g cd (r_{1}, r_{2}) = \dots = g cd (r_{n - 1}, r_{n}) = 1$ 把辗转相除法中的运算展开, 做成带余数的除法, 得 $a_{1} b_{1} r_{1} r_{n - 3} r_{n - 2} r_{n - 1} = q_{1} b + r_{1} = q_{2} r_{1} + r_{2} = q_{3} r_{2} + r_{3} \dots = q_{n - 1} r_{n - 2} + r_{n - 1} = q_{n} r_{n - 1} + r_{n} = q_{n + 1} r_{n} (0 \leq r_{1} < b_{1}) (0 \leq r_{2} < r_{1}) (0 \leq r_{3} < r_{2})$ 不妨令辗转相除法在除到互质的时候退出则 $r_{n} = 1$ 所以有 ( $q$ 被换成了 $x$ , 为了符合最终形式) $r_{n - 2} = x_{n} r_{n - 1} + 1$ 即 $1 = r_{n - 2} - x_{n} r_{n - 1}$ 由倒数第三个式子 $r_{n - 1} = r_{n - 3} - x_{n - 1} r_{n - 2}$ 代入上式, 得 $1 = (1 + x_{n} x_{n - 1}) r_{n - 2} - x_{n} r_{n - 3}$ 然后用同样的办法用它上面的等式逐个地消去 $r_{n - 2}, \dots, r_{1}$ , 可证得 $1 = a_{1} x + b_{1} y$ . 这样等于是一般式中 $d = 1$ 的情况.

$□$

名字空间

视图

用户: Hbghlyj/Bézout 定理