最大公约数即为Greatest Common Divisor，常缩写为gcd。

更相减损术

描述

更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

定义

∀a,b∈N,a⩾b⇒gcd⁡(a,b)=gcd⁡(b,a−b)=gcd⁡(a,a−b)\forall a, b \in \mathbb{N}, a \geqslant b \Rightarrow \gcd(a, b) = \gcd(b, a - b) = \gcd(a, a - b)

∀a,b∈N⇒gcd(2a,2b)=2⋅gcd⁡(a,b)\forall a, b \in \mathbb{N} \Rightarrow gcd(2a, 2b) = 2 \cdot \gcd(a, b)

证明

a∣ba \mid b 表示 aa 能整除 bb（aa 为 bb 的约数）。

  • 显然，根据最大公约数的定义，后者是成立的，主要证明前者。
  • 对于 a,ba,b 的任意公约数 dd，因为 d∣a,d∣bd \mid a,d \mid b，所以 d∣(a−b)d \mid (a−b)。（不妨设 a=x⋅d,b=y⋅da=x \cdot d,b=y \cdot d，那么 a−b=x⋅d−y⋅d=(x−y)⋅da−b=x \cdot d−y \cdot d=(x−y) \cdot d，显然 (x−y)⋅d(x−y) \cdot d 是 dd 的倍数）
  • 因为 dd 是任意取的，所以可以取到整个 a,ba,b 的公约数集合。故 a,ba,b 的公约数集合与 b,a−bb,a−b 的公约数集合相同，于是他们的最大公约数自然也相等。对于 a,a−ba,a−b 同理。