用欧几里得算法计算最大公因数

1. 声音
   观察依据

   开场说明最大公约数，并用整数对举例。

2. 公式
   观察依据

   开场说明最大公约数，并用整数对举例。

gcd(a,b)

能同时整除整数 a 和 b 且无余数的最大整数。

整数 a 和 b，不全为零；GCD 取正值。

1. 公式
   观察依据

   板书引理用整数变量陈述交换、整除与同余性质。

a, b, c

用于陈述 GCD 性质和欧几里得算法的整数变量。

整数

1. 公式
   观察依据

   板书把可整除的差写成模数的整数倍。

2. 声音
   观察依据

   板书把可整除的差写成模数的整数倍。

y

一个整数，使得 by = a - c，由整除条件 b | (a - c) 推导得出。

整数

1. 公式
   观察依据

   板书把同一个最大公约数依次写为不同整数对的最大公约数。

2. 声音
   观察依据

   板书把同一个最大公约数依次写为不同整数对的最大公约数。

$\gcd(\cdot,\cdot)$

两个整数的最大公约数。

此处用于整数对，如 $(a,b)$、$(b,c)$、$(b,r_1)$ 和 $(r_1,r_2)$。

1. 公式
   观察依据

   板书把一个整数替换为减去另一个整数倍所得的差。

2. 声音
   观察依据

   板书把一个整数替换为减去另一个整数倍所得的差。

$a,b,c$

在证明 $\gcd(a,b)=\gcd(b,c)$ 的引理中出现的整数，条件为 $b\mid a-c$。

整数。

1. 公式
   观察依据

   整数倍系数出现在整除等式与其移项结果中。

2. 声音
   观察依据

   整数倍系数出现在整除等式与其移项结果中。

$y$

见证 $a-c$ 是 $b$ 的倍数的整数。

$y\in\mathbb{Z}$。

1. 公式
   观察依据

   原片引入公约数并追踪正向整除关系，未单独展示反向论证。

2. 声音
   观察依据

   原片引入公约数并追踪正向整除关系，未单独展示反向论证。

1. 视频口头将 $d$ 识别为最大公约数，但显示的线条仅在后来关于 gcd 相等的结论之前明确陈述了 $d\mid a$ 和 $d\mid b$。

$d$

证明中使用的 $a$ 和 $b$ 的整数因子；口头处理为最大公约数。

$d\in\mathbb{Z}$。

1. 公式
   观察依据

   板书在公约数论证中使用整除符号。

2. 声音
   观察依据

   板书在公约数论证中使用整除符号。

$\mid$

整除关系：$x\mid y$ 表示 $x$ 整除 $y$。

整数。

1. 公式
   观察依据

   连续带余除法引入商与余数，并用方框突出递减界。

2. 声音
   观察依据

   连续带余除法引入商与余数，并用方框突出递减界。

$q_1,q_2,r_1,r_2$

欧几里得算法连续除法步骤中的商和余数。

整数，由除法算法上下文隐含余数界限 $0\le r_1<b$ 和 $0\le r_2<r_1$；黑板仅明确显示 $r_1<b$ 和 $r_2<r_1$。

1. 公式
   观察依据

   板书在最大公约数归约等式中使用被除数。

a

最大公约数函数的第一个整数输入。

有序正整数算法中的正整数；基本情况允许非负值。

1. 公式
   观察依据

   板书在最大公约数归约等式中使用除数。

b

最大公约数函数的第二个整数输入。

非负整数；进行除法时必须为正。

1. 公式
   观察依据

   递减余数链在终止论证中达到零。

$r_k$

欧几里得余数链中的非负余数；编辑约定 $r_0=b$ 以涵盖第一步即整除的情形。

非负整数

1. 声音
   观察依据

   定义和小数值例子介绍正公约数与互质。

2. 公式
   观察依据

   定义和小数值例子介绍正公约数与互质。

两个整数的 GCD 是能同时整除这两个数且无余数的最大正整数。如果两个数的 GCD 为 1，则称它们互质。

1. 整数 a 和 b，不全为零；使用最大的正公约数。

1. 声音
   观察依据

   讲解把向下枚举公约数与更快的余数算法作比较。

寻找 GCD 的一种朴素方法是检查从较小数到 1 的每一个整数，看它是否能同时整除这两个数。这种方法具有线性时间复杂度，对于大数来说效率低下。

1. 正整数输入；在单位成本算术模型下，最坏情况下的整除测试次数与 min(a,b) 成线性关系。

1. 最大公约数 (GCD) 的定义

1. 公式
   观察依据

   板书第一项说明交换两个输入不改变最大公约数。

2. 声音
   观察依据

   板书第一项说明交换两个输入不改变最大公约数。

GCD 函数参数的顺序不影响结果。

1. 整数 a 和 b，不全为零。

1. 最大公约数 (GCD) 的定义

1. 公式
   观察依据

   下一项讨论一个正整数输入能够整除另一个输入的情况。

2. 声音
   观察依据

   下一项讨论一个正整数输入能够整除另一个输入的情况。

如果正整数 a 整除另一个整数 b，那么 a 和 b 的最大公约数就是 a。

1. $a > 0$

2. a 整除 b (a|b)

1. 最大公约数 (GCD) 的定义

1. 公式
   观察依据

   板书第三项用同余关系保持与模数的公约数。

2. 声音
   观察依据

   板书第三项用同余关系保持与模数的公约数。

如果两个整数 a 和 c 对模 b 同余，它们与 b 的最大公约数是相同的。这一性质是欧几里得算法的基础，允许减小大数的计算规模。

1. 整数 a 和 c；正整数模数 b。

1. 最大公约数 (GCD) 的定义

1. 公式
   观察依据

   板书保留最大公约数的交换性质。

视频列出一个基本事实：交换两个参数不会改变最大公约数。

1. 整数 $(a,b)$ 不全为零；GCD 为正。

1. 公式
   观察依据

   板书保留正整数能够整除另一个整数的特殊情况。

如果 $a$ 为正且整除 $b$，那么 $a$ 和 $b$ 的最大公约数恰好是 $a$。

1. $a>0$

2. $a\mid b$

1. gcd 的对称性

1. 公式
   观察依据

   原片展示同余引理及正向公约数论证，公开笔记中的反向论证是编辑补充。

2. 声音
   观察依据

   原片展示同余引理及正向公约数论证，公开笔记中的反向论证是编辑补充。

1. 较早的原生引理帧确认了同余，而不是模型读取的集合成员记号。源显示正向因子蕴含；逆向由编辑补充。

对于整数 $a,c$ 和正整数 $b$，把 $a$ 替换为 $c=a-by$ 保持最大公约数。原片展示正向公约数蕴含。编辑补充：$b$ 和 $c$ 的公约数也整除 $a=c+by$，因此两组正公约数相同。

1. $a,c,y\in\mathbb Z$，$b>0$ 是整数。

2. $c=a-by$。

1. gcd 的对称性

1. 公式
   观察依据

   板书把被除数与除数替换为除数与余数，保持最大公约数。

2. 声音
   观察依据

   板书把被除数与除数替换为除数与余数，保持最大公约数。

欧几里得算法被呈现为对除法余数重复应用归约引理：将 $(a,b)$ 替换为 $(b,r_1)$，然后是 $(r_1,r_2)$，依此类推，每一步都保持 gcd 不变。

1. 整数输入 $a\ge b>0$，具有标准非负除法余数。

2. 仅在 $r_1$ 为正时继续用该余数作除数；为零时停止。

1. 减去倍数下的 gcd 归约

1. 公式
   观察依据

   板书完成余数链并指出最后的正除数。

2. 声音
   观察依据

   板书完成余数链并指出最后的正除数。

对正整数输入，把整数对替换为除数与非负余数。余数为零时返回前一个正除数；第一步即整除时返回原除数。

1. 非负整数输入不全为零；展示的除法链使用 $a\ge b>0$。

2. 递归除法要求 $b>0$ 并使用非负余数；当 $b=0$ 时返回 $a$。

1. 公式
   观察依据

   复杂度幻灯片讨论余数界与对数级调用次数；公开算术成本条件为编辑补充。

2. 公式
   观察依据

   复杂度幻灯片讨论余数界与对数级调用次数；公开算术成本条件为编辑补充。

对有序正整数输入，至多两次递归调用后，较大参数降到此前值的一半以下，除非算法已经终止。单位成本算术模型下，这给出按数值量级计算的对数级取余调用次数。

1. 整数 $a>b>0$；$N=a+b$ 表示数值量级，不是二进制位数。

2. 每次取余按单位成本计数；这里不是所有位运算次数的界。

1. 欧几里得算法原理

1. 声音
   观察依据

   原片把交换、整除与同余性质归为支撑算法的引理。

2. 公式
   观察依据

   原片把交换、整除与同余性质归为支撑算法的引理。

欧几里得算法依赖于 GCD 的三个性质：交换律、一个数整除另一个数的情况，以及 GCD 与模同余之间的关系。

1. 前两部分需要其陈述的整数和正性条件；同余用于正模数 b。

对满足每一部分特定条件的整数 a, b, c 进行全称量化。

1. 公式
   观察依据

   讲解把前述最大公约数性质与余数算法联系起来。

2. 声音
   观察依据

   讲解把前述最大公约数性质与余数算法联系起来。

视频提出三个引理——gcd 的对称性、一个正整数整除另一个时的 gcd，以及在减去倍数下 gcd 的保持——作为解释欧几里得算法的基础。

1. 整数处于通常的 gcd 设置中。

2. 对于第二个引理，$a>0$ 且 $a\mid b$。

3. 对于第三个引理，$b\mid a-c$。

在每个引理中显示的整数变量上的全称量词。

1. 公式
   观察依据

   原片在展示正向蕴含后陈述最大公约数相等，该相等结论需要笔记补充的反向蕴含。

2. 声音
   观察依据

   原片在展示正向蕴含后陈述最大公约数相等，该相等结论需要笔记补充的反向蕴含。

1. 显示的证明明确追踪了一个公因子 $d$；完全严谨还需要反向包含或诉诸 gcd 的定义，这在此片段中没有单独写出。

在条件 $b\mid a-c$ 下，$a$ 和 $b$ 的最大公约数等于 $b$ 和 $c$ 的最大公约数。

1. $a,c\in\mathbb Z$，$b>0$ 是整数。

2. $b\mid(a-c)$。

对于满足假设的所有整数 $a,c$ 和正整数 $b$。

1. 公式
   观察依据

   实际复杂度幻灯片比较新余数与先前被除数的一半。

对整数 $a>b>0$，新的第二个参数 $a\bmod b$ 至多是此前第一个参数 $a$ 的一半。

1. $a > b > 0$

对于所有有效输入 a, b

1. 公式
   观察依据

   板书从把差写成整数倍开始同余论证，后续画面继续该论证。

2. 声音
   观察依据

   板书从把差写成整数倍开始同余论证，后续画面继续该论证。

1. 只有这个论证的开头位于前 0–101 秒的分析区间内；完整源视频继续。反向公约数蕴含关系将作为编辑性的数学澄清提供。

1. 公式

   $$a \equiv c \pmod b$$
   解释

   从假设 a ≡ c (mod b) 开始。

   步骤依据

   引理第三部分的假设。

   视频直接表达
2. 公式

   $$b \mid (a - c)$$
   解释

   根据同余的定义，b 必须整除 a 和 c 之间的差。

   步骤依据

   模同余的定义。

   视频直接表达
3. 公式

   $$\exists y \in \mathbb{Z}, by = a - c$$
   解释

   这意味着存在一个整数 y，使得 by 等于 a 减 c。

   步骤依据

   整除的定义。

   视频直接表达

显示的方程开始了论证。源视频在此分析区间之后继续；仅凭这个部分推导尚未建立两个 GCD 相等。

1. 公式
   观察依据

   板书推出公约数整除差并陈述相等结论，反向公约数集合论证为编辑补充。

2. 声音
   观察依据

   板书推出公约数整除差并陈述相等结论，反向公约数集合论证为编辑补充。

1. 片段清楚显示了正向整除链，但没有单独显示为了完全对称地证明 gcd 集合相等所需的反向包含。

1. 公式

   $$\exists y\in\mathbb{Z}\; by=a-c$$
   解释

   从 $b$ 整除 $a-c$ 的假设开始，因此存在整数 $y$ 使得 $by=a-c$。

   步骤依据

   整除的定义。

   视频直接表达
2. 公式

   $$c=a-by$$
   解释

   移项，把 $c$ 用 $a$、$b$ 和 $y$ 表示。

   步骤依据

   $by=a-c$ 的代数重排。

   视频直接表达
3. 公式

   $$\exists d\in\mathbb{Z},\ d\mid a,\ d\mid b$$
   解释

   取整数 $d$ 同时整除 $a$ 和 $b$；原讲解将其放在最大公约数语境中。

   步骤依据

   证明设置中的假设 / 公因子的定义。

   视频直接表达
4. 公式

   $$d\mid a-by$$
   解释

   因为 $d$ 整除 $a$ 和 $b$，它也整除组合 $a-by$。

   步骤依据

   整除在整数线性组合下的封闭性；说话者将其描述为乘以 $b$ 的因子。

   视频直接表达
5. 公式

   $$d\mid c$$
   解释

   因为 $c=a-by$，之前的整除陈述变为 $d\mid c$。

   步骤依据

   使用 $c=a-by$ 进行替换。

   视频直接表达
6. 公式

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

   源在正向蕴含后陈述相等。为了完成证明，还需取 $b$ 和 $c$ 的任何正因子；它整除 $a=c+by$。因此两个正公因子集合重合。

   步骤依据

   编辑的反向包含，连同观察到的正向包含，证明了 GCD 的相等。

   补充解释

该等式对于整数 $a,c$ 和正整数 $b$ 是正确的。其完整证明使用了两个公因子蕴含；上述反向蕴含是编辑性的，未在源中单独显示。

1. 公式
   观察依据

   板书展示连续符号除法及对应的最大公约数等式。

2. 声音
   观察依据

   板书展示连续符号除法及对应的最大公约数等式。

1. 停止情况在此 101–202 秒分析区间之外，并在完整源的后半部分解释。

1. 公式

   $$a=bq_1+r_1,\ 0\le r_1<b$$
   解释

   应用 $a$ 除以 $b$ 引入商 $q_1$ 和余数 $r_1$。

   步骤依据

   整数除法算法。

   补充解释
2. 公式

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

   将配对 $(a,b)$ 替换为 $(b,r_1)$ 而不改变 gcd。

   步骤依据

   归约引理，配合编辑的反向因子论证完成。

   视频直接表达
3. 公式

   $$b=r_1q_2+r_2,\ 0\le r_2<r_1$$
   解释

   当 $r_1>0$ 时，将 $b$ 除以 $r_1$；否则停止。

   步骤依据

   整数除法算法。

   补充解释
4. 公式

   $$\gcd(b,r_1)=\gcd(r_1,r_2)$$
   解释

   重复相同的归约，从 $(b,r_1)$ 传递到 $(r_1,r_2)$。

   步骤依据

   对下一对应用相同的归约引理。

   视频直接表达
5. 公式

   $$\dots$$
   解释

   只要当前除数为正就重复。正整数余数严格递减，因此过程终止而不是无限继续。

   步骤依据

   编辑的非负整数下降；下一个源区间呈现终止规则。

   补充解释

欧几里得算法是通过迭代恒等式 $\gcd(x,y)=\gcd(y,\operatorname{rem}(x,y))$ 经过逐渐变小的余数获得的。

1. 公式
   观察依据

   实际幻灯片用反证法建立余数界，其中零商旁注有笔误；对应公开步骤已由编辑修正。

1. 实际幻灯片误写零商会推出 $k=b$；正确结果是 $k=a$。下面的商界步骤是编辑修正，并非照抄该错误旁注。

1. 公式

   $$a \% b = k, \quad k > a/2$$
   解释

   在整数 $a>b>0$ 条件下，反设余数大于被除数的一半。

   步骤依据

   反证法假设

   补充解释
2. 公式

   $$a = q \cdot b + k, \quad k < b$$
   解释

   根据取模的定义，a 可以写成商乘以除数加上余数，其中余数小于除数。

   步骤依据

   除法算法

   视频直接表达
3. 公式

   $$a/2 < k < b < a$$
   解释

   结合假设 $k > a/2$ 和 $k < b$ 得到这个不等式链。

   步骤依据

   不等式的传递性

   视频直接表达
4. 公式

   $$q = 1$$
   解释

   由 $b>a/2$ 可排除至少为二的商，且 $a>b$ 要求商为正，因此 $q=1$。特别地，零商会得到 $k=a$，而非幻灯片写的 $k=b$。

   步骤依据

   编辑修正后的整数商界。

   补充解释
5. 公式

   $$k + b > a/2 + a/2 = a$$
   解释

   将 $q=1$ 代入 $a = b + k$ 得到 $a = b + k$。但我们已确立 $k > a/2$ 且 $b > a/2$，所以它们的和超过 a。

   步骤依据

   算术代换

   视频直接表达
6. 公式

   $$a>a$$
   解释

   我们推导出 $k + b > a$，但方程 $a = q*b + k$ 在 $q=1$ 时意味着 $a = b + k$。这是一个矛盾。

   步骤依据

   逻辑矛盾

   补充解释

假设的大余数不可能存在，因此 $k\le a/2$。把这个界应用到两次调用，可得到限制取余调用次数所需的参数缩减。

1. 公式
   观察依据

   开场显示小整数对以说明最大公约数与互质；下面的公约数列表是编辑核算。

2. 声音
   观察依据

   开场显示小整数对以说明最大公约数与互质；下面的公约数列表是编辑核算。

求几对整数的 GCD。

1. 对：(7, 21), (24, 30), (7, 9)

确定每对数的最大公约数。

1. 解释

   对于 7 和 21，7 整除 21，所以 GCD 是 7。

   步骤依据

   GCD 的定义。

   视频直接表达
2. 解释

   对于 24 和 30，公约数是 1, 2, 3, 6。最大的是 6。

   步骤依据

   GCD 的定义。

   补充解释
3. 解释

   对于 7 和 9，唯一的公约数是 1。

   步骤依据

   GCD 的定义。

   视频直接表达

GCD(7, 21) = 7; GCD(24, 30) = 6; GCD(7, 9) = 1。

演讲者指出，由于 GCD(7, 9) = 1，数字 7 和 9 是互质的。

1. 图示
   观察依据

   开场用一对整数提出高效计算最大公约数的问题。

1. 文本框

2. 蓝色背景

1. 从通用标题过渡到具体问题示例。

开场以一对较大整数引出高效求最大公约数的方法；该数值只用作问题动机，原片没有逐步计算这一对数。

1. 图示
   观察依据

   网格白板呈现编号引理与逐步写出的等式。

2. 动画
   观察依据

   网格白板呈现编号引理与逐步写出的等式。

1. 网格纸背景

2. 手写文本和公式

1. 引理陈述的出现。

2. 引理第三部分证明步骤的顺序书写。

1. 当证明第三部分时，引理的前两部分保持静止。

板书按引理陈述和逐步等式组织论证；反向公约数推理需要编辑补充。

1. 图示
   观察依据

   网格板书在编号引理下逐行添加代数关系。

2. 动画
   观察依据

   网格板书在编号引理下逐行添加代数关系。

1. “欧几里得算法”标题

2. 手写引理列表

3. 带有 $\exists y\in\mathbb{Z}$、$c=a-by$、$\exists d\in\mathbb{Z}$、整除陈述和 $\gcd(a,b)=\gcd(b,c)$ 的证明行

1. 行在引理列表下方一个接一个添加。

2. 证明从假设 $by=a-c$ 增长到结论 $\gcd(a,b)=\gcd(b,c)$。

1. 黑板保持为单个静态书写表面，没有坐标轴或几何图形。

2. 引理编号在证明上方保持可见。

板书组织归约论证；正向关系来自原片，公开反向论证明确标为编辑补充。

1. 动画
   观察依据

   画面移向较低书写区域以展示连续余数等式。

2. 图示
   观察依据

   画面移向较低书写区域以展示连续余数等式。

1. 滚动的黑板视图

2. 连续除法的新手写方程

3. 表示延续的省略号

1. 早期的引理证明向上移出主要焦点。

2. 下方写入新行以将引理应用于除法余数。

3. 最终可见状态在第二次归约后包括一个省略号。

1. 相同的数学主题从引理延续到算法。

2. 未引入数值示例；推导保持符号化。

滚动标志着从证明关键引理到将其用作欧几里得算法递归机制的转变。

1. 动画
   观察依据

   板书画面移动，把余数链与前述最大公约数性质联系起来。

1. 手写数学方程

1. 视图垂直移动以显示上下文

1. 相机平移时方程保持静止

视觉辅助工具，用于将最终结果与初始引理定义联系起来。

1. 图示
   观察依据

   原片展示带零除数判断的 Java 风格递归函数。

1. 代码块

1. 从白板过渡到打字代码

1. 代码逻辑与数学推导相匹配

演示递归数学定义如何直接转化为编程语法。

1. 声音
   观察依据

   讲解通过与逐个测试候选数比较，引出更高效的算法。

人们可能认为检查所有向下到 1 的数字是计算 GCD 的一种可行策略。

视频强调这种暴力方法具有线性时间复杂度，对于大数来说太慢，从而引出欧几里得算法。

1. 公式
   观察依据

   原片明确展示正向公约数蕴含，随后给出相等结论。

2. 声音
   观察依据

   原片明确展示正向公约数蕴含，随后给出相等结论。

人们可能认为仅通过显示 $a$ 和 $b$ 的每个公因子都整除 $c$，写下的链条就证明了两个 gcd 的相等。

为了严谨地证明 $\gcd(a,b)=\gcd(b,c)$，还需要反向包含（或使用最大公约数定义的等效论证）。片段明确显示正向方向，然后陈述相等。

1. 公式
   观察依据

   此分析区间在余数链仍继续时结束，完整原片随后解释终止规则。

2. 声音
   观察依据

   此分析区间在余数链仍继续时结束，完整原片随后解释终止规则。

观众可能假设显示的链条已经指定了完整的欧几里得算法。

此 101–202 秒区间建立了归约机制。完整源稍后在余数变为 $0$ 时停止并返回前一个正因子；没有完整源媒体遗漏。

1. 声音
   观察依据

   原片从直接枚举公约数转向欧几里得算法。

欧几里得算法被提出作为一种专门用于应用和计算最大公约数的高效方法。

1. 公式
   观察依据

   同余陈述为后续最大公约数归约提供不变量。

同余保持了与模数的公约数，并被应用于减少 GCD 计算；这是一种不变量，而不是 GCD 定义的推广。

1. 声音
   观察依据

   余数步骤使用经编辑补全的公约数不变量。

2. 公式
   观察依据

   余数步骤使用经编辑补全的公约数不变量。

归约引理，配合其编辑的反向公因子补充，证明了每个欧几里得余数步骤。

1. 公式
   观察依据

   最大公约数相等陈述交换了整数对的顺序。

2. 声音
   观察依据

   最大公约数相等陈述交换了整数对的顺序。

1. 片段在结论时刻没有明确指向对称引理；连接是从显示的陈述推断出来的。

gcd 的对称性允许归约结果以第二个参数为先的形式写出，产生算法中使用的形式 $\gcd(a,b)=\gcd(b,c)$。

1. 公式
   观察依据

   带余除法等式提供最大公约数的下一组参数。

2. 声音
   观察依据

   带余除法等式提供最大公约数的下一组参数。

每个欧几里得步骤都是在将被除数表示为除数乘以商加余数后，归约引理的一个实例。

1. 声音
   观察依据

   讲解把递归函数与前述余数规则联系起来。

数学原理被直接应用于编写递归函数。

1. 公式
   观察依据

   余数界用来说明递归调用次数为何是对数级。

修正后的减半论证说明有序正整数输入在单位成本算术模型下具有对数级递归取余调用次数。

1. 声音
   观察依据

   原片比较直接搜索所需的算术测试次数。

1. 求 GCD 的暴力法

1. 公式
   观察依据

   同余引理陈述两个最大公约数表达式相等。

1. GCD 与模同余

1. 公式
   观察依据

   开头的板书等式把同余转化为整除。

1. GCD 与模同余性质的证明（第 1 部分）

1. 公式
   观察依据

   板书把减去整数倍与保持公约数联系起来。

2. 声音
   观察依据

   板书把减去整数倍与保持公约数联系起来。

1. 减去倍数下的 gcd 归约
2. 证明 $b\mid a-c$ 蕴含 $\gcd(a,b)=\gcd(b,c)$

1. 公式
   观察依据

   连续带余除法旁边写有最大公约数相等的恒等式。

2. 声音
   观察依据

   连续带余除法旁边写有最大公约数相等的恒等式。

1. 欧几里得算法归约规则
2. 欧几里得算法的递归归约链

1. 公式
   观察依据

   突出的余数不等式说明递减与终止的依据。

2. 声音
   观察依据

   突出的余数不等式说明递减与终止的依据。

1. 欧几里得算法归约规则
2. 欧几里得算法的递归归约链

1. 公式
   观察依据

   原片把参数缩减与对应调用次数作比较。

1. 欧几里得算法的时间复杂度
2. 余数减半性质

1. 公式
   观察依据

   展示的函数在第二个参数为零时返回第一个参数。

1. 欧几里得算法原理