欧几里得算法

欧几里得算法通过反复带余除法计算最大公约数。把 (a,b) 替换为 (b,r) 不改变公因数，而非负余数严格递减，因此过程必然终止。

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

探索概念图谱 · 探索关联视频

从不同角度理解

用欧几里得算法计算最大公因数
SoftwareEngenius · 英语 · 讲解
关联依据
35 至 202 秒通过整除引理反复把整数对替换为余数对，解释最大公因数为何保持不变。原片只展示了公约数论证的一个方向，公开编辑注补全反向论证，因此关联归为讲解而非证明。
辗转相除法完整解析：原理、步骤与例题
NUMA數之本 · 中文 · 讲解
关联依据
全片先计算余数链，再说明 gcd(a,b)=gcd(b,r)。81 至 113 秒只证明 a、b 的公因数也整除 r，未给出反向，因此归为讲解而非完整证明。
欧几里得算法为什么成立：减法形式直观解释
eHowEducation · 英语 · 讲解
关联依据
14 至 84 秒计算 $12-8$ 与 $8-4$ ，并说明公因数整除差值；审核材料明确标出原片缺少反向保持步骤，因此不归为完整证明。
初级数论之：两个数的最大公约数的递推公式【更相减损术】【辗转相除法】
南瓜之运 · 中文 · 讲解
关联依据
175 至 254 秒先给出 gcd(a,b)=gcd(b,a-kb)，令 $k=1$ 得更相减损术，再令 k=floor( $a/b$ )，用手写箭头把 a-floor( $a/b$ )b 与 a mod b 对应起来，从而得到 gcd(a,b)=gcd(b,a mod b)。审核材料保留 b 非零及余数约定的缺失，因此归为讲解而非证明。
详细描述欧几里得算法（附证明）
杰瑞和太一 · 中文 · 证明
关联依据
196 至 290 秒在 a>= $b>0$ 、 $a=q1*b+r1$ 的条件下，先证明 gcd(a,b) 同时整除 b 与 r1，再证明 b、r1 的任意公因子也整除 a 且不超过 gcd(a,b)，从而得到 gcd(a,b)=gcd(b,r1)。
详细描述欧几里得算法（附证明）
杰瑞和太一 · 中文 · 应用
关联依据
296 至 487 秒给出 gcd(a,b)=gcd(b,a mod b)，沿余数链定位最后一个非零余数，用 C++ 循环实现，并用十次除法验证 gcd(1160718174,316258250)=1078；正式有限下降与输入边界说明明确标为编辑补充。
欧几里得算法：两个最大公因数例题
Learn Math Tutorials · 英语 · 应用
关联依据
25 至 245 秒把两组正整数的带余除法链完整算到余数为零： $45=10*4+5$ 、 $10=5*2+0$ 得 gcd(10,45)=5；3768 与 1701 的七步计算最终得到 gcd=3。原片演示算法但没有证明不变量与终止性，因此归为应用而非证明。
欧几里得算法：最大公因数例题｜Michael Penn
Michael Penn · 英语 · 应用
关联依据
从 0 至 163 秒，板书先回顾反复带余除法，再完整计算 5295 与 4321 的八步除法，得到零余数，并把前一个非零余数确定为 1。视频应用算法，不证明一般定理。
用欧几里得算法计算最大公因数
SoftwareEngenius · 英语 · 应用
关联依据
202 至 282 秒推导递归取余规则，给出 Java 实现，并说明至多两次调用后余数会小于一半。公开审核把复杂度结论限定为单位成本模型下的取余调用次数，并纠正约 270 秒幻灯片中的旁注笔误。
欧几里得算法例题｜Socratica
Socratica · 英语 · 应用
关联依据
从 0 到 123 秒，视频先说明反复带余除法与停止规则，用 104 和 84 做简短示例，再完整演算 1785 与 546 的五步除法。它是在应用算法，并未证明一般定理。