二元一次丢番图方程的有趣性质

1. 命题：对于任意 \(a, b \in \mathbb{N^+}\) 且 \((a, b) = 1\)，最大不能被表示为 \(ax +by\) \((x, y > 0)\) 的整数是 \(ab- a - b\)。

   证明：先证明 \(ab - a - b\) 不可被表示为 \(ax + by\) 的形式。使用反证法，假设

   \[ax +by = ab - a - b, \]

   移项得：

   \[a(x+1) +b(y +1) = ab, \]

   两边对 \(b\) 取模得：

   \[a(x+1) \equiv 0 \pmod{b}. \]

   由于 \((a, b) = 1\) 所以 \(b \mid x + 1\) ，则 \(x\geq b - 1\)。同理有 \(y \geq a - 1\)。因此，

   \[ax +by \geq a(b-1)+b(a-1)=2ab-a-b>ab-a-b. \]

   这与假设矛盾，故 \(ab-a-b\) 不可被表示。

   再证明任意 \(ax +by > ab-a-b\) 都可被表示。

   设 \(ax + by = n > ab-a-b\)。由于 \((a, b) = 1\)，\(x = \{ar|0\leq r <b\}\) 构成了模 \(b\) 的完全剩余系，因此存在 \(0<r^*<b\) 使得

   \[n\equiv ar^* \pmod{b} \Rightarrow n - ar^* = bt. \]

   如果 \(t\geq 0\) 则$(x, y) = (r^*, t) $ 已经构成原方程的一组解。

   如果 \(t < 0\)，则

   \[n = bt +ar^* \leq a(b-1) -b = ab-a-b. \]

   这与 \(n > ab -a -b\) 矛盾，因此任意 \(n > ab - a - b\) 都可被表示为 \(ax+by\) 的形式。

   拓展：该问题也被称为 Frobenius Coin Problem 是一个经典组合/数论问题，拓展为多个数则为无固定数学公式的 NP-Hard 问题，可用动态规划（背包问题）/生成函数解决。\(c_1, c_2, \cdots, c_n\) 的线性组合（且系数均为非负整数）所可表示的整数与生成函数

   \[F(x) = \prod_{i=1}^{n}\frac{1}{1-x^{c_i}} \]

   所联系。根据泰勒展开，当 \(0<x <1\) 时

   \[\frac{1}{1-x^{c_i}}=1+x^{c_i}+x^{2c_i}+x^{3c_i}+\cdots, \]

   若选取 \(x^{kc_i}\) 则表示 \(c_i\) 最终贡献了 \(k\) 次，于是 \(x^n\) 前的系数表示 \(n\) 可以被用 \(c_1, c_2, \cdots, c_n\) 表示的总方法数。

2. 命题：证明恰有 \((ab-a-b+1)/2\) 个非负整数在区间 \([0, ab-a-b]\) 中可以被表示为 \(ax+by\) \((x, y \in N)\) 的形式。

   证明：令 \(ax+by=n \in [0, ab-a-b]\)，则当 \(x \in [0, b-1]\) 时，存在唯一的一组 \((x_0, y_0)\) 表示 \(n\) 且 \(y_0\) 为 所有 \(x \geq 0\) 的 \((x, y)\) 中最大的 \(y\)。 那么 \(n\) 是可被表示的当且仅当 \(y_0 \geq 0\)。设 \(N = ab - a - b\)，则

   \[N-n = ab-a-b-ax_0-by_0 = a(b-1-x_0)+b(-1-y_0), \]

   于是令 \(x_0'=b-1-x_0\), \(y_0'=-1-y_0\) 那么 \(N-k = ax_0'+by_0'\)。

   由 \(0\leq x_0 \leq b-1\) 知 \(0 \leq x_0' \leq b-1\)。

   若 \(y_0 \geq 0\)，则 \(y_0' \leq -1\)，此时 \(n\) 为可被表示数，\(N-k\) 为不可被表示数。

   若 \(y_0 \leq -1\)，则 \(y_0' \geq 0\)，此时 \(n\) 为不可表示数，\(N-k\) 为可被表示数。

   故每一对 \((n, N-n)\) 中恰有一个数为可被表示数，而 \([0, ab-a-b]\) 中共有 \(ab-a-b+1\) 个数，故共有 \((ab-a-b+1) / 2\) 个可被表示数。