详细描述欧几里得算法（附证明）

1. 公式
   观察依据

   幻灯片上出现 $\gcd(a, b) =$ max {k | k|a 且 k|b} 以及 $\gcd(a, b) = \gcd(|a|, |b|)$。

2. 声音
   观察依据

   讲解者提到“最大公因子”并读出等价定义。

gcd(a, b)

a 和 b 的最大公因子

整数输入不同时为零；最大公因数及共同因子按正整数处理（本站明确范围）

1. 公式
   观察依据

   幻灯片定义中使用字母 a、b、c 表示整数及其公因子。

a, b, c

a 和 b 为待求最大公因子的整数，c 为其最大公因子候选

整数输入不同时为零；最大公因数及共同因子按正整数处理（本站明确范围）

1. 公式
   观察依据

   幻灯片使用 k|a 与 k|b 表示整除关系。

2. 声音
   观察依据

   讲解者专门说明整除记号中谁是被除数、谁是除数。

|

整除符号；k|a 表示 k 整除 a

整数之间的整除关系

1. 公式
   观察依据

   等价定义写作 max {k | k|a 且 k|b}。

k

同时整除 a 和 b 的公因子

整数输入不同时为零；最大公因数及共同因子按正整数处理（本站明确范围）

1. 公式
   观察依据

   幻灯片给出 $\gcd(a, b) = \gcd(|a|, |b|)$。

|a|, |b|

a 和 b 的绝对值

实数/整数上的绝对值

1. 公式
   观察依据

   幻灯片正文写出 $\gcd(a,b)$，并在 Notes 中写出 k | a 与 $a = mk$。

2. 声音
   观察依据

   原音解释：k 整除 a 等价于 a 等于 m 倍的 k。

a, b

被讨论最大公因子的两个整数。

整数；在后续证明页中进一步限定为 $a ≥ b > 0$。

1. 公式
   观察依据

   第一页定义句为称 c 为 a 和 b 的最大公因子。

c

候选的最大公因子。

正整数；整数输入不同时为零（本站范围明确）

1. 公式
   观察依据

   页面写出 $\gcd(a,b)=$max{k, 其中 k|a 且 k|b}，Notes 又写出 k|a。

2. 声音
   观察依据

   讲解者解释整除记号|的左右项角色。

k

同时整除 a 与 b 的公因子候选。

共同正因子；整数输入不同时为零（本站范围明确）

1. 公式
   观察依据

   Notes 中给出 $a = mk$。

2. 声音
   观察依据

   讲解者把 k|a 读作a 等于 m 倍的 k。

m

使 $a = mk$ 成立的倍数。

整数。

1. 公式
   观察依据

   第二页写记 d 为 a 和 b 的最大公因子，并列出 $d = \gcd(a,b)$。

2. 声音
   观察依据

   原音说明：记 d 为 a 和 b 的最大公因子。

d

a 与 b 的最大公因子。

正整数。

1. 公式
   观察依据

   页面写出 $a = q_1·b + r_1$，且 $q_1 =$ floor($a / b$)。

2. 声音
   观察依据

   原音说明：$q_1$ 称它为商。

3. 动画
   观察依据

   152秒出现商的标注，指向$q_1$。

q₁

带余除法中的商。

整数。

1. 公式
   观察依据

   页面写出 $0 ≤ r_1 < b$。

2. 声音
   观察依据

   原音说明：$r_1$ 的值介于 0 和 b 之间$r_1$ 称它为余数。

3. 动画
   观察依据

   157秒出现余数标注，指向$r_1$。

r₁

a 除以 b 的余数。

整数，满足 $0 ≤ r_1 < b$。

1. 公式
   观察依据

   幻灯片标题为“1、定义最大公因子 (Greatest Common Divisor)”，并列出两条判定条件。

2. 声音
   观察依据

   讲解者逐条解释条件一和条件二。

3. 公式
   观察依据

   本站将共同因子、正数约定及不同时为零的范围写清；未把补充条件归作原片原话。

$c$ 必须是 $a,b$ 的共同因子，且两个数的任何共同因子都整除 $c$。这区分是否为公因子与是否满足最大性；不把只整除其中一个输入的数纳入第二条件。本站补充 $c>0$、输入不同时为零的明确范围。

1. 整数 $a,b$ 不同时为零（本站范围说明）

2. $c$ 是正整数，且同时整除 $a,b$

3. 任意共同正因子都整除 $c$

1. gcd(a, b)
2. a, b, c
3. |

1. 公式
   观察依据

   幻灯片写出 $\gcd(a, b) =$ max {k | k|a 且 k|b}，并进一步写出 $\gcd(a, b) = \gcd(|a|, |b|)$。

2. 声音
   观察依据

   讲解者说明因为所求最大公因子是正数，所以可化为绝对值形式。

3. 公式
   观察依据

   本站将共同因子、正数约定及不同时为零的范围写清；未把补充条件归作原片原话。

以共同正因子的最大值定义 $\gcd(a,b)$，可以看出输入变号不影响公因子结构；所以取绝对值保持最大公因数。本站明确限定输入不同时为零。

1. 整数 $a,b$ 不同时为零（本站明确排除无法取最大值的情况）

2. $k$ 是同时整除 $a,b$ 的正整数

1. 最大公因子的定义
2. k
3. |a|, |b|

1. 公式
   观察依据

   幻灯片底部 Notes 说明整除记号“|”区分谁是被除数、谁是除数，并举例 k|a 等价于 $a = mk$。

2. 声音
   观察依据

   讲解者口头强调整除记号的左右项角色。

视频专门说明整除记号“|”的方向：左边是除数，右边是被除数。以 k|a 为例，它等价于存在整数 m 使 $a = mk$。

1. 用于整数间的整除关系

2. 左侧是除数，右侧是被除数

1. |
2. k

1. 公式
   观察依据

   第一页标题为1、定义最大公因子 (Greatest Common Divisor)。

2. 公式
   观察依据

   正文列出两条：1. c 是 a 和 b 的因子；2. a 和 b 的任何因子都是 c 的因子。

正整数 $c$ 是两个输入的共同因子，且它们的任何共同正因子都整除 $c$。共同因子不是只整除其中一个数的因子；本站明确输入为不同时为零的整数。

1. 整数输入不同时为零；最大公因数取正值（本站范围说明）

2. 第二条件量化两个输入的共同正因子

1. 整除记号的读法与角色

1. 公式
   观察依据

   页面写出以下是一个等价定义：$\gcd(a, b) =$ max {k, 其中 k | a 且 k | b}。

最大公因数是共同正因子中的最大值。本站明确输入不同时为零，避免同时为零时集合没有最大值。

1. 整数输入不同时为零（本站明确范围）

2. 候选为共同正因子

1. 最大公因子的两条件定义

1. 公式
   观察依据

   第一页黄色文字写出 $\gcd(a,b)=\gcd(a,-b)=\gcd(-a,b)=\gcd(-a,-b)=\gcd(|a|,|b|)$。

视频直接给出一个性质链：改变 a、b 的符号不会改变最大公因子，因此可把讨论归约到非负绝对值情形。

1. 整数输入不同时为零（本站范围说明）

1. 最大公因子的两条件定义
2. 最大公因子的集合最大值定义

1. 公式
   观察依据

   Notes 写整除记号 ‘|’ 区分谁是被除数，谁是除数的问题。例如 k | a 等价于 $a = mk$。

2. 声音
   观察依据

   原音说明：k 整除 a 等价于 a 等于 m 倍的 k。故而左手项是除数，右手项是被除数。

视频专门解释竖线记号的方向性：左侧是除数，右侧是被除数；k|a 的含义是存在整数 m 使 $a=mk$。

1. k、a、m 为整数。

2. 视频强调这是记忆要点，不是推导。

1. 公式
   观察依据

   第二页标题为2、欧几里得算法的证明。

2. 公式
   观察依据

   正文写求整数 a 和 b 的最大公因子，不妨假设 $a ≥ b > 0$，记 d 为 a 和 b 的最大公因子。

3. 声音
   观察依据

   原音说明：下面正式开始证明欧几里得算法……不妨假设 a 大于等于 b 大于 0。

视频进入证明时先固定目标：求整数 a 与 b 的最大公因子；再作不失一般性的排序假设 $a ≥ b > 0$，并把最大公因子记为 d。

1. a、b 为整数。

2. 证明页明确假设 $a ≥ b > 0$。

1. 最大公因子的两条件定义
2. 最大公因子的集合最大值定义

1. 公式
   观察依据

   页面写由除法的定义，可以得到：$a = q_1 · b + r_1$。（$q_1 =$ floor($a / b$), $0 ≤ r_1 < b$。）

2. 声音
   观察依据

   原音解释带余除法等式、向下取整的商以及余数非负且小于除数的范围。

3. 动画
   观察依据

   149至158秒依次出现被除数、商、除数和余数标注。

视频把证明中的关键工具定义为带余除法：a 被写成 $q_1b+r_1$，其中 $q_1$ 是商，$r_1$ 是余数，且余数严格小于除数 b。画面还用标注框把 a、$q_1$、b、$r_1$ 分别命名为被除数、商、除数、余数。

1. 用于 $a ≥ b > 0$ 的整数除法场景。

2. 视频未单独证明该除法定义，只是直接引用。

1. 欧几里得算法证明的初始设定

1. 公式
   观察依据

   幻灯片标题为“2、欧几里得算法的证明”，正文开头写有“求整数 a 和 b 的最大公因子，不妨假设 $a ≥ b > 0$，记 d 为 a 和 b 的最大公因子”。

2. 声音
   观察依据

   讲解者在这一段围绕 d 对 a、b 的整除性以及后续推导展开说明。

本片段进入“欧几里得算法的证明”部分，先把问题设定为：给定整数 a 和 b，且不妨假设 $a ≥ b > 0$；记 d 为 a 和 b 的最大公因子。随后由除法定义引入商 $q_1$ 和余数 $r_1$，建立 a 与 b、$r_1$ 之间的关系，为证明 $\gcd(a,b)=\gcd(b,r_1)$ 做准备。

1. a、b 为整数

2. 视频中明确假设 $a ≥ b > 0$

3. $q_1$ 与 $r_1$ 由除法定义给出

1. 公式
   观察依据

   幻灯片写有“∵式和②式，∴ $d | (a - q_1·b) = d | r_1$ …④”以及“∵②式和④式，∴ d 同时是 b 和 $r_1$ 的公因子”。

2. 声音
   观察依据

   原音把最大公因数对两个输入的整除性用于差的线性组合，得到它整除余数，因而也是新数对的共同因子。

这一方法先利用 $d=\gcd(a,b)$ 得到 $d\mid a$ 与 $d\mid b$，再利用整除对线性组合封闭的性质，推出 $d\mid(a-q_1b)$。由于 $a-q_1b=r_1$，于是 $d\mid r_1$。再结合 $d\mid b$，就得到 d 同时是 b 和 $r_1$ 的公因子。这一步证明了“公共因子集合的一个元素 d 属于 (b,$r_1$) 的公因子集合”的方向。

1. 已设定 $d=\gcd(a,b)$

2. 已使用 $a=q_1b+r_1$

3. 使用整除对线性组合封闭的性质

1. 欧几里得算法正确性证明的起始设定

1. 公式
   观察依据

   证明下半页任取新数对的共同因子c，用$q_1b+r_1=a$恢复c对a的整除性；c也是原数对的共同因子，所以$c≤d$。结合d本身整除b与$r_1$，最后得到新数对的最大公因数等于d。

2. 声音
   观察依据

   原音依次解释任取c、通过和的线性组合恢复c整除a、比较c与原最大公因数d，最后合并前半段得到相同最大公因数。

在完成“d 是 b 与 $r_1$ 的公因子”之后，视频继续证明最大性：任取 b 与 $r_1$ 的一个公因子 c，则 $c\mid b$ 且 $c\mid r_1$，因此 c 整除它们的线性组合 $q_1b+r_1$。由于 $q_1b+r_1=a$，得到 $c\mid a$；又已知 $c\mid b$，所以 c 也是 a 与 b 的公因子。因为 $d=\gcd(a,b)$，任何 a、b 的公因子都不超过 d，故 $c\le d$。再结合前面已证 d 本身是 b、$r_1$ 的公因子，可知 b、$r_1$ 的最大公因子正好等于 d。

1. 任取 c 为 b 与 $r_1$ 的公因子

2. 使用 $a=q_1b+r_1$

3. 使用 $d=\gcd(a,b)$ 的最大性定义

1. 欧几里得算法正确性证明的起始设定
2. 从 $\gcd(a,b)$ 推出 d 是 b 与 $r_1$ 的公因子

1. 公式
   观察依据

   页面新增黄色文字大胆假设：a 和 b 的最大公因子等价于 b 和 $r_1$ 的最大公因子。

2. 声音
   观察依据

   原音说明：下面不妨进行大胆假设，a 和 b 的最大公因子等价于 b 和 $r_1$ 的最大公因子。

1. 片段结束时只提出这一待证命题，未给出完整证明。

在当前设定下，视频提出待证命题：$\gcd(a,b)$ 等价于 $\gcd(b,r_1)$。

1. a、b 为整数。

2. $a ≥ b > 0$。

3. $a = q_1·b + r_1$，且 $0 ≤ r_1 < b$。

针对满足上述条件的整数 a、b 及其带余除法余数 $r_1$。

1. 公式
   观察依据

   幻灯片先写“大胆假设：a 和 b 的最大公因子等价于 b 和 $r_1$ 的最大公因子”，随后通过两段论证得到“c_max = $d = \gcd(b, r_1)$。证毕。”

2. 声音
   观察依据

   讲解者在结尾明确说“c_max就是b和$r_1$的最大公因子，证毕”。

在整数 a、b 满足 $a ≥ b > 0$，且 $a=q_1b+r_1$、$0≤r_1<b$ 的条件下，有 $\gcd(a,b)=\gcd(b,r_1)$。

1. a、b 为整数

2. $a ≥ b > 0$

3. $a=q_1b+r_1$

4. $q_1=\lfloor a/b\rfloor$

5. $0≤r_1<b$

对满足上述条件的整数 a、b、$q_1$、$r_1$ 成立；证明中对“任意公因子 c”使用全称论证。

1. 公式
   观察依据

   左侧明确写出 $\gcd(a,b) = \gcd(b, a$ mod b)。

2. 声音
   观察依据

   讲解者口头复述为“a和b的最大公因子等于b和余数的最大公因子”。

在该片段语境下，$\gcd(a,b)=\gcd(b, a\bmod b)$。

1. 整数 $a\ge b>0$，沿用原片此前证明条件

2. 余数由正除数带余除法确定

3. 此前双向公因数与最大性证明支持此处不变量总结

针对视频讨论的一对整数输入 a,b。

1. 公式
   观察依据

   右侧最后一行写 $d = \gcd(a,b) = r_n$，且上一行 $r_{n-1}=q_{n+1}r_n+0$。

2. 声音
   观察依据

   讲解者说“而 r n减1和 r n它是可以发生整除的。那么 d 也即最大公因子就记为 r n。”

若连续带余除法进行到 $r_{n-1}=q_{n+1}r_n+0$，则 $\gcd(a,b)=r_n$。

1. 存在如图所示的连续带余除法链。

2. $r_n$ 是最后一个非零余数。

3. $r_{n-1}$ 能被 $r_n$ 整除。

针对该余数链终止时的情形。

1. 声音
   观察依据

   原音明确区分终止的零余数与给出答案的最后正除数。

2. 公式
   观察依据

   公式页写有 $r_{n-1}=q_{n+1}r_n+0$ 与 $d=\gcd(a,b)=r_n$。

在欧几里得算法的辗转相除序列中，当某一步余数为 0 时，前一步的较小数 $r_n$ 等于原两数的最大公因数。

1. 已经按欧几里得算法连续作带余除法

2. $r_n$ 是最后一个非零余数

对满足算法过程的整数 a,b 成立

1. 公式
   观察依据

   左侧文字写有 $\gcd(a,b)=\gcd(b,a\bmod b)$。

2. 公式
   观察依据

   代码注释写有 //辗转相除 $\gcd(a,b)=\gcd(b,r)$。

求 a 与 b 的最大公因数可以转化为求 b 与 a 除以 b 的余数之间的最大公因数。

1. a,b 为整数

2. 视频代码页要求 $a \ge b > 0$

对适用输入成立

1. 公式
   观察依据

   实际末帧表格从 $a=q_1b+r_1$ 起，共10行除法；末行是 $r_8=q_{10}r_9+r_{10}$，其中 $r_{10}=0$、$r_9=1078$。

2. 声音
   观察依据

   原音统计十轮演算并给出结果1078。

对于示例输入 $a=1160718174$、$b=316258250$，视频给出的手算过程共进行 10 轮带余除法，最终得到最大公因数 1078。

1. 使用该具体测试样例

对该数值例子成立

1. 公式
   观察依据

   页面列出由已知条件可以得到：d | a …①，d | b …②，$d = \gcd(a,b)$ …③。

2. 声音
   观察依据

   讲解者逐条读出这三项。

1. 公式

   $$d\mid a$$
   解释

   因为 d 被记为 a 和 b 的最大公因子，所以 d 首先必须是 a 的因子。

   步骤依据

   使用前面给出的最大公因子定义中的“公因子”条件。

   视频直接表达
2. 公式

   $$d\mid b$$
   解释

   同理，d 也必须是 b 的因子。

   步骤依据

   使用最大公因子定义中的“公因子”条件。

   视频直接表达
3. 公式

   $$d=\gcd(a,b)$$
   解释

   页面把这一记号本身列为第③条，作为后续论证的出发点。

   步骤依据

   来自证明设定“记 d 为 a 和 b 的最大公因子”。

   视频直接表达

得到三条编号事实 ① d|a、② d|b、③ $d=\gcd(a,b)$，为后续比较 $\gcd(a,b)$ 与 $\gcd(b,r_1)$ 做准备。

1. 公式
   观察依据

   页面小心论证下写出∵①式和②式，∴ $d | (a - q_1 · b) = d | r_1$ …④。

2. 公式
   观察依据

   下一行写出∵②式和④式，∴ d 同时是 b 和 $r_1$ 的公因子。

3. 声音
   观察依据

   讲解者说到小心论证，根据一式后片段结束。

1. 片段只展示这一半方向的开头，未展示完整收尾，也未展示反方向论证。

1. 公式

   $$d\mid a,\ d\mid b$$
   解释

   先引用前面已建立的 ① 和 ②。

   步骤依据

   来自最大公因子定义。

   视频直接表达
2. 公式

   $$d\mid (a-q_1\cdot b)$$
   解释

   由于 d 同时整除 a 和 b，它也整除 a 减去 $q_1$ 倍 b 的线性组合。

   步骤依据

   使用整除对线性组合封闭的标准性质；视频未口头展开这一原理名称。

   视频直接表达
3. 公式

   $$a-q_1\cdot b=r_1$$
   解释

   由带余除法定义 $a=q_1·b+r_1$，移项可得 $a-q_1·b=r_1$。

   步骤依据

   使用前面给出的除法定义。

   视频直接表达
4. 公式

   $$d\mid r_1$$
   解释

   把上一步代入，得到 d 整除 $r_1$，这就是页面中的 ④。

   步骤依据

   等量代换。

   视频直接表达
5. 公式

   $$d\mid b\land d\mid r_1$$
   解释

   结合 ② 与新得到的 ④，说明 d 同时是 b 与 $r_1$ 的公因子。

   步骤依据

   公因子定义。

   视频直接表达

片段内可见的结论止于“d 同时是 b 和 $r_1$ 的公因子”；要完整证明 $\gcd(a,b)=\gcd(b,r_1)$，还需要继续论证最大性以及另一方向，这些在本片段中未出现。

1. 公式
   观察依据

   证明上半页列出d整除a和b、$d=\gcd(a,b)$以及$a=q_1b+r_1$，并用差的线性组合把整除性传递到$r_1$；接着说明d同时整除b和$r_1$。

2. 声音
   观察依据

   讲解者口头复述了这些步骤，并把 $a-q_1b$ 说成 a 和 b 的线性组合。