裴蜀等式

假設你有兩個量杯，一個容量為 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 能取到該最大公因數的任意倍數 — 而非任意整數。