如有谬误，欢迎联系 premierbob@qq.com，笔者感激不尽。

“小凯的疑惑”中的核心命题

∀n>ab−a−b,∃p,qs.t.n=pa+qb\forall n>ab-a-b,\exist p, q\;s.t.\;n=pa+qb ∀n>ab−a−b,∃p,qs.t.n=pa+qb

其中，a,ba, ba,b 为一对互质的整数，nnn 为整数，p,qp, qp,q 均为非负整数。后文中，不指明取值范围的符号均默认理解为整数（尽管如此，我会尽可能指明每个符号的取值范围）。

定义 111：标准逆元 ab−1a_b^{-1}ab−1​

若 aaa 为正整数， bbb 为大于 111 的正整数，且 gcd⁡(a,b)=1\gcd(a, b)=1gcd(a,b)=1。根据拓展欧几里得算法，我们能够找到一对整数 p,qp, qp,q 使得：
pa+qb=1pa+qb=1 pa+qb=1
我们记 ab−1=pmodba_b^{-1}=p\mod bab−1​=pmodb，读作 aaa 在模 bbb 意义下的标准逆元，换言之有 0≤ab−1

设 p1a+q1b=1p_1a+q_1b=1p1​a+q1​b=1 且 p2a+q2b=1p_2a+q_2b=1p2​a+q2​b=1，我们需要证明 p1≡p2modbp_1 \equiv p_2 \mod bp1​≡p2​modb。由于当 p1=p2p_1=p_2p1​=p2​ 时结论显然成立，不妨设 p1≠p2p_1\neq p_2p1​=p2​。两式联立，得到：

p1a+q1b=p2a+q2b=1∴(p1−p2)a=(q2−q1)b\begin{aligned} p_1a+q_1b&=p_2a+q_2b=1\\ \therefore (p_1-p_2)a&=(q_2-q_1)b \end{aligned} p1​a+q1​b∴(p1​−p2​)a​=p2​a+q2​b=1=(q2​−q1​)b​

在等式 (p1−p2)a=(q2−q1)b(p_1-p_2)a=(q_2-q_1)b(p1​−p2​)a=(q2​−q1​)b 中，我们看到 p1−p2≠0p_1-p_2\neq 0p1​−p2​=0，q1−q2≠0q_1-q_2\neq 0q1​−q2​=0，而且两侧都是 bbb 的整数倍。即 b∣(p1−p2)ab|(p_1-p_2)ab∣(p1​−p2​)a，而我们知道 gcd⁡(a,b)=1\gcd(a, b)=1gcd(a,b)=1，根据欧几里得引理可知：
b∣(p1−p2)b|(p_1-p_2) b∣(p1​−p2​)
而这等价于 p1≡p2modbp_1\equiv p_2\mod bp1​≡p2​modb。综上，ab−1a_b^{-1}ab−1​ 的唯一性得证。

标准逆元的性质： ab−1a≡1modba_b^{-1}a\equiv 1\mod bab−1​a≡1modb

根据我们的定义，存在 pa+qb=1pa+qb=1pa+qb=1 （即 pa≡1modbpa\equiv 1\mod bpa≡1modb） 使得 ab−1≡pmodba_b^{-1}\equiv p\mod bab−1​≡pmodb，由于同余关系是等价关系，因此可以将 ab−1a^{-1}_bab−1​ 替换同余式中的 ppp，得到 ab−1a≡1modba^{-1}_ba\equiv 1 \mod bab−1​a≡1modb。

另一方面，我们在计算标准逆元时，我们要求 bbb 必须为大于 111 的正整数。因此我们能够知道 ab−1≠0a^{-1}_{b}\neq 0ab−1​=0。反证法：假设 ab−1=0a_b^{-1}=0ab−1​=0，则有 ab−1a=0a_b^{-1}a=0ab−1​a=0，而 0≢1modb0\not \equiv 1\mod b0≡1modb，与标准逆元的性质矛盾。因此有 1≤ab−1

引理 111：ab+1=ab−1⋅a+ba−1⋅b(a>1,b>1,gcd⁡(a,b)=1)ab+1=a^{-1}_b\cdot a+b^{-1}_a\cdot b\;(a\gt1, b\gt 1,\gcd(a,b)=1)ab+1=ab−1​⋅a+ba−1​⋅b(a>1,b>1,gcd(a,b)=1)

注：这个引理是打酱油的，即使不使用这个引理，我们仍然可以证明定理 111 和定理 222。

首先证明右侧 ab−1⋅a+ba−1⋅b=1modaba^{-1}_b\cdot a+b^{-1}_a\cdot b=1\mod abab−1​⋅a+ba−1​⋅b=1modab，再证明 ab−1⋅a+ba−1⋅b>1a^{-1}_b\cdot a+b^{-1}_a\cdot b>1ab−1​⋅a+ba−1​⋅b>1，再证明 ab−1⋅a+ba−1⋅b<2aba^{-1}_b\cdot a+b^{-1}_a\cdot b<2abab−1​⋅a+ba−1​⋅b<2ab，最后夹得答案。

1. 使用类似中国剩余定理得证明方式进行证明 ab−1⋅a+ba−1⋅b=1modaba^{-1}_b\cdot a+b^{-1}_a\cdot b=1\mod abab−1​⋅a+ba−1​⋅b=1modab，设 x=ab−1⋅a+ba−1⋅bx=a^{-1}_b\cdot a+b^{-1}_a\cdot bx=ab−1​⋅a+ba−1​⋅b。

首先，证明 x≡1modax\equiv 1\mod ax≡1moda，再证明 x≡1modbx\equiv 1\mod bx≡1modb，最后合并得到 x≡1modabx\equiv 1\mod abx≡1modab。由于 ab−1⋅aa^{-1}_b\cdot aab−1​⋅a 是 aaa 的倍数，所以 x≡ba−1⋅b≡1modax\equiv b_a^{-1}\cdot b\equiv 1\mod ax≡ba−1​⋅b≡1moda。同理可得 x≡1modbx\equiv 1\mod bx≡1modb。

根据这两个同余式，我们得知，一定存在整数 k1,k2k_1, k_2k1​,k2​ 使得：

x=k1a+1x=k2b+1\begin{aligned} x&=k_1a+1\\ x&=k_2b+1 \end{aligned} xx​=k1​a+1=k2​b+1​

此时，我们得到 k1a=k2bk_1a=k_2bk1​a=k2​b。可以看到，这个等式两侧都是 bbb 的倍数，但 a,ba, ba,b 互质，那么，根据欧几里得引理可知，k1k_1k1​ 一定是 bbb 的倍数。因为 b>1(i.e.,b≠0)b>1\;(i.e.,\;b\ne 0)b>1(i.e.,b=0)，我们可以得知，k1b\frac{k_1}{b}bk1​​ 是整数。

因此，我们可以得到：

x=k1a+1=k1b⋅ab+1x=k_1a+1=\frac{k_1}{b}\cdot ab+1x=k1​a+1=bk1​​⋅ab+1

而这就意味着，x≡1modabx\equiv 1\mod abx≡1modab。

2. 再证明 ab−1⋅a+ba−1⋅b>1a^{-1}_b\cdot a+b^{-1}_a\cdot b>1ab−1​⋅a+ba−1​⋅b>1，这个证明是显然的。根据标准逆元的性质，ab−1,bb−1a^{-1}_b, b_{b}^{-1}ab−1​,bb−1​ 均大于等于 111，而 a,ba, ba,b 均大于 111，两个大于一的数之和仍然是大于一的。

ab−1⋅a+ba−1⋅b≥a+b>1a^{-1}_b\cdot a+b^{-1}_a\cdot b\geq a+b>1 ab−1​⋅a+ba−1​⋅b≥a+b>1

3. 证明 ab−1⋅a+ba−1⋅b<2aba^{-1}_b\cdot a+b^{-1}_a\cdot b<2abab−1​⋅a+ba−1​⋅b<2ab，这个过程也不难，由于 1≤ab−1

4. 由于在开区间 (1,2ab)(1, 2ab)(1,2ab) 中，模 ababab 意义下与 111 同余的数只有 ab+1ab+1ab+1 一个，因此可知：
   ab+1=ab−1⋅a+ba−1⋅bab+1=a^{-1}_b\cdot a+b^{-1}_a\cdot b ab+1=ab−1​⋅a+ba−1​⋅b

等式得证。

定理 111：任意整数 n≥ab−a−b+1n\geq ab-a-b+1n≥ab−a−b+1，均能写成 n=pa+qbn=pa+qbn=pa+qb 的形式，其中 a,ba, ba,b 为一对互质的正整数，p,qp, qp,q 为非负整数

这一命题就是小凯的疑惑中的核心命题。当 a=1a=1a=1 时，ab−a−b+1=0ab-a-b+1=0ab−a−b+1=0，命题退化为：对于任意正整数 nnn，都能写成 n=p⋅1+q⋅bn=p\cdot1+q\cdot bn=p⋅1+q⋅b 的形式。不难发现取 p=n,q=0p=n, q=0p=n,q=0 即可。当 b=1b=1b=1 时，也是类似的情况，结论显然是正确的。因此我们只需要考虑 a>1a>1a>1 且 b>1b>1b>1 的情况。

根据引理 111：ab+1=ab−1⋅a+ba−1⋅bab+1=a^{-1}_b\cdot a+b^{-1}_a\cdot bab+1=ab−1​⋅a+ba−1​⋅b，我们得到：
ab−a−b+1=(ab−1−1)⋅a+(ba−1−1)⋅bab-a-b+1=(a^{-1}_b-1)\cdot a+(b^{-1}_a-1)\cdot b ab−a−b+1=(ab−1​−1)⋅a+(ba−1​−1)⋅b

根据标准逆元的性质，1≤ab−1,1≤ba−11\leq a^{-1}_b, 1\leq b^{-1}_a1≤ab−1​,1≤ba−1​，因此 ab−1−1≥0a^{-1}_b-1\geq 0ab−1​−1≥0，ba−1−1≥0b^{-1}_a-1\geq 0ba−1​−1≥0。可以看到当 n=ab−a−b+1n=ab-a-b+1n=ab−a−b+1 时，取 p=ab−1−1,q=ba−1−1p=a^{-1}_b-1, q=b^{-1}_a-1p=ab−1​−1,q=ba−1​−1，那么 n=pa+qbn=pa+qbn=pa+qb 就是一种符合要求的表示方式，因此当 n=ab−a−b+1n=ab-a-b+1n=ab−a−b+1，“符合条件的表示”存在。（这只是一个打酱油的证明，后面的内容根本没有用到它。）

根据拓展欧几里得定理，我们能够找到一对整数 p′,q′p', q'p′,q′ 使得：

1=p′a+q′b1=p'a+q'b 1=p′a+q′b

换言之，n=(np′)a+(bq′)bn=(np')a+(bq')bn=(np′)a+(bq′)b，在形式上看起来符合 “n=pa+qbn=pa+qbn=pa+qb” 这一形式，但是实际上我们并不能保证 p′p'p′ 和 q′q'q′ 都是非负的。但是我们接下来可以证明，一定存在一个整数 ttt 使得：
n=(np′+t⋅b)a+(nq′−t⋅a)bn=(np'+t\cdot b)a+(nq'-t\cdot a)b n=(np′+t⋅b)a+(nq′−t⋅a)b

且满足 np′+t⋅b≥0,nq′−t⋅a≥0np'+t\cdot b\geq 0, nq'-t\cdot a\geq 0np′+t⋅b≥0,nq′−t⋅a≥0。通俗的讲，就是 p,qp, qp,q 的原始解 (np′,nq′)(np', nq')(np′,nq′) 一定能够平移到一组非负解上。记 p(t)=np′+t⋅b,q(t)=nq′−t⋅ap(t)=np'+t\cdot b, q(t)=nq'-t\cdot ap(t)=np′+t⋅b,q(t)=nq′−t⋅a，可以看到，p(t)p(t)p(t) 与 ttt 成正相关，q(t)q(t)q(t) 与 ttt 成负相关，我们要做的事情就是找到一个 ttt，使得 p(t)p(t)p(t) 与 q(t)q(t)q(t) 均大于等于零。

考虑反证法，假设不存在满足条件的 ttt 使得 p(t)p(t)p(t) 与 q(t)q(t)q(t) 同时大于等于零 ，换言之，当 p(t)≥0p(t)\geq 0p(t)≥0 时 q(t)q(t)q(t) 一定小于零，当 q(t)≥0q(t)\geq 0q(t)≥0 时 p(t)p(t)p(t) 一定小于零。那么一定存在着一个分界点 t0t_0t0​ 使得:
p(t−1)<0,p(t)≥0,q(t)<0\begin{aligned} p(t-1)<0, p(t)\geq 0, q(t)<0\\ \end{aligned} p(t−1)<0,p(t)≥0,q(t)<0​

此时 t=t0t=t_0t=t0​ 是能使得 p(t)≥0p(t)\geq 0p(t)≥0 的最小的 ttt 值。由于 p(t)p(t)p(t) 的单调性，p(t)≥0p(t)\geq 0p(t)≥0 当且仅当 t≥t0t\geq t_0t≥t0​。再增大 ttt，只会让 p(t)p(t)p(t) 变得更大，q(t)q(t)q(t) 变得更小。如果 t=t0t=t_0t=t0​ 不能使 q(t)≥0q(t)\geq 0q(t)≥0，那么 p(t),q(t)p(t),q(t)p(t),q(t) 就一定不能同时大于等于零。接下来我们要推出矛盾，从而证明假设不成立。

由 p(t−1)<0p(t-1)<0p(t−1)<0 得到 np′+(t−1)b<0np'+(t-1)b<0np′+(t−1)b<0 即 np′+tb

由于 q(t)<0q(t)<0q(t)<0，因此 q(t)≤−1q(t)\leq -1q(t)≤−1 进而 q(t)⋅b≤−bq(t)\cdot b\leq -bq(t)⋅b≤−b 所以 −q(t)⋅b≥b-q(t)\cdot b\geq b−q(t)⋅b≥b。我们已知 n≥ab−a−b+1n\geq ab-a-b+1n≥ab−a−b+1 带入 n=p(t)a+q(t)bn=p(t)a+q(t)bn=p(t)a+q(t)b 得到：

p(t)a+q(t)b≥ab−a−b+1∴p(t)a≥−q(t)b+ab−a−b+1≥ab−a+1=(b−1)a+1\begin{aligned} p(t)a+q(t)b&\geq ab-a-b+1\\ \therefore p(t)a&\geq -q(t)b+ab-a-b+1\geq ab-a+1=(b-1)a+1 \end{aligned} p(t)a+q(t)b∴p(t)a​≥ab−a−b+1≥−q(t)b+ab−a−b+1≥ab−a+1=(b−1)a+1​

而这里与上文中 p(t)⋅a≤(b−1)ap(t)\cdot a\leq (b-1)ap(t)⋅a≤(b−1)a 矛盾。换言之，存在 ttt 使得 p(t)p(t)p(t) 与 q(t)q(t)q(t) 同时大于等于零。另外，根据 np′+tb=np′modbnp'+tb=np'\mod bnp′+tb=np′modb，我们得到了一种构造 ttt 的方式：

t=−⌊np′b⌋t=-\left\lfloor\frac{np'}{b}\right\rfloor t=−⌊bnp′​⌋

因此，对于任意的 n≥ab−a−b+1n\geq ab-a-b+1n≥ab−a−b+1 取 p=np′−⌊np′b⌋⋅b,q=nq′+⌊np′b⌋⋅ap=np'-\left\lfloor\frac{np'}{b}\right\rfloor \cdot b, q=nq'+\left\lfloor\frac{np'}{b}\right\rfloor \cdot ap=np′−⌊bnp′​⌋⋅b,q=nq′+⌊bnp′​⌋⋅a 则有以下条件成立：

1. n=pa+qbn=pa+qbn=pa+qb；
2. p≥0,q≥0p\geq 0, q\geq 0p≥0,q≥0；

定理 222：对于 n=ab−a−bn=ab-a-bn=ab−a−b，a,ba,ba,b 为互质的正整数，不存在非负整数对 p,qp, qp,q 使得 n=pa+qbn=pa+qbn=pa+qb

当 a=1a=1a=1 时，n=ab−a−b=b−1−b=−1<0n=ab-a-b=b-1-b=-1<0n=ab−a−b=b−1−b=−1<0 而 pa+qb≥0pa+qb\geq 0pa+qb≥0，因此定理在此条件下成立。当 b=1b=1b=1 时也是同理。因此我们只需要考虑 a>1a>1a>1 且 b>1b>1b>1 的情况。

考虑等式 ab−a−b=pa+qbab-a-b=pa+qbab−a−b=pa+qb。两侧同时模 bbb 得到 −b≡qbmoda-b\equiv qb \mod a−b≡qbmoda，同余式两侧同时乘以 ba−1b^{-1}_aba−1​，可以得到 q≡−1modaq \equiv -1 \mod aq≡−1moda。使用类似的方法，可以得到 p≡−1modbp\equiv -1 \mod bp≡−1modb。倘若等式可能有 p,qp, qp,q 的非负整数解，那么一定有：

p∈{−1+k1⋅b∣k1∈Z}q∈{−1+k2⋅a∣k2∈Z}\begin{aligned} p\in\{-1+k_1\cdot b\mid k_1\in \Z\}\\ q\in\{-1+k_2\cdot a\mid k_2\in \Z\} \end{aligned} p∈{−1+k1​⋅b∣k1​∈Z}q∈{−1+k2​⋅a∣k2​∈Z}​

又根据 p≥0,q≥0,a>1,b>1p\geq 0, q\geq 0, a>1, b>1p≥0,q≥0,a>1,b>1，可知 p≥b−1,q≥a−1p\geq b-1, q\geq a-1p≥b−1,q≥a−1，因此 pa+qb≥(b−1)a+(a−1)b=2ab−a−b>ab−a−bpa+qb\geq(b-1)a+(a-1)b=2ab-a-b>ab-a-bpa+qb≥(b−1)a+(a−1)b=2ab−a−b>ab−a−b。因此 ab−a−bab-a-bab−a−b 与 pa+qbpa+qbpa+qb 不可能相等，故命题得证。