欧几里得算法例题｜Socratica

1. 公式
   观察依据

   屏幕出现文字“求 gcd(1785, 546)”；该画面位于 00:29。随后写出最终结论“$\therefore$ gcd(1785, 546) = 21”；该画面位于 01:54。

2. 声音
   观察依据

   旁白说要“求两个整数的最大公约数”（00:01），并说明“1,785 与 546 的最大公约数是 21”（01:54）。

$\gcd(a, b)$

两个整数 a 和 b 的最大公约数。

整数

1. 声音
   观察依据

   旁白解释欧几里得算法是一种通过反复进行长除法直到余数为零来求两个整数最大公约数的方法。

2. 图示
   观察依据

   从 00:18 到 00:27 的视觉示例展示了将 104 除以 84，然后将 84 除以 20，最后将 20 除以 4 的步骤，直至余数为 0。

欧几里得算法用于求两个整数的最大公约数（GCD），而无需对它们进行因式分解。该过程涉及反复进行长除法：用较大的数除以较小的数，然后用上一步的除数除以上一步的余数，并继续此过程。当余数变为零时，最后一个非零余数即为最大公约数。

1. 适用于两个整数。

2. 需要反复进行长除法。

3. 当余数为零时停止。

1. 声音
   观察依据

   旁白把概念介绍为“两个整数的最大公约数”（00:01），随后对 1785 与 546 给出具体结论（01:54）。

2. 公式
   观察依据

   符号“gcd(1785, 546)”从 00:29 开始显示在屏幕上。

两个整数的最大公约数是能同时整除这两个数且没有余数的最大正整数。在视频中，它是使用欧几里得算法求得的。

1. 定义于两个整数之上。

1. 声音
   观察依据

   旁白说道：“When you get a remainder of zero, you stop 且 the method is over. The last nonzero remainder is the greatest common divisor.”（当你得到余数为零时，你就停止，方法结束。最后一个非零余数就是最大公约数。）

2. 图示
   观察依据

   箭头指向倒数第二次除法的余数“21”（01:51），把它标识为结果。

在欧几里得算法中，当除法过程产生余数为零时，原始两个整数的最大公约数是获得的最后一个非零余数。

1. 对两个整数应用欧几里得算法。

2. 遵循反复长除法的过程，直到达到余数为零。

对于任意两个整数。

1. 图示
   观察依据

   视觉序列显示 104 除以 84（商 1，余数 20），然后 84 除以 20（商 4，余数 4），最后 20 除以 4（商 5，余数 0）。

1. 公式

   $$104 \div 84 = 1 \text{ R } 20$$
   解释

   用初始较大的数除以较小的数。

   步骤依据

   欧几里得算法的第一步。

   视频直接表达
2. 公式

   $$84 \div 20 = 4 \text{ R } 4$$
   解释

   用上一步的除数（84）除以上一步的余数（20）。

   步骤依据

   欧几里得算法的第二步。

   视频直接表达
3. 公式

   $$20 \div 4 = 5 \text{ R } 0$$
   解释

   用上一步的除数（20）除以上一步的余数（4）。余数为零，因此过程停止。

   步骤依据

   欧几里得算法的第三步。

   视频直接表达

最后一个非零余数是 4，即 104 和 84 的最大公约数。

1. 图示
   观察依据

   屏幕依次显示长除法步骤：1785 除以 546，546 除以 147，147 除以 105，105 除以 42，以及 42 除以 21。

2. 声音
   观察依据

   旁白口头引导每一个除法步骤，陈述商和余数。

1. 公式

   $$1785 = 546 \times 3 + 147$$
   解释

   用 1785 除以 546，得到商 3 和余数 147。

   步骤依据

   欧几里得算法的第一步。

   视频直接表达
2. 公式

   $$546 = 147 \times 3 + 105$$
   解释

   用上一步的除数（546）除以上一步的余数（147），得到商 3 和余数 105。

   步骤依据

   欧几里得算法的第二步。

   视频直接表达
3. 公式

   $$147 = 105 \times 1 + 42$$
   解释

   用上一步的除数（147）除以上一步的余数（105），得到商 1 和余数 42。

   步骤依据

   欧几里得算法的第三步。

   视频直接表达
4. 公式

   $$105 = 42 \times 2 + 21$$
   解释

   用上一步的除数（105）除以上一步的余数（42），得到商 2 和余数 21。

   步骤依据

   欧几里得算法的第四步。

   视频直接表达
5. 公式

   $$42 = 21 \times 2 + 0$$
   解释

   用上一步的除数（42）除以上一步的余数（21），得到商 2 和余数 0。

   步骤依据

   欧几里得算法的第五步；因为余数为零，过程停止。

   视频直接表达

最后一个非零余数是 21，因此 $\gcd(1785, 546) = 21$。

1. 公式
   观察依据

   问题“Find gcd(1785, 546)”在 00:29 显示，最终答案“$\therefore$ gcd(1785, 546) = 21”在 01:54 显示。

2. 声音
   观察依据

   旁白明确陈述了问题和最终解决方案。

使用欧几里得算法求 1785 和 546 的最大公约数。

1. $a = 1785$

2. $b = 546$

确定 $\gcd(1785, 546)$。

1. 公式

   $$1785 \div 546 = 3 \text{ R } 147$$
   解释

   执行第一次长除法。

   步骤依据

   欧几里得算法步骤 1。

   视频直接表达
2. 公式

   $$546 \div 147 = 3 \text{ R } 105$$
   解释

   用上一步的除数除以上一步的余数。

   步骤依据

   欧几里得算法步骤 2。

   视频直接表达
3. 公式

   $$147 \div 105 = 1 \text{ R } 42$$
   解释

   重复该过程。

   步骤依据

   欧几里得算法步骤 3。

   视频直接表达
4. 公式

   $$105 \div 42 = 2 \text{ R } 21$$
   解释

   重复该过程。

   步骤依据

   欧几里得算法步骤 4。

   视频直接表达
5. 公式

   $$42 \div 21 = 2 \text{ R } 0$$
   解释

   重复该过程直到余数为零。

   步骤依据

   欧几里得算法步骤 5。

   视频直接表达

21

除法序列中的最后一个非零余数是 21。

1. 图示
   观察依据

   标题卡片“Example Euclidean Algorithm”显示，带有古典希腊边框设计。

1. 文本“Example Euclidean Algorithm”

2. 希腊钥匙边框

1. 无

1. 静态图像

介绍视频的主题。

1. 图示
   观察依据

   出现欧几里得的插图，随后是关于数字 104 和 84 的算法的快速视觉演示。

1. 欧几里得的插图

2. 104 和 84 的长除法步骤

1. 长除法步骤从左到右依次出现。

1. 欧几里得的插图保持静止。

在深入详细示例之前，提供历史背景并简要概述算法的操作方式。

1. 图示
   观察依据

   屏幕清空并呈现问题“Find gcd(1785, 546)”。长除法步骤在屏幕上依次动画显示。

1. 问题陈述

2. 连续的长除法计算

3. 指示数字流动的箭头

4. 最终结论文本

1. 每个除法步骤逐一出现。

2. 箭头将一步的除数和余数连接起来，成为下一步的被除数和除数。

3. 最终答案写在底部。

1. 问题陈述保持在顶部。

直观地演示欧几里得算法的分步执行，突出使用前一步的除数和余数进行下一次计算的递归性质。

1. 声音
   观察依据

   旁白说道：“What makes this method so powerful is you don't have to factor the numbers to find the greatest common divisor.”（这种方法如此强大的原因在于，你不必对数字进行因式分解就能找到最大公约数。）

为了找到两个数的最大公约数，你必须首先找到它们的质因数分解。

欧几里得算法允许你通过反复长除法高效地找到 GCD，完全绕过了对数字进行因式分解的需要。

1. 声音
   观察依据

   旁白专门将欧几里得算法介绍为一种求最大公约数的方法。

欧几里得算法是一种用于求两个整数最大公约数的特定计算方法。

1. 图示
   观察依据

   推导的最后一步显示余数为 0，并且箭头指向前一个余数（21）作为答案，直接说明了这一主张。

该示例的分步推导作为一般规则的实际演示和验证，即最后一个非零余数是 GCD。

1. 声音
   观察依据

   整个介绍部分解释了算法的目的和基本机制。

1. 欧几里得算法方法
2. 最大公约数 (GCD)

1. 声音
   观察依据

   旁白明确陈述了停止条件及其原因。

1. GCD 是最后一个非零余数