数学永恒定理/贝祖等式

贝祖等式是数论和代数中的一个定理，以法国数学家埃蒂安·贝祖 (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$ 的公约数。