數學永恆定理/貝祖等式

貝祖等式是數論和代數中的一個定理，以法國數學家埃蒂安·貝祖 (1730 年 3 月 31 日 - 1783 年 9 月 27 日) 命名。該定理指出，整數 $a$ 和 $b$ 的最大公約數，可以寫成 $ax+by=d,$ 的形式，其中 $x$ 和 $y$ 是整數。這裡， $x$ 和 $y$ 被稱為 $(a,b)$ 的貝祖係數。

計算對， $(x,y)$

有無限多對 $(x,y)$ 滿足方程 $ax+by=d,$ 。可以開發一個通用公式來計算儘可能多的對。為此，首先需要計算一對 $(x,y)$ 。一種簡單的方法是使用擴充套件歐幾里得演算法來計算一對。

計算的一般公式

一旦你得到了一對 $(x_{0},y_{0}),$ 你就可以應用以下公式： $(x_{k},y_{k})=(x_{0}-k{\frac {b}{d}},y_{0}+k{\frac {a}{d}})$ 其中 $k\in \mathbb {Z}$ ，這意味著 $k$ 是一個整數。

證明：因為 $(x,y)=(x_{0},y_{0})$ 滿足方程式 $ax+by=d,$ 那麼，

$ax_{0}+by_{0}=d$

或者， ${\frac {d(ax_{0}+by_{0})}{d}}=d$

或者， ${\frac {dax_{0}+dby_{0}}{d}}=d$

或者， ${\frac {dax_{0}-kba+kba+dby_{0}}{d}}=d$

或者， $ax_{0}-ak{\frac {b}{d}}+by_{0}+bk{\frac {a}{d}}=d$

或者， $a(x_{0}-k{\frac {b}{d}})+b(y_{0}+k{\frac {a}{d}})=d$

或者， $a(x_{0}-k{\frac {b}{d}})+b(y_{0}+k{\frac {a}{d}})=ax_{k}+by_{k}$

因此， $a$ 的係數相等， $b$ 的係數也相等， $(x_{k},y_{k})=(x_{0}-k{\frac {b}{d}},y_{0}+k{\frac {a}{d}})$

[注意：該公式僅在 $d\neq 0$ 時有效。此外，由於 $x\in \mathbb {Z}$ ，則 $k\in \mathbb {Z}$ 。]

示例： $a=8$ 和 $b=12$ 的最大公約數是 $\gcd(8,12)=4.$ 根據恆等式，存在整數 $x$ 和 $y$ ，使得 $8x+12y=4$ $\Rightarrow 2x+3y=1$ 。如果您嘗試求解該方程，您很快就會找到一對解，例如 $(x_{0},y_{0})=(-1,1)$ 。因此， $(x_{k},y_{k})=(-(1+k{\frac {b}{d}}),1+k{\frac {a}{d}})$ 。使用此公式，您可以找到任意多對解。

證明

假設 $S=\{ax+by:x,y\in \mathbb {Z} {\text{ and }}ax+by>0\}$ 其中 $a$ 和 $b$ 是非零整數。該集合不是空集，因為它包含 $a$ 或 $-a$ 當 $x=\pm 1$ 且 $y=0$ 。由於 $S$ 不是空集，根據良序原理，該集合有一個最小元素 $d=as+bt$ 。

對 ${\frac {a}{d}}$ 的歐幾里得除法可以寫成 $a=dq+r$ ，其中 $q=\left\lfloor {\frac {a}{d}}\right\rfloor$ ， $r=a-d\left\lfloor {\frac {a}{d}}\right\rfloor$ 且 $0\leq r<d$ 。

這裡， $r=a-dq$ $=a-q(as+bt)$ $=a-qas+qbt$ $=a(1-qs)+b(qt)$

因此， $r$ 的形式為 $ax+by$ ，因此 $r\in S\cup \{0\}$ 。但是， $0\leq r<d$ 且 $d$ 是 $S$ 中最小的正整數。所以， $r$ 必須是 $0$ 。因此， $d$ 是 $a$ 的約數。 $q={\frac {a}{d}}>0$ ，因為餘數為零，而 a 是非零整數。類似地， $d$ 也是 $b$ 的約數。因此， $d$ 是 $a$ 和 $b$ 的公約數。