【原】更相减损术和辗转相除法的介绍

今天咱来聊聊一个超有意思的数学方法 ——辗转相除法，它也叫 “欧几里得算法”，说白了就是用来找两个数的最大公约数（能同时整除这俩数的最大整数）的妙招，操作起来跟玩积木叠叠乐似的，特别好理解！

🌰 先看个例子：找 12 和 8 的最大公约数

1. 第一步：大数除以小数，算余数
   12 比 8 大，用 12 除以 8，商是 1，余数是 4（因为 12=8×1+4）。
   这时候，余数 4 比除数 8 小，就接着往下走～

2. 第二步：把除数当新的被除数，余数当新的除数，继续算余数
   现在，原来的除数 8 变成新的被除数，余数 4 变成新的除数，算 8÷4。
   商是 2，余数 0（8=4×2+0）。

3. 第三步：当余数为 0 时，最后一次的除数就是最大公约数
   余数为 0 的时候，当前的除数 4 就是 12 和 8 的最大公约数！

🧩 原理拆解：为什么这么算能找到最大公约数？

其实它的核心逻辑就一句话：两个数的最大公约数，等于其中较小的数和两数余数的最大公约数。
比如上面的例子：

• 12 和 8 的最大公约数，等于 8 和 4 的最大公约数；
• 8 和 4 的最大公约数，等于 4 和 0 的最大公约数（而任何数和 0 的最大公约数都是它本身）。
  就像剥洋葱一样，每次把问题缩小，直到剩下最简单的情况～

📝 再试一个复杂点的例子：找 252 和 105 的最大公约数

1. 252÷105=2……42（余数 42）
2. 105÷42=2……21（余数 21）
3. 42÷21=2……0（余数 0）
   所以最大公约数是 21！

💡 生活中的类比：分蛋糕切方块

假设你有一块长 252 厘米、宽 105 厘米的大蛋糕，想切成边长最大的正方形小块，且不浪费蛋糕。
这时候，正方形的边长就应该是 252 和 105 的最大公约数 21 厘米～
辗转相除法就像在说：“先试试用小长度切，看剩下多少，再用剩下的长度接着切，直到刚好切完！”

📌 总结步骤（傻瓜式操作指南）：

1. 拿大的数除以小的数，算余数；
2. 把 “小的数” 当成新的被除数，“余数” 当成新的除数，再算余数；
3. 重复步骤 2，直到余数为 0，此时的除数就是最大公约数！
   
   

是不是超简单？下次遇到找最大公约数的问题，试试用这个方法玩一玩呀！

接下来我们再看看更相减损术：

更相减损术是老祖宗发明的 “求最大公约数神器”，不用除法，靠一顿猛减就能算出结果，操作特别接地气，咱举个例子秒懂 ——

🌰 比如求 24 和 18 的最大公约数：

1. 先看谁大，24 比 18 大，那就用 24 减 18，得 6；
2. 现在不算 24 和 18 了，改算 18 和 6；
3. 18 比 6 大，18 减 6 得 12，接着算 12 和 6；
4. 12 减 6 得 6，这时候俩数都是 6，相等了！
   所以 24 和 18 的最大公约数就是 6。
5. 
   

📝 核心逻辑：揪着 “大减小” 不放

不管俩数多大，只要不相等，就用大的减小的，减出来的差和小数组成新的一对数，继续重复这个操作，直到俩数一模一样，这个数就是最大公约数。
就像用 “减法尺子” 量东西：比如量 15 和 9，先减去一个 9，剩 6；再从 9 里减 6，剩 3；从 6 里减 3，剩 3，这时候 3 就是能同时量完 15 和 9 的 “最小尺子”。

✨ 古人的小聪明：遇偶数先砍半

《九章算术》里还说了个窍门：要是俩数都是偶数，先一起除以 2，最后再把公约数乘回去。比如求 36 和 24：

1. 都是偶数，先除以 2 得 18 和 12；
2. 还是偶数，再除以 2 得 9 和 6；
3. 9 减 6 得 3，6 减 3 得 3，相等了，公约数是 3；
4. 之前除以两次 2，所以最终结果是 3×2×2=12。
   这招能减少减法次数，相当于给计算 “偷个懒”～
   
   

🧩 和除法比有啥不一样？

比如求 1001 和 13，辗转相除法用 1001÷13=77 余 0，直接出结果；但更相减损术得从 1001 里连减 77 次 13，显然慢很多。不过它的厉害之处在于：不用懂除法，只要会减法就能算，老祖宗的智慧是不是很接地气？

简单说，这方法就像俩人数数比大小，大的每次让着小的，一点点 “退” 到相同的数，这个数就是它们的 “最大公共小伙伴”～ 😊

辗转相除法和更相减损术都是求最大公约数的方法，但它们的「操作逻辑」和「适用场景」不太一样，就像用剪刀剪纸和用手撕纸的区别～ 让我用大白话给你拆解清楚！

🧮 核心区别对比表

维度	辗转相除法（欧几里得）	更相减损术（中国古法）
操作方式	除法 + 取余数 （大数 ÷ 小数，不断用余数迭代）	减法 （大数 - 小数，不断用差值迭代）
计算效率	大数时更快（余数缩小问题规模更显著）	小数时直观，但大数减法可能慢
适用场景	适合计算机算法（整除和取余运算高效）	适合心算或没有计算器的场景（只需要减法）
思想核心	用余数的公约数替代原数的公约数	用差值的公约数替代原数的公约数

🌰 举个例子：求 252 和 105 的最大公约数

辗转相除法（除法版）

1. 252 ÷ 105 = 2 余 42
    → 新问题：105 和 42
2. 105 ÷ 42 = 2 余 21
    → 新问题：42 和 21
3. 42 ÷ 21 = 2 余 0
    → 最大公约数 = 21

更相减损术（减法版）

1. 252 - 105 = 147
    → 新问题：147 和 105
2. 147 - 105 = 42
    → 新问题：105 和 42
3. 105 - 42 = 63
    → 新问题：63 和 42
4. 63 - 42 = 21
    → 新问题：42 和 21
5. 42 - 21 = 21
    → 新问题：21 和 21
6. 21 - 21 = 0
    → 最大公约数 = 21
   
   

🤔 本质理解：为什么都行得通？

• 辗转相除法
  ：利用「余数」是两数差值的叠加，快速逼近公约数。
  比如：252 和 105 的公约数，一定也是 105 和 42（252-105×2）的公约数。
• 更相减损术
  ：利用「差值」和原数共享公约数。
  比如：252 和 105 的公约数，一定也是 147（252-105）和 105 的公约数。
  
  

⚡ 效率对比：谁更快？

• 辗转相除法
  ：每次用余数缩小问题，大数场景下迭代次数少。
  比如求 10000 和 125 的 GCD，辗转相除法只需 3 步（10000→125→0）。
• 更相减损术
  ：每次只减 1 次，小数场景直观，但大数可能需要很多步。
  比如求 10000 和 125 的 GCD，需要减 79 次（10000→9875→…→125）。
  
  

🎯 实际应用建议

1. 计算机编程
   ：选辗转相除法，除法和取余运算在代码中效率极高。
2. 心算 / 口算
   ：选更相减损术，只需要减法，适合没有计算器的场景。
3. 分数约分
   ：两者都行，但辗转相除法更快。
   
   

🧠 总结记忆口诀

• 辗转相除法
  ：除到余 0 见分晓（用除法快速缩小问题）。
• 更相减损术
  ：减到两数一样高（用减法慢慢逼近答案）。
  
  

下次遇到求最大公约数的问题，根据场景选工具，就像选剪刀还是手撕纸一样自然～ 😊！

最后需要强调的是，对公约数的两个数，通常是要求这两个数都是正整数。