数学永恒定理/贝祖等式

埃蒂安·贝祖 (1730 年 3 月 31 日 - 1783 年 9 月 27 日)

贝祖等式是数论和代数中的一个定理，以法国数学家埃蒂安·贝祖 (1730 年 3 月 31 日 - 1783 年 9 月 27 日) 命名。该定理指出，整数 $a$ 和 $b$ 的最大公约数，${\displaystyle }$ 可以写成 $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$ 的公约数。

假设 $c$ 为 $a$ 和 $b$ 的任何公约数；$a=cu$，$b=cv$。同样，$d=as+bt$ $=cus+cvt$ $=c(us+vt)$

因此，$c$ 是 d 的约数。由于 $d>0$ $\implies c\leq d$。因此，$a$ 和 $b$ 的任何公约数都小于或等于 $d$。

$\therefore d$ 等于 $gcd(a,b)$，并且 $d$ 可以表示为 $ax+by=d$。 [已证明]