利用同余分析证明$(ab - a - b)$不能表示为$(xa + yb)$

1. 先看等式变形：$(x + 1)a + (y + 1)b = ab$

等式变形

我们从假设 “存在非负整数 $x,y$ 使得 $xa + yb = ab - a - b$” 出发，为了方便分析，两边同时加 $a + b$，得到：

$(x + 1)a + (y + 1)b = ab$

可以简单理解为：把左边的 “$-a - b$” 通过 “加 $a + b$” 消掉，让等式更对称，方便后续分析。

2. 重点理解 “两边除以 $b$ 并取模 $b$”

取模

这一步是同余分析的核心，目的是通过 “模 $b$”（即除以 $b$ 看余数），缩小 $x$ 的取值范围。

先解释 “模 $b$” 的含义

“模 $b$” 就是看一个数除以 $b$ 的余数。比如：

• $10 \div 3$ 商 3 余 1，就说 $10 \equiv 1 \pmod{3}$（读作 “10 模 3 余 1”）；

• $7 \div 5$ 商 1 余 2，就说 $7 \equiv 2 \pmod{5}$。

再看 “两边除以 $b$ 并取模 $b$” 的操作

对等式 $(x + 1)a + (y + 1)b = ab$，我们想研究它除以 $b$ 的余数，所以：

• 左边：$(x + 1)a + (y + 1)b$ 除以 $b$ 的余数，等于 $(x + 1)a$ 除以 $b$ 的余数（因为 $(y + 1)b$ 是 $b$ 的倍数，除以 $b$ 余 0）。

• 右边：$ab$ 除以 $b$ 的余数是 0（因为 $ab = a \times b$，显然是 $b$ 的倍数）。

所以，左边除以 $b$ 的余数（即 $(x + 1)a \mod b$）必须等于右边除以 $b$ 的余数（即 $0$）。用同余符号表示就是：

$$(x + 1)a \equiv 0 \pmod{b}$$

3. 结合 “$a$ 和 $b$ 互质” 推导 $x + 1$ 的性质

结合互质推导

因为 $a$ 和 $b$ 互质（最大公约数是 1，比如 $a=3, b=5$），所以 $a$ 除以 $b$ 的余数不是 0，且 $a$ 和 $b$“没有公共因子”。

• 这时候有个重要结论：如果 $a \times k$ 是 $b$ 的倍数，且 $a$ 和 $b$ 互质，那么 $k$ 本身是 $b$ 的倍数。

• 翻译成人话：因为 $a$ 和 $b$ 互质，想让 $a \times k$ 是 $b$ 的倍数，只能让 $k$ 本身是 $b$ 的倍数。

回到我们的式子 $ (x + 1)a \equiv 0 \pmod{b} $，因为 $a$ 和 $b$ 互质，所以必须满足：

$$x + 1 \equiv 0 \pmod{b}$$

• 也就是说，$x + 1$ 是 $b$ 的倍数，即存在正整数 $m$（因为 $x$ 是非负整数，所以 $x + 1 \geq 1$），使得：

$$x + 1 = m \times b$$

• 因此， $x = m \times b - 1$

举个例子理解（用 $a=3, b=5$ 验证）

举例说明

假设 $a=3$，$b=5$（互质），我们想证明 $3 \times 5 - 3 - 5 = 7$ 不能表示为 $3x + 5y$。

按照上面的步骤：

1. 假设 $3x + 5y = 7$，两边加 $3 + 5 = 8$，得到 $(x + 1) \times 3 + (y + 1) \times 5 = 15$。

2. 两边除以 $5$ 并取模 $5$：左边 $(x + 1) \times 3$ 除以 $5$ 的余数，必须等于右边 $15$ 除以 $5$ 的余数（即 0）。所以 $(x + 1) \times 3 \equiv 0 \pmod{5}$。

3. 因为 $3$ 和 $5$ 互质，所以 $x + 1$ 必须是 $5$ 的倍数，即 $x + 1 = 5m$，$x = 5m - 1$。

• 若 $m=1$，则 $x=4$，代入 $(x + 1) \times 3 + (y + 1) \times 5 = 15$，得 $5 \times 3 + (y + 1) \times 5 = 15$，即 $(y + 1) \times 5 = 0$，$y = -1$（不是非负整数，矛盾）。

• 若 $m \geq 2$，$x$ 会更大，$y$ 会是负数，更不满足条件。

总结

总结

1. 通过等式变形，把原问题转化为更对称的形式；

2. 利用同余分析（除以 $b$ 看余数），结合 $a$ 和 $b$ 互质的条件，推导出 $x + 1$ 必须是 $b$ 的倍数；

3. 最终发现 $x$ 或 $y$ 会出现负数，与 “非负整数” 矛盾，从而证明 $ab - a - b$ 不能表示为 $xa + yb$。

如果还没完全理解，可以再找一组互质数（比如 $a=2, b=3$），按照步骤自己推导一遍，会更清晰！

《基于非负整数的 Frobenius 数公式推导与验证》

基于非负整数 $x$ 和 $y$ 的 Frobenius 数公式推导与验证（二元情形）

二元验证

对于两个互质正整数 $a$ 和 $b$（$\gcd(a,b)=1$），其 Frobenius 数公式为 $g(a,b) = ab - a - b$。以下用非负整数 $x$ 和 $y$ 重新表述推导过程，明确 “非负整数组合” 的核心约束：

一、证明 $ab - a - b$ 不能表示为 $xa + yb$（$x,y$ 为非负整数）

证明

假设存在非负整数 $x$ 和 $y$，使得：

$$xa + yb = ab - a - b$$

步骤 1：等式变形与同余分析

两边同时加 $a + b$，整理得：

$$(x + 1)a + (y + 1)b = ab$$

• 两边除以 $b$ 并取模 $b$：$(x + 1)a \equiv 0 \pmod{b}$。 因

  因 $a$ 与 $b$ 互质（$\gcd(a,b)=1$），根据数论性质，$a$ 对模 $b$ 可逆，故 $x + 1 \equiv 0 \pmod{b}$。即存在正整数 $m \geq 1$（因 $x$ 非负，$x + 1 \geq 1$），使得 $x + 1 = mb$，因此 $x = mb - 1$。

• 同理，两边除以 $a$ 并取模 $a$：$(y + 1)b \equiv 0 \pmod{a}$。 因

  因 $a$ 与 $b$ 互质，故 $y + 1 \equiv 0 \pmod{a}$，即存在正整数 $n \geq 1$，使得 $y + 1 = na$，因此 $y = na - 1$。

步骤 2：导出矛盾

将 $x = mb - 1$ 和 $y = na - 1$ 代入变形后的等式 $(x + 1)a + (y + 1)b = ab$，得：

$$(mb) \cdot a + (na) \cdot b = ab$$

化简为：

$$mab + nab = ab \implies m + n = 1$$

但 $m \geq 1$ 且 $n \geq 1$（因 $x,y$ 为非负整数，$mb - 1 \geq 0 \implies m \geq 1$，同理 $n \geq 1$），故 $m + n \geq 2$，与 $m + n = 1$ 矛盾。因此，$ab - a - b$ 无法表示为 $xa + yb$（$x,y$ 为非负整数）。

二、证明所有大于 $ab - a - b$ 的数均可表示为 $xa + yb$（$x,y$ 为非负整数）

证明

任取正整数 $N > ab - a - b$，需证明存在非负整数 $x,y$ 使得 $N = xa + yb$。

• 步骤 1：利用互质性构造$y$的取值

因 $a$ 与 $b$ 互质，根据数论中的 “完全剩余系” 性质：对于模 $a$，$b, 2b, \dots, (a-1)b$ 的余数恰好覆盖 $1, 2, \dots, a-1$（即任意余数 $r \in \{0,1,\dots,a-1\}$ 都能通过某个 $yb \mod a$ 实现）。

设 $N \mod a = r$（$0 \leq r < a$），则存在非负整数 $y_0$（$0 \leq y_0 < a$）使得：

$$y_0b \equiv r \pmod{a}$$

即 $y_0b = ka + r$（$k$ 为非负整数）。

• 步骤 2：证明$x$为非负整数

由 $N \mod a = r$，可设 $N = ta + r$（$t$ 为整数）。将 $r = y_0b - ka$ 代入得：

$$N = ta + y_0b - ka = (t - k)a + y_0b$$

令 $x = t - k$，则 $N = xa + y_0b$。只需证明 $x \geq 0$：

• 由 $N > ab - a - b$，得 $ta + r > ab - a - b$。

• 因 $r < a$，故 $ta + (a - 1) \geq ta + r > ab - a - b$，整理得 $t > b - 1 - \frac{b + 1}{a}$。

• 由于 $t$ 为整数且 $a \geq 1$，可得 $t \geq b - 1$。

又因 $y_0 < a$，则 $y_0b < ab$，结合 $N = xa + y_0b$ 得 $x = \frac{N - y_0b}{a} > \frac{(ab - a - b) - ab}{a} = -1 - \frac{b}{a}$。因 $x$ 为整数，故 $x \geq 0$。

重要

综上，$ab - a - b$ 是最大的不可表示数，且所有大于它的数均可表示为两个互质数的非负整数组合，公式得证。