date: 2025-04-11
title: "Bézout's identity"
status: UNFINISHED
author:
- AllenYGY
tags:
- NOTE
publish: false
Bézout's identity
裴蜀定理（贝祖定理）
- 表述：对于给定的两个整数 和 ，设它们的最大公因数为 ，那么一定存在整数 和 ，使得 。特别地， 与 互质（）的充要条件是存在整数 和 使得 。
- 证明思路：
- 考虑所有 形式的数构成的集合 ，其中 （ 表示整数集）。设 是 中的最小正整数，即 （）。
- 对于任意整数 除以 ，根据带余除法，有 ，其中 ，则 ，这表明 也具有 的形式。由于 是 中的最小正整数且 ，所以 ，即 。同理可证 ，所以 是 和 的公因数。
- 又因为 是 和 的最大公因数，且 是 和 的公因数，所以 。同时，因为 且 ，所以 ，即 。因此，，也就证明了存在整数 使得 。
扩展欧几里得算法
- 目的：用于求解裴蜀定理中的 和 ，即对于已知的整数 和 ，求出满足 的整数 和 。
- 算法步骤：
- 基本情况：若 ，则 ，此时 ，（因为 ）。
- 递归情况：设 ，，先递归调用扩展欧几里得算法求出 和 对应的 和 ，使得 。然后通过一定的变换关系 ， 得到 和 对应的 和 。这里 表示 除以 的向下取整。
- 示例：求 ， 时满足 的 和 。
- 首先，。
- 执行算法：
- 初始 ，，，进入递归，此时 ，。
- 对于 ，，，递归到基本情况，此时 ，（因为 ）。
- 回溯计算 和 ：根据公式，当从 ， 回溯到 ， 时，，。最终得到 ，（因为 ，符号调整后 ）。
中国剩余定理（孙子定理）
- 表述：设 是两两互质的正整数，令 ，（）。则对于同余方程组 ，有唯一解 ，其中 是 模 的逆元，即满足 。
- 证明思路：
- 首先证明解的存在性：
- 对于每个 ，因为 两两互质，所以 ，根据逆元存在性， 模 的逆元 存在。
- 考虑 ，对于任意 ，当 时，（因为 且 是 的因子且 ），所以 。当 时，。因此，，即 是同余方程组的一个解。
- 然后证明解的唯一性：假设 和 都是同余方程组的解，则 （），即 。因为 两两互质，所以 ，也就是 ，说明在模 意义下解是唯一的。