概念

带余除法

整除、最大公约数与辗转相除（欧几里得算法）是数论的第一组工具，贝祖等式保证线性组合表示公约数。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

已是本主题的起点

带余除法初等数论

01定义

任意整数

a

除以正整数

b

，存在唯一的商

q

与余数

r

（

0\leq r<b

）使

a=bq+r

。这一平凡事实衍生出欧几里得辗转相除法与贝祖等式

\gcd(a,b)=xa+yb

——整数算术的第一块基石。

辗转相除：余数递减链收敛到 gcd

取 $q=\lfloor a/b\rfloor$ 、 $r=a-bq$ 即得存在；若两组表示相减得 $b(q-q')=(r'-r)$ ，而 $|r'-r|<b$ 强制相等——唯一性免费附送。

回溯辗转相除的每一步， $\gcd(a,b)$ 可写成 $xa+yb$ ；推论： $\gcd(a,b)=1\iff$ 存在 $x,y$ 使 $xa+yb=1$ ——模逆元存在的判据。

由带余除法 + 欧几里得引理（ $p\mid ab\Rightarrow p\mid a$ 或 $p\mid b$ ）推出：每个大于 1 的整数唯一分解为素数之积——整数的「化学元素表」。

a=bq+r,\quad 0\leq r<b,\quad \gcd(a,b)=\gcd(b,r)

欧几里得《几何原本》卷 VII（约公元前 300 年）已记载辗转相除法；贝祖 18 世纪给出线性组合表示；高斯《算术研究》将其纳入同余体系。

RSA 密钥生成中的模逆元计算、有理数约分与连分数展开、多项式环的欧几里得算法（纠错码设计）、计算代数中的 Gröbner 基化归。

带余除法：n = q·d + r调整被除数 n 与除数 d，观察商 q 与余数 r 的几何含义

n 被除数17d 除数5