裴蜀等式

假设你有两个量杯，一个容量为 a 个单位，一个为 b 个单位，通过反复装满与倒回，你能量出某些分量。你所能量出的最小正分量，恰好是 a 与 b 的最大公约数 — 裴蜀等式正是对“为何如此”的精确陈述。

它说：对任意整数 a 与 b，存在整数 x 与 y，使得 a x + b y = gcd(a, b)。系数 x 与 y 称为裴蜀系数，可用扩展欧几里得算法，在把除法步骤逆推回去时追踪各组合而算出。它们不唯一 — 有许多组都成立 — 但它们所产生的值 gcd(a, b) 是唯一的。

这条等式是求解线性丢番图方程、以及在模运算中求逆元背后的理论钥匙。特别地，a x + b y 能等于 1，当且仅当 a 与 b 互素，这正是互素的数总有模逆元的原因。一个常见的失误：gcd(a, b) 是 a x + b y 的最小正值，但 a x + b y 能取到该最大公约数的任意倍数 — 而非任意整数。