内容 第二章 · 一次同余方程 · 19
术语线索
algorithmus Euclideus / fractio continua / inversus
欧几里得算法 / 连分数 / 逆元。
命题
Solving ax ≡ ±1 is equivalent to solving a Bezout equation ax = by ± 1.
求 ax ≡ ±1 的解，等价于求不定方程 ax = by ± 1 的整数解。
读法 现代白话辅助
高斯把一次同余的计算落回欧几里得算法。现代语言说：扩展欧几里得算法给出 a 在模 b 下的逆元。
分步证明Step-by-step proof
1 / 2把 ax ≡ 1 (mod b) 改写成 ax - by = 1。
用辗转相除反代，找到 x 与 y。
小例 worked example
题
求 5 在模 12 下的逆元。
解
5 · 5 = 25 ≡ 1 (mod 12)，所以逆元是 5。
我的笔记 自动保存