最大公约数（GCD）和最小公倍数（LCM）是数论中的基本概念，用于简化分数和解决问题。

定义

GCD（最大公约数） — 能整除两个数的最大正整数。

LCM（最小公倍数） — 能被两个数整除的最小正整数。

GCD(a, b) × LCM(a, b) = a × b
LCM(a, b) = (a × b) ÷ GCD(a, b)

方法1：质因数分解

示例： 36和48的GCD和LCM

  • 36 = 2² × 3²
  • 48 = 2⁴ × 3

GCD = 2² × 3¹ = 12 LCM = 2⁴ × 3² = 144

验证：36 × 48 = 1,728 = 12 × 144 ✓

方法2：欧几里得算法

对于GCD(a, b)：用a除以b，将a替换为b，b替换为余数。重复直到余数为0。

示例： GCD(48, 18)

  • 48 = 2 × 18 + 12
  • 18 = 1 × 12 + 6
  • 12 = 2 × 6 + 0

GCD = 6

实际应用

  • 化简分数：36/48 = 3/4（除以GCD 12）
  • 用LCM求通分母
  • 安排不同间隔发生的事件