The Greatest Common Divisor

最大公约数（the Greatest Common Divisir, GCD） 是指可以整除几个数字的最大的数。

推论

推论一：GCD(A, B) = GCD(A, A - B)，假设 A > B

1. 证明 C 可以被 GCD(A, B) 整除

   • 令 A - B = C
   • 可以找到整数 X，使得 X * GCD(A, B) = A
   • 可以找到整数 Y，使得 Y * GCD(A, B) = B
   • X * GCD(A, B) - Y * GCD(A, B) = C => (X - Y) * GCD(A, B) = C，所以 C 可以被 GCD(A, B) 整除

2. 证明 A 可以被 GCD(B, C) 整除

   • B + C = A
   • 可以找到整数 M，使得 M * GCD(B, C) = B
   • 可以找到整数 N，使得 N * GCD(B, C) = C
   • M * GCD(B, C) + N * GCD(B, C) = A => (M + N) * GCD(B, C) = A，所以 A 可以被 GCD(B, C) 整除

3. 证明 GCD(A, B) = GCD(A, A - B)

   • B 可以被 GCD(B, C) 整除
   • A 可以被 GCD(B, C) 整除
   • 因此 GCD(B, C) 也是 A 和 B 的公约数，且 GCD(B, C) <= GCD(A, B)（因为 GCD(A, B) 是 A 和 B 的最大公约数）

   同理

   • B 可以被 GCD(A, B) 整除
   • C 可以被 GCD(A, B) 整除
   • 因此 GCD(A, B) 也是 B 和 C 的公约数，且 GCD(A, B) <= GCD(B, C)（因为 GCD(B, C) 是 B 和 C 的最大公约数）

   因此，GCD(A, B) = GCD(B, C)，也就是 GCD(A, B) = GCD(A, A - B)。

推论二：GCD(A, B) = GCD(B, R)，假设 A > B 且 A = B * Q + R

由推论一 GCD(A, B) = GCD(A - B, B)，可以推出：

GCD(A, B) = GCD(A - B, B) = GCD(A - 2B, B) = GCD(A - Q * B, B)

而 A = B * Q + R 因此 A - Q * B = R，所以 GCD(A, B) = GCD(B, R)