裴蜀等式——凑邮资问题

从一道“数学归纳法”例题说起

题目：当n≥17时，用面值4元和面值7元的邮票可支付任何n元邮资。即对于任意正整数n≥17，存在非负整数a,b，使得4a+7b=n

证明：（归纳法）

设P(n)表示“可以用面值4元和7元的邮票支付n元邮资”，令Q(n)=P(n)^P(n+1)^P(n+2)^P(n+3)，则

P(18)=2*7+4，P(19)=3*4+7，P(20)=5*4，P(21)=3*7，于是Q(18)为真。

假设对于k≥18，有Q(k)=P(k)^P(k+1)^P(k+2)^P(k+3)为真

则Q(k)=P(k+1)^P(k+2)^P(k+3)^P(k+4)也为真，因为P(k)成立，选用面值为4的邮票，P(k+4)也成立。

更一般的情况

令a和b是正整数，不失一般性地假设 gcd(a,b)=1 。则存在 n ，使得对所有的正整数 k≥n， k元的邮资都可以用 a 元的邮票和 b 元的邮票凑齐。

也即可以找到非负整数 s 和 t 使得 sa+rt=k ——这就是裴蜀等式。

定理1 对于不全为0的整数 $x, y$ 和 $d$ ，方程 $sx+ty=d$ 存在整数解 $s$ 和 $t$ 当且仅当 $GCD(x, y)|d$ 。方程 $sx+ty=d$ 称作裴蜀（Bezout）等式或贝祖等式。

对于裴蜀等式的解，有如下一般性结果：

定理2 假设 $x, y$ 和 $d$ 是不全为0的整数， $s_0$ 和 $t_0$ 是方程 $sx+ty=d$ 的一组整数解，则方程 $sx+ty=d$ 的所有解为： $left{ egin{matrix} s={{s}_{0}}+frac{y}{ ext{GCD}left( x,y ight)} imes k \ t={{t}_{0}}-frac{x}{ ext{GCD}left( x,y ight)} imes k \ end{matrix} ight.$ ，其中 $k$ 是整数。

证明：

“构成解”很容易验证。反过来，假设 $s_1$ 和 $t_1$ 是方程 $sx+ty=d$ 的一组整数解，则有 $(s_1-s_0)x=-(t_1-t_0)y$ 。

于是 $[left( {{s}_{0}}-{{s}_{1}} ight)frac{x}{ ext{GCD}left( x,y ight)}=-left( {{t}_{0}}-{{t}_{1}} ight)frac{y}{ ext{GCD}left( x,y ight)}]$ ，由于 $frac{x}{ ext{GCD}left( x,y ight)}$ 和 $frac{y}{ ext{GCD}left( x,y ight)}$ 互素，有 $[k={left( {{t}_{0}}-{{t}_{1}} ight)}/{frac{x}{ ext{GCD}left( x,y ight)}};]$ ，即得

推论：假设整数 $x$ 与 $y$ 互素，则存在整数 $s_0>0$ ， $t_0<0$ ， $s_1<0$ ， $t_1>0$ 使得 $s_0x+t_0y=1$ 及 $s_1x+t_1y=1$ 。

我们反过来思考，假设a,b已知，且存在N，使得任意的n>N都能由a,b线性表示，求N的最小值。

面值的下界

定理： $a$ 和 $b$ 是互素的正整数，则当 $n>ab-a-b$ 时，方程 $ax+by=n$ 均有非负整数解，而 $ax+by=ab-a-b$ 没有非负整数解。

证明：

假设 $n>ab-a-b$ ，方程 $ax+by=n$ 的所有整数解为 $x=x_0+bt$ ， $y=y_0-at$ ，其中 $tinmathbb{Z}$ 。取 $t=t_0$ ，使得 $0leq x_0+bt_0leq b-1$ ，则由 $a(x_0+bt_0)+b(y_0-at_0)=n>ab-a-b$ ，有 $b(y_0-at_0)>ab-a-b-a(b-1)= -b$ ，从而 $y_0-at_0>-1$ ，即 $y_0-at_0geq0$ 。于是 $(x_0+bt_0, y_0-at_0)$ 就是 $ax+by=n$ 的一个非负整数解。

另一方面，若非负整数 $x$ 和 $y$ 使得 $ax+by=ab-a-b$ ，则 $a(x+1)+b(y+1)=ab$ 。于是 $b|a(x+1)$ ，由 $GCD(a, b)=1$ 有 $b|x+1$ ，从而 $x+1geq b$ ；同样可知 $y+1geq a$ 。因此 $ab=a(x+1)+b(y+1)geq ab+ab=2ab$ ，导致矛盾，所以 $ax+by=ab-a-b$ 不存在非负整数解。

该定理表明，如果 $a$ 和 $b$ 是互素的正整数，则 $N=ab-a-b$ 具有这样的性质： $N$ 元邮资无法用 $a$ 元的邮票和 $b$ 元的邮票凑齐；而对于每个大于 $N$ 的正整数 $k$ ， $k$ 元的邮资都可以用 $a$ 元的邮票和 $b$ 元的邮票凑齐。

例如：

$a=7, b=4$ 时， $N=7 imes4-7-4=17$ 。这也对应了最初的“数学归纳法例题”。

参考链接：

1、中国大学mooc 刘铎离散数学

2、https://zhuanlan.zhihu.com/p/32504576