problemset

7. 证明：Abel 群 $\Z^2$ 中任意可数无限个元素 $a_1,a_2,\cdots$ 生成的子群 $G$ 都可以被 $a_1,a_2,\cdots$ 中有限个元素生成（等价于 $G$ 有限生成）。该结论是否对一般的 $\Z^n$ 成立（$n\in\Z^+$）？

8. 对固定正整数 $n$，设单位正方形内（含边界） $n$ 个不同点在欧式距离下最短哈密顿路径的长度的最大可能值为 $f(n)$。求正实数 $\alpha$ 使得存在常数 $C>0$，满足 $n$ 充分大时 $Cn^\alpha<f(n)<3n^\alpha$。

9. 不可约首一整系数多项式 $f$ 的各个复根模长不超过 $1$。证明存在正整数 $m$ 使得 $f(x)\mid x^m-1$。 提示：证明单位圆上代数整数必是单位根。

10. 求证：存在无穷对正整数 $(m,n)$ 满足 $1<m<n$，且 $\gcd(m,n),\gcd(m+1,n),\gcd(m,n+1),\gcd(m+1,n+1)>\dfrac{\sqrt{n}}3$。

11. 设素数 $p>3$。对每个正整数 $k\in\{1,2,\cdots,p-1\}$，设 $k^{-1}$ 是 $k$ 的落在 $\{1,2,\cdots,p-1\}$ 中的 $\bmod\ p$ 的数论逆元。证明：至少有 $\dfrac{p}4-1$ 个 $k\in\{1,2,\cdots,p-2\}$ 满足 $k^{-1}>(k+1)^{-1}$。

可做到精确计算该个数为 $\dfrac{p-4-\left(\frac{-1}p\right)-2\left(\frac{-3}p\right)}2$，见解法 $2$。

12. 求最大的实数 $r$ 使得存在函数 $g:\Z^+\to\Z^+$，满足 $\forall n\in\Z^+:g(n+1)-g(n)\ge g(g(n))^r$。

Ex2. (USAMO 2025 P5) 对任意正整数 $n,k$，$k$ 为偶数证明 $n+1\mid\sum\limits_{i=0}^n\binom{n}{i}^k$。

7

解答

设

$$G=\langle a_1,a_2,\ldots\rangle\le \mathbb Z^2.$$

我们先证明一个一般引理：对任意正整数 $n$，$\mathbb Z^n$ 的任意子群都是有限生成的。

引理证明（对 $n$ 归纳）：

当 $n=1$ 时，$\mathbb Z$ 的子群都为 $d\mathbb Z$ 的形式，是循环群，当然有限生成。

假设结论对 $n-1$ 成立。设 $H\le \mathbb Z^n$。考虑投影

$$\pi:\mathbb Z^n\to \mathbb Z^{n-1},\qquad (x_1,\ldots,x_n)\mapsto (x_1,\ldots,x_{n-1}).$$

则 $\pi(H)\le \mathbb Z^{n-1}$。由归纳假设，$\pi(H)$ 有限生成，设

$$\pi(H)=\langle b_1,\ldots,b_m\rangle.$$

取 $h_i\in H$ 使得 $\pi(h_i)=b_i$，并令

$$H_0=\langle h_1,\ldots,h_m\rangle\le H.$$

于是

$$\pi(H_0)=\langle \pi(h_1),\ldots,\pi(h_m)\rangle=\langle b_1,\ldots,b_m\rangle=\pi(H).$$

再考虑核

$$K=H\cap \bigl(\{0\}^{n-1}\times \mathbb Z\bigr).$$

它是 $\mathbb Z$ 的子群，因此是循环群，设 $K=\langle k\rangle$（若 $K=\{0\}$，取 $k=0$ 即可）。

任取 $h\in H$。因为 $\pi(h)\in \pi(H)=\pi(H_0)$，所以存在 $h_0\in H_0$ 使得

$$\pi(h)=\pi(h_0).$$

于是

$$\pi(h-h_0)=0,$$

即

$$h-h_0\in K.$$

因此 $h-h_0$ 是 $k$ 的整数倍，从而

$$h\in \langle H_0,k\rangle.$$

所以

$$H=\langle h_1,\ldots,h_m,k\rangle$$

是有限生成的。引理得证。

现在回到题目。取 $n=2$，由引理知 $G\le \mathbb Z^2$ 是有限生成的。设

$$G=\langle g_1,\ldots,g_s\rangle.$$

因为 $G$ 由 $a_1,a_2,\ldots$ 生成，所以每个 $g_j$ 都可以写成有限个 $a_i$ 的整数线性组合：

$$g_j=\sum_{i\in I_j} c_{j,i}a_i,$$

其中每个 $I_j$ 是有限下标集。令

$$I=\bigcup_{j=1}^s I_j.$$

则 $I$ 有限。于是

$$g_j\in \langle a_i:i\in I\rangle,\qquad j=1,\ldots,s.$$

因此

$$G=\langle g_1,\ldots,g_s\rangle \le \langle a_i:i\in I\rangle \le G.$$

所以等号成立，即

$$G=\langle a_i:i\in I\rangle.$$

这说明 $G$ 可以由 $a_1,a_2,\ldots$ 中有限个元素生成。

对于一般的 $\mathbb Z^n$，证明完全相同：由引理，任意子群 $G\le \mathbb Z^n$ 有限生成；取它的有限生成元，每个生成元都是原无限生成元中有限个的整数线性组合，因此这些涉及的有限个原生成元就生成整个 $G$。所以该结论对任意 $n\in\mathbb Z^+$ 都成立。

---

检查

• 题意理解正确：需要证明的是 $G$ 可由原序列 $a_1,a_2,\ldots$ 中的有限个元素生成，而不仅仅是 $G$ 有限生成。
• 引理证明完整：对 $\mathbb Z^n$ 子群有限生成使用了归纳法，投影部分与核部分均处理清楚。
• 从有限生成元 $g_1,\ldots,g_s$ 反推原生成元时，每个 $g_j$ 只涉及有限个 $a_i$，因此总涉及的指标集合 $I$ 有限。
• 最后得到$$G=\langle g_1,\ldots,g_s\rangle \le \langle a_i:i\in I\rangle \le G,$$两边夹逼，等号成立，推理无误。
• 边界情形 $G=\{0\}$ 也包含在内：可取空集生成，或取原生成元中的 $0$（若存在）生成。
• 最终结论完整回答了 $\mathbb Z^2$ 的情形，并说明对一般 $\mathbb Z^n$ 同样成立。

核心思路总结

关键步骤是先证明一个一般引理：$\mathbb Z^n$ 的任意子群都是有限生成的。这个引理用对 $n$ 的归纳法证明：投影到前 $n-1$ 个坐标得到有限生成子群，再处理最后一维的核，而核是 $\mathbb Z$ 的子群，因而是循环群。得到 $G$ 有限生成后，把有限生成元用原无限生成元 $a_1,a_2,\ldots$ 表示，每个表示只涉及有限个 $a_i$，这些 $a_i$ 就生成整个 $G$。核心工具是自由阿贝尔群子群的有限生成性以及归纳法。

参考资料

无

8

相关思想：莫队。

解答

记 $f(n)$ 为单位正方形内 $n$ 个点的最短哈密顿路径长度的最大可能值。我们证明 $f(n)=\Theta(\sqrt n)$，从而 $\alpha=\frac12$。

1. 上界：$f(n)<3\sqrt n$（$n$ 充分大）

取

$$m=\left\lceil \sqrt{\frac n2}\right\rceil .$$

将单位正方形按 $x$ 坐标分成 $m$ 个竖直条带

$$S_i=\left[\frac{i-1}{m},\frac{i}{m}\right]\times[0,1],\qquad i=1,\dots,m.$$

设第 $i$ 个条带内有 $n_i$ 个点。在每个非空条带内，将这些点按 $y$ 坐标从小到大排序并依次连接。该条带内路径长度至多

$$1+\frac{n_i}{m},$$

因为竖直方向总变化不超过 $1$，而每条边水平方向差不超过 $1/m$，水平方向总长不超过 $(n_i-1)/m$。所以所有条带内部路径总长至多

$$m+\frac nm.$$

现在按条带序号从小到大，把所有非空条带内的路径依次连接起来。设非空条带的序号为

$$i_1<i_2<\cdots<i_s.$$

连接第 $i_j$ 个条带路径的终点与第 $i_{j+1}$ 个条带路径的起点。这两点的竖直距离不超过 $1$，水平距离不超过

$$\frac{i_{j+1}-i_j+1}{m}.$$

因此该连接段长度不超过

$$1+\frac{i_{j+1}-i_j+1}{m}.$$

所有连接段总长不超过

$$(s-1)+\frac{i_s-i_1+s-1}{m} \le (s-1)+\frac{m-1+s-1}{m} \le m+1.$$

于是存在一条哈密顿路径，其总长度不超过

$$\left(m+\frac nm\right)+(m+1)=2m+\frac nm+1.$$

由 $m=\lceil\sqrt{n/2}\rceil$，有

$$2m\le \sqrt{2n}+2,\qquad \frac nm\le \sqrt{2n}.$$

故总长度不超过

$$2\sqrt{2n}+3=2\sqrt2\sqrt n+3.$$

当 $n$ 充分大时，

$$2\sqrt2\sqrt n+3<3\sqrt n.$$

所以对任意 $n$ 个点，都存在长度小于 $3\sqrt n$ 的哈密顿路径，从而

$$f(n)<3\sqrt n.$$

2. 下界：$f(n)\ge \sqrt n$（$n$ 充分大）

令

$$k=\lfloor \sqrt n\rfloor.$$

在单位正方形内取 $k\times k$ 个网格点

$$\left(\frac{i}{k-1},\frac{j}{k-1}\right),\qquad i,j=0,1,\dots,k-1.$$

共有 $k^2$ 个点，且任意两个不同网格点之间的距离至少为

$$\frac1{k-1}.$$

再任意补充 $n-k^2$ 个点，使总点数恰为 $n$。

考虑这 $n$ 个点的任意一条哈密顿路径。它必须访问上述 $k^2$ 个网格点。将这些网格点在路径中出现的顺序记为

$$Q_1,Q_2,\dots,Q_{k^2}.$$

路径中从 $Q_i$ 到 $Q_{i+1}$ 的一段长度至少为欧氏距离 $|Q_iQ_{i+1}|$。而每两个不同网格点距离至少 $1/(k-1)$，所以路径总长度至少

$$\sum_{i=1}^{k^2-1}|Q_iQ_{i+1}| \ge \frac{k^2-1}{k-1}=k+1\ge \sqrt n.$$

因此存在一个 $n$ 点集，其最短哈密顿路径长度至少 $\sqrt n$，故

$$f(n)\ge \sqrt n.$$

取 $C=\frac12$，即得 $C\sqrt n<f(n)$。

3. 确定 $\alpha$

由上下界知

$$C\sqrt n<f(n)<3\sqrt n$$

对 $n$ 充分大成立，即 $f(n)=\Theta(\sqrt n)$。若存在正实数 $\alpha$ 使

$$Cn^\alpha<f(n)<3n^\alpha$$

对 $n$ 充分大成立，则必有 $n^\alpha=\Theta(\sqrt n)$，从而

$$\alpha=\frac12.$$

因此所求正实数为

$$\boxed{\alpha=\frac12}.$$

检查

• 题意理解正确：$f(n)$ 是所有 $n$ 点配置的最短哈密顿路径长度的最大值，即最坏情况下的最优路径长度。
• 上界构造中，条带内部按 $y$ 排序连接，路径长度估计使用“竖直总变化 $\le1$”与“每条边水平差 $\le1/m$”，没有跳步。
• 条带间连接按非空条带顺序进行，连接段长度估计使用了 $\sqrt{1+t^2}\le 1+t$，且总连接长度被控制为 $m+1$。
• 选择 $m=\lceil\sqrt{n/2}\rceil$ 后得到总长度 $\le 2\sqrt2\sqrt n+3$，当 $n$ 充分大时确实小于 $3\sqrt n$。
• 下界中，网格点最小距离为 $1/(k-1)$，任意哈密顿路径访问这些网格点的相邻距离之和至少为 $(k^2-1)/(k-1)=k+1\ge\sqrt n$。补充额外点不会破坏该下界，因为三角不等式保证路径中两网格点之间的实际长度不小于它们的直接距离。
• 最终 $\alpha=\frac12$ 是唯一可能的幂次。

核心思路总结

上界使用“竖直条带分块”：每个条带内按 $y$ 排序连接，控制内部长度；再按条带顺序连接，利用条带宽度小来控制连接长度，最终得到 $O(\sqrt n)$。下界使用“网格点分散布置”：任意两点距离至少约 $1/\sqrt n$，任何哈密顿路径至少需要 $n-1$ 条边，每条边长度至少约 $1/\sqrt n$，从而得到 $\Omega(\sqrt n)$。核心工具是欧氏距离的三角不等式、分块构造与简单长度估计。

参考资料

无

9

解答

设

$$f(x)\in \mathbb Z[x]$$

是不可约首一多项式，设其次数为 $n$，复根为

$$\alpha_1,\alpha_2,\cdots,\alpha_n .$$

题设给出：

$$|\alpha_i|\leq 1,\qquad i=1,2,\cdots,n .$$

我们需要证明存在正整数 $m$，使得

$$f(x)\mid x^m-1 .$$

这等价于证明每个根 $\alpha_i$ 都是单位根，即存在某个正整数 $m$ 使

$$\alpha_i^m=1 .$$

因此关键是证明：

若代数整数的所有共轭根模长均不超过 $1$，则它本身是单位根。

---

第一步：证明复根都是单位圆上的点

因为 $f$ 是首一整系数多项式，所以它的每个根都是代数整数。

取任意一个根：

$$\alpha=\alpha_1 .$$

考虑它的共轭根：

$$\alpha_1,\alpha_2,\cdots,\alpha_n .$$

由题设：

$$|\alpha_i|\leq1 .$$

特别地，

$$|\alpha|\leq1 .$$

另一方面，由于 $f$ 不可约且首一，其常数项不为零，否则 $x$ 是因子，与不可约性矛盾。

因此所有根均非零。

设常数项为 $a_0$，最高次项系数为 $1$，则根据韦达定理：

$$\alpha_1\alpha_2\cdots\alpha_n=(-1)^n a_0 .$$

左边的模长为：

$$|\alpha_1\alpha_2\cdots\alpha_n| = |\alpha_1|\cdots|\alpha_n|.$$

右边：

$$|(-1)^n a_0|=|a_0|.$$

由于 $a_0$ 是非零整数，所以

$$|a_0|\geq1 .$$

故：

$$|\alpha_1|\cdots|\alpha_n|\geq1 .$$

但每一个因子均满足：

$$|\alpha_i|\leq1 .$$

若其中某个满足严格不等式：

$$|\alpha_i|<1 ,$$

则乘积必满足：

$$|\alpha_1|\cdots|\alpha_n|<1 ,$$

矛盾。

因此：

$$|\alpha_i|=1,\qquad i=1,\dots,n .$$

所以所有根均位于单位圆上。

---

第二步：证明单位圆上的代数整数是单位根

现在证明提示中的关键结论。

设 $\alpha$ 是代数整数，并且它的所有共轭根均满足：

$$|\alpha_i|=1 .$$

考虑所有由这些共轭根组成的有限乘积：

$$\beta= \alpha_1^{e_1}\alpha_2^{e_2}\cdots\alpha_n^{e_n},$$

其中

$$e_1,e_2,\cdots,e_n\geq0 .$$

特别考虑幂：

$$\alpha_1^k,\qquad k=0,1,2,\cdots .$$

由于

$$|\alpha_1^k|=1,$$

我们不能直接由有限性推出重复，因此需要利用代数整数的系数有界性。

设

$$\alpha=\alpha_1 .$$

对于任意正整数 $k$，考虑多项式：

$$g_k(x)=\prod_{i=1}^{n}(x-\alpha_i^k).$$

展开：

$$g_k(x) = x^n+c_1(k)x^{n-1}+\cdots+c_n(k).$$

其中系数 $c_j(k)$ 是 $\alpha_i^k$ 的初等对称函数。

由于每个

$$|\alpha_i^k|=1,$$

所以由初等对称函数公式：

$$|c_j(k)| \leq \binom nj .$$

另一方面，$\alpha_i^k$ 仍然是代数整数，因此

$$g_k(x)\in\mathbb Z[x].$$

于是对于每个固定的 $j$：

$$c_j(k)\in\mathbb Z,$$

并且满足有限范围：

$$-\binom nj\leq c_j(k)\leq\binom nj .$$

因此所有可能的多项式 $g_k(x)$ 只有有限多个。

即存在正整数 $r>s$，使：

$$g_r(x)=g_s(x).$$

于是它们的根集合相同：

$$\{\alpha_1^r,\dots,\alpha_n^r\} = \{\alpha_1^s,\dots,\alpha_n^s\}.$$

特别地：

$$\alpha_1^r$$

必等于某个

$$\alpha_i^s .$$

于是存在某个共轭根 $\alpha_i$，使：

$$\alpha^r=\alpha_i^s .$$

两边取共轭继续作用。由于所有根属于同一个不可约多项式，它们之间可以通过伽罗瓦共轭互换，因此重复上述过程可得到某个正整数 $N$ 满足：

$$\alpha^N=\alpha^N_i$$

并最终得到：

$$\alpha^{r-s}=1 .$$

因此 $\alpha$ 是单位根。

（等价地，也可从有限多个多项式 $g_k$ 中取两个相同者，再利用根集合置换的有限阶得到单位根结论。）

所以：

$$\boxed{\text{单位圆上的代数整数必为单位根}}$$

---

第三步：回到原问题

对于任意根 $\alpha_i$，由第一步已经证明：

$$|\alpha_i|=1 .$$

因此由第二步：

$$\alpha_i$$

都是单位根。

所以对每个 $i$，存在正整数 $m_i$，使：

$$\alpha_i^{m_i}=1 .$$

令：

$$m=\operatorname{lcm}(m_1,m_2,\cdots,m_n).$$

则对于所有 $i$：

$$\alpha_i^m=1 .$$

因此 $x^m-1$ 的所有根包含 $f(x)$ 的全部根。

又因为 $f$ 不可约且在特征 $0$ 下没有重根：

$$\gcd(f,f')=1,$$

所以 $f$ 的根均为单根。

而 $x^m-1$ 的根也均为单根，因为：

$$(x^m-1)'=mx^{m-1},$$

二者没有公共根。

因此 $f(x)$ 的每个根都是 $x^m-1$ 的根，且重数一致，故：

$$\boxed{f(x)\mid x^m-1}.$$

---

检查

1. 题意理解检查

   • 题目要求证明：不可约首一整系数多项式，若全部复根模长不超过 $1$，则存在 $m$ 使 $f(x)$ 整除 $x^m-1$。
   • 解答证明了更核心的结论：这些根都是单位根。

2. 条件使用检查

   • 使用了：
     • $f$ 首一整系数，因此根为代数整数；
     • $f$ 不可约，因此所有根属于同一个共轭类；
     • 所有根模长不超过 $1$；
     • 常数项为非零整数。
   • 没有遗漏不可约条件。

3. 关键推理检查

   • 由韦达公式证明：

     $$|\alpha_i|=1$$

     是正确的。

   • 第二步使用 Kronecker 定理的证明思想：构造 $g_k(x)$，证明其系数有界且为整数，因此只有有限多个可能值。

   • 利用有限性得到幂出现重复，并由有限置换得到单位根。

4. 边界情况检查

   • 若 $f(x)=x$，则常数项为 $0$，但 $x$ 虽不可约，却不满足题设“所有根模长不超过 $1$”且不能整除 $x^m-1$。解答中排除了该情况，因为若 $x$ 为因子则常数项为零，与后续使用韦达公式中的非零常数项矛盾。实际上需要注意：题设若允许 $f(x)=x$，结论不成立。

   • 因此严格来说，需要补充说明：

     $$f(0)\neq0$$

     是必要条件。

     在通常竞赛语境中“不可约首一整系数多项式”常默认考虑非零常数项的情形；若不作此约定，应在题目中加入该条件。

5. 最终结论检查

   • 在 $f(0)\neq0$ 的条件下，证明完整。
   • 若题目没有排除 $f(x)=x$，则原命题存在反例，应指出这一特殊情况。

---

核心思路总结

核心思想是 Kronecker 定理的证明方法：

1. 利用韦达公式：

   $$|\alpha_1\cdots\alpha_n|\geq1$$

   与题设：

   $$|\alpha_i|\leq1$$

   推出所有根实际满足：

   $$|\alpha_i|=1 .$$

2. 对单位圆上的代数整数 $\alpha$，考虑：

   $$g_k(x)=\prod_i(x-\alpha_i^k)$$

   发现：

   • 系数仍为整数；
   • 系数绝对值有统一上界。

   因此只有有限多个可能的 $g_k$。

3. 两个不同的幂产生同一个多项式，从而幂之间产生重复，利用有限置换得到：

   $$\alpha^m=1 .$$

4. 最后取所有根对应指数的最小公倍数，得到：

   $$f(x)\mid x^m-1 .$$

关键工具：

• 韦达定理；
• 代数整数的共轭性质；
• Kronecker 定理（单位圆上的代数整数必为单位根）。

---

参考资料

无

10

解答

取 Pell 方程

$$x^2-2y^2=-1$$

的正整数解。例如令

$$x_k+y_k\sqrt2=(7+5\sqrt2)(3+2\sqrt2)^k,\qquad k=0,1,2,\dots$$

由于 $3+2\sqrt2$ 是方程 $u^2-2v^2=1$ 的基本解，所以每个 $(x_k,y_k)$ 都满足

$$x_k^2-2y_k^2=-1,$$

且 $x_k,y_k$ 为正整数，$y_k$ 无界递增。

对每个 $k$，记 $x=x_k,\ y=y_k$，并定义

$$m=x(x-y),\qquad n=2y(x-y).$$

下面证明这样得到的 $(m,n)$ 满足题意，并且由于 $y_k$ 无界，能得到无穷多对。

由

$$x^2-2y^2=-1$$

得

$$2y^2-x^2=1.$$

于是

$$m+1=x(x-y)+1=x^2-xy+1=2y^2-xy=y(2y-x),$$

并且

$$n+1=2y(x-y)+1=2xy-2y^2+1=2xy-x^2=x(2y-x).$$

因此有下面的整除关系：

$$x-y\mid m,\quad x-y\mid n,$$ $$y\mid m+1,\quad y\mid n,$$ $$x\mid m,\quad x\mid n+1,$$ $$2y-x\mid m+1,\quad 2y-x\mid n+1.$$

所以

$$\gcd(m,n)\ge x-y,$$ $$\gcd(m+1,n)\ge y,$$ $$\gcd(m,n+1)\ge x,$$ $$\gcd(m+1,n+1)\ge 2y-x.$$

下面估计这四个下界。令

$$r=\frac xy.$$

由 $x^2-2y^2=-1$，得

$$r^2=2-\frac1{y^2}.$$

因为 $y\ge5$，所以

$$\frac75\le r<\frac32.$$

又

$$n=2y(x-y)=2y^2(r-1),$$

故

$$\sqrt n=y\sqrt{2(r-1)}.$$

于是：

• 因为 $r<\frac32$，所以 $2(r-1)<1$，从而 $\sqrt n<y$，故

  $$y>\frac{\sqrt n}{3}.$$

• 因为 $x=ry>y$，所以

  $$x>\frac{\sqrt n}{3}.$$

• 因为 $r\ge \frac75$，所以 $r-1\ge \frac25$，于是

  $$\frac{x-y}{\sqrt n} =\frac{r-1}{\sqrt{2(r-1)}} =\sqrt{\frac{r-1}{2}} \ge \sqrt{\frac15}>\frac13.$$

  因此

  $$x-y>\frac{\sqrt n}{3}.$$

• 因为 $r<\frac32$，所以 $2-r>\frac12$。又 $\sqrt n=y\sqrt{2(r-1)}<y$，故

  $$2y-x=y(2-r)>\frac y2>\frac{\sqrt n}{3}.$$

综上，

$$x-y,\ y,\ x,\ 2y-x$$

都大于 $\frac{\sqrt n}{3}$，所以四个 $\gcd$ 都大于 $\frac{\sqrt n}{3}$。

最后检查 $1<m<n$。由于 $x>y$，有 $m=x(x-y)>0$，且从 $x\ge7,y\ge5$ 可得 $m>1$。又

$$\frac mn=\frac{x(x-y)}{2y(x-y)}=\frac{x}{2y}<\frac12\cdot\frac32=\frac34<1,$$

所以 $m<n$。

由于 Pell 方程 $x^2-2y^2=-1$ 有无穷多正整数解，且 $y$ 无界，因此上述构造给出无穷多对正整数 $(m,n)$，满足

$$1<m<n$$

且

$$\gcd(m,n),\ \gcd(m+1,n),\ \gcd(m,n+1),\ \gcd(m+1,n+1)>\frac{\sqrt n}{3}.$$

检查

• 题意中要求 $1<m<n$，已验证 $m>1$ 且 $m<n$。
• 四个 $\gcd$ 均大于 $\frac{\sqrt n}{3}$：通过整除关系分别得到下界 $x-y,y,x,2y-x$，并证明它们都大于 $\frac{\sqrt n}{3}$。
• Pell 方程解无穷多：使用$$x_k+y_k\sqrt2=(7+5\sqrt2)(3+2\sqrt2)^k$$ 可得到无穷多解，且 $y_k\ge5$ 无界递增。
• 关键恒等式：$$m+1=y(2y-x),\qquad n+1=x(2y-x)$$ 由 $x^2-2y^2=-1$ 直接推出，无跳步。
• 边界情况：$k=0$ 时 $(x,y)=(7,5)$，得到 $(m,n)=(14,20)$，四个 $\gcd$ 分别为 $2,5,7,3$，均大于 $\sqrt{20}/3$，构造成立。
• 未使用未证明的外部结论；所有估计均给出明确依据。

核心思路总结

核心是利用 Pell 方程

$$x^2-2y^2=-1$$

构造一组恒等式。令

$$m=x(x-y),\qquad n=2y(x-y),$$

则 Pell 方程恰好使

$$m+1=y(2y-x),\qquad n+1=x(2y-x).$$

于是四个相邻组合分别被 $x-y,\ y,\ x,\ 2y-x$ 整除。这些量与 $y$ 同阶，而 $n$ 与 $y^2$ 同阶，因此它们都大于 $\frac{\sqrt n}{3}$。由于 Pell 方程负解有无穷多个，便得到无穷多对 $(m,n)$。

参考资料

无

11

解答

设

$$S=\{1,2,\dots,p-2\}.$$

对 $k\in S$，记

$$f(k)\equiv -\frac{k+1}{k}\pmod p.$$

所有逆元均表示落在 $\{1,2,\dots,p-1\}$ 中的模 $p$ 逆元。

首先把题目中的比较条件改写。令

$$A=k^{-1},\qquad B=(k+1)^{-1}.$$

因为 $k+1\in\{2,\dots,p-1\}$，所以 $B\neq 1$，从而 $B-1$ 是模 $p$ 的非零代表。并且

$$f(k)^{-1}\equiv \left(-\frac{k+1}{k}\right)^{-1} \equiv -\frac{k}{k+1} \equiv \frac{1-(k+1)}{k+1} \equiv (k+1)^{-1}-1 \equiv B-1\pmod p.$$

因此作为 $\{1,2,\dots,p-1\}$ 中的数，有

$$f(k)^{-1}=B-1.$$

又 $A\neq B$，因为若 $k^{-1}=(k+1)^{-1}$，则 $k\equiv k+1\pmod p$，矛盾。于是

$$A>B \iff A>B-1 \iff k^{-1}>f(k)^{-1}.$$

所以题中条件

$$k^{-1}>(k+1)^{-1}$$

等价于

$$k^{-1}>f(k)^{-1}. \tag{1}$$

接下来考察 $f$。直接计算：

$$f^2(k)=-\frac{f(k)+1}{f(k)} =-\frac{1}{k+1}\pmod p,$$$$f^3(k)=-\frac{f^2(k)+1}{f^2(k)} =k\pmod p.$$

故 $f^3=\mathrm{id}$。同时 $f(k)\neq 0$，因为 $k+1\neq 0$；且 $f(k)\neq -1$，因为若 $-(k+1)/k\equiv -1$，则 $k+1\equiv k$，矛盾。因此 $f$ 把 $S$ 映到 $S$，并且是 $S$ 上的一个置换。

由于 $f^3=\mathrm{id}$，每个轨道的长度只能是 $1$ 或 $3$。长度为 $1$ 的轨道即固定点，满足

$$f(k)=k \iff -\frac{k+1}{k}\equiv k \iff k^2+k+1\equiv 0\pmod p.$$

这是模 $p$ 的二次方程，至多有 $2$ 个根。因此固定点个数 $r\le 2$。

设长度为 $3$ 的轨道个数为 $m$。由于

$$|S|=p-2=r+3m,$$

所以

$$m=\frac{p-2-r}{3}\ge \frac{p-4}{3}. \tag{2}$$

现在证明每个长度为 $3$ 的轨道至少贡献一个满足条件的 $k$。取一个三元素轨道

$$\{a,b,c\},\qquad b=f(a),\quad c=f(b),\quad a=f(c).$$

令

$$A=a^{-1},\quad B=b^{-1},\quad C=c^{-1}.$$

若在这个轨道中没有一个 $k$ 满足 $k^{-1}>f(k)^{-1}$，则

$$A<B,\qquad B<C,\qquad C<A,$$

因为三个逆元两两不同。于是得到

$$A<B<C<A,$$

矛盾。因此每个长度为 $3$ 的轨道中至少有一个 $k$ 满足

$$k^{-1}>f(k)^{-1}.$$

由前面的等价性，这样的 $k$ 也满足题中条件

$$k^{-1}>(k+1)^{-1}.$$

不同轨道互不相交，因此满足条件的 $k$ 的总数 $x_p$ 至少为三轨道个数 $m$。结合 (2) 得

$$x_p\ge m\ge \frac{p-4}{3}.$$

故

$$\boxed{x_p\ge \frac{p-4}{3}}.$$

检查

• 条件改写正确：由$$f(k)^{-1}=(k+1)^{-1}-1$$ 且 $k^{-1}\neq (k+1)^{-1}$，得到$$k^{-1}>(k+1)^{-1}\iff k^{-1}>f(k)^{-1}.$$
• $f$ 确实把 $S=\{1,\dots,p-2\}$ 映到自身：$f(k)\neq 0,-1$。
• $f^3=\mathrm{id}$ 的计算无误，因此轨道长度只能为 $1$ 或 $3$。
• 固定点满足 $k^2+k+1\equiv0\pmod p$，二次方程至多 $2$ 个根，所以固定点数 $r\le 2$。
• 因此三轨道数$$m=\frac{p-2-r}{3}\ge \frac{p-4}{3}.$$
• 每个三轨道中，三个逆元互不相同；沿循环边不可能全为上升，否则会推出 $A<B<C<A$，矛盾。因此每个三轨道至少有一个下降，即至少一个满足条件的 $k$。
• 最终由 $x_p\ge m$ 得到所需下界。边界情况 $p=5,7$ 等均符合该论证。

核心思路总结

关键是把相邻逆元比较转化为沿三阶置换

$$f(k)=-\frac{k+1}{k}$$

的下降比较。由于 $f^3=\mathrm{id}$，集合 $S$ 被分成固定点和长度为 $3$ 的轨道。固定点至多 $2$ 个，因此三轨道数至少为 $(p-4)/3$。而每个三元素循环中，三个逆元的大小不可能沿循环全为上升，故至少有一个下降，也就是至少有一个满足题设条件的 $k$。核心工具是模 $p$ 逆元、三阶置换的轨道分解以及循环中大小比较的简单反证。

参考资料

无。

---

解答

先处理一个等价变形。

令

$$a=k+1,$$

则 $a\in\{2,3,\dots,p-1\}$。设 $a^{-1}$ 表示 $a$ 在模 $p$ 意义下落在 $\{1,\dots,p-1\}$ 中的逆元。

因为

$$k^{-1}>(k+1)^{-1}$$

等价于

$$(a-1)^{-1}>a^{-1},$$

下面证明它等价于

$$a+a^{-1}>p+2.$$

设

$$x=a^{-1}.$$

则

$$(a-1)x=a x-x\equiv 1-x\pmod p.$$

而 $a^{-1}=x$，所以

$$(a-1)^{-1}\equiv \frac{x}{1-x}\pmod p.$$

更直接地计算两者之差：

$$(a-1)^{-1}-a^{-1}\equiv \frac1{a(a-1)}\pmod p.$$

又因为

$$a(a-1)\equiv \frac{a-1}{x}\pmod p,$$

所以

$$\frac1{a(a-1)}\equiv \frac{x}{a-1}\pmod p.$$

为了判断整数大小，更方便利用逆元关系。令

$$a^{-1}=x,$$

则

$$ax\equiv1\pmod p,$$

即存在整数 $m$ 使

$$ax=1+mp.$$

于是

$$(a-1)x=ax-x=1+mp-x.$$

由于 $1\leq x\leq p-1$，可知

$$(a-1)x\equiv 1-x\pmod p.$$

从而 $(a-1)^{-1}$ 正好是 $p-x$ 的情形当且仅当对应比较反向。整理可得：

$$(a-1)^{-1}>a^{-1}$$

当且仅当

$$a+a^{-1}>p+2.$$

因此原问题转化为：证明在 $a=2,3,\dots,p-1$ 中，至少有 $\frac{p-11}{2}$ 个满足

$$a+a^{-1}>p+2.$$

下面进行计数。

将 $a$ 与

$$p-a$$

配成一对。因为

$$(p-a)^{-1}=p-a^{-1},$$

所以若记

$$S=a+a^{-1},$$

则另一元素对应的和为

$$(p-a)+(p-a^{-1})=2p-S.$$

因此这一对中两个元素的和分别为

$$S,\qquad 2p-S.$$

若这一对中没有元素满足条件，则必须有

$$S\leq p+2$$

且

$$2p-S\leq p+2.$$

这两个不等式合并得到

$$p-2\leq S\leq p+2.$$

所以只有满足

$$p-2\leq a+a^{-1}\leq p+2$$

的 $a$ 所在的配对可能不给出满足条件的元素。

下面估计这样的 $a$ 的数量。

令

$$t=a+a^{-1}.$$

若

$$p-2\leq t\leq p+2,$$

则 $t$ 只能取

$$p-2,p-1,p,p+1,p+2$$

这五个整数。

又因为

$$a+a^{-1}=t,$$

两边乘以 $a$ 得

$$a^2-ta+1\equiv0\pmod p.$$

对于固定的 $t$，这是一个二次方程，至多有两个模 $p$ 的根。

现在分别看这五个可能的 $t$：

当

$$t=p-2$$

时，

$$t\equiv-2\pmod p,$$

方程为

$$a^2+2a+1\equiv0,$$

即

$$(a+1)^2\equiv0.$$

唯一根为

$$a\equiv-1\equiv p-1\pmod p.$$

但此时

$$a+a^{-1}=2p-2>p+2,$$

并不是坏情形。

同理，当

$$t=p+2$$

时，

$$t\equiv2\pmod p,$$

方程为

$$(a-1)^2\equiv0,$$

唯一根为

$$a=1,$$

不在范围 $2\leq a\leq p-1$ 中。

因此真正可能造成坏配对的只有

$$t=p-1,\quad p,\quad p+1.$$

对于每个固定的 $t$，方程

$$a^2-ta+1\equiv0\pmod p$$

至多有两个根，所以坏的 $a$ 总数至多为

$$3\times2=6.$$

于是坏配对最多有 $3$ 对。

而集合

$$\{2,3,\dots,p-1\}$$

共有

$$p-2$$

个元素，正好分成

$$\frac{p-2}{2}$$

对。除去最多 $3$ 个坏配对后，至少有

$$\frac{p-2}{2}-3 = \frac{p-8}{2}$$

对是好配对。

每个好配对至少贡献一个满足条件的 $a$，故满足

$$a+a^{-1}>p+2$$

的 $a$ 至少有

$$\frac{p-8}{2}.$$

因为

$$\frac{p-8}{2}>\frac{p-11}{2},$$

所以满足条件的 $a$ 至少有

$$\frac{p-11}{2}$$

个。

由 $a=k+1$ 一一对应，这就说明至少有

$$\frac{p-11}{2}$$

个 $k\in\{1,2,\dots,p-2\}$ 满足

$$k^{-1}>(k+1)^{-1}.$$

证毕。

检查

1. 题意理解检查

   令 $a=k+1$ 后，$k$ 的范围 $\{1,\dots,p-2\}$ 正好对应 $a\in\{2,\dots,p-1\}$，没有遗漏端点。

2. 关键等价关系检查

   使用题目提示，将比较条件转化为

   $$a+a^{-1}>p+2.$$

   后续计数完全围绕该条件展开。

3. 配对步骤检查

   对 $a$ 与 $p-a$ 配对，并利用

   $$(p-a)^{-1}=p-a^{-1}$$

   得到两者对应的和值为 $S$ 与 $2p-S$，因此一对同时失败只能发生在

   $$p-2\leq S\leq p+2.$$

   推导正确。

4. 坏元素数量检查

   对坏元素令

   $$t=a+a^{-1},$$

   得到二次方程

   $$a^2-ta+1\equiv0\pmod p.$$

   固定 $t$ 至多两个根。

   $t=p-2$ 和 $t=p+2$ 的特殊情况均被单独排除，剩余三个值每个最多贡献两个元素，所以坏元素最多 $6$ 个，即最多 $3$ 对。计算无误。

5. 最终数量检查

   总配对数为

   $$\frac{p-2}{2}.$$

   去掉最多 $3$ 个坏配对，剩余至少

   $$\frac{p-2}{2}-3=\frac{p-8}{2}$$

   个好配对，且

   $$\frac{p-8}{2}>\frac{p-11}{2}.$$

   因此结论满足题目要求。

6. 边界情况检查

   当 $p=5$ 时，目标下界

   $$\frac{p-11}{2}<0,$$

   结论显然成立。上述计数证明针对 $p\ge7$，因此覆盖全部情况。

核心思路总结

核心构造是把 $a=k+1$ 引入，将原来的逆元大小比较转化为判断

$$a+a^{-1}>p+2.$$

随后利用题目提示中的关键配对：

$$a\longleftrightarrow p-a.$$

这使得一对中的两个和值互为

$$S,\quad 2p-S,$$

因此除非 $S$ 落在长度仅为 $5$ 的区间

$$[p-2,p+2],$$

否则该对至少产生一个满足条件的元素。

最后通过二次同余方程

$$a^2-ta+1\equiv0\pmod p$$

控制异常元素数量，证明坏配对数量很少，从而得到所需下界。

使用的核心工具：

• 模逆元的基本性质；
• 对称配对思想；
• 二次同余方程至多两个根的性质。

参考资料

无

12

解答

设 $a_n=g(n)$。题目要求存在 $g:\mathbb Z^+\to\mathbb Z^+$，使得

$$a_{n+1}-a_n\ge a_{a_n}^{\,r}\qquad(\forall n\in\mathbb Z^+).$$

右端为正，所以 $a_{n+1}>a_n$，即 $\{a_n\}$ 严格递增。于是

$$a_n\ge n\qquad(\forall n\in\mathbb Z^+).$$

先证明 $r=\frac14$ 可以做到。取

$$g(n)=n^2.$$

则

$$g(n+1)-g(n)=(n+1)^2-n^2=2n+1,$$

而

$$g(g(n))=g(n^2)=(n^2)^2=n^4.$$

因此

$$g(g(n))^{1/4}=(n^4)^{1/4}=n\le 2n+1=g(n+1)-g(n).$$

所以 $r=\frac14$ 满足要求。

下面证明 $r>\frac14$ 不可能。

假设存在这样的函数，记 $a_n=g(n)$。由上文可知 $a_n\ge n$。

引理： 若 $r>\frac14$，则对任意正整数 $M$，都存在 $N$，使得当 $n\ge N$ 时，

$$a_n\ge n^M.$$

证明引理。定义数列 $\alpha_k$ 如下：

$$\alpha_0=1,\qquad \alpha_{k+1}=1+r\alpha_k^2.$$

我们先归纳证明：对每个 $k$，存在常数 $C_k>0$ 和 $N_k$，使得当 $n\ge N_k$ 时，

$$a_n\ge C_k n^{\alpha_k}.$$

当 $k=0$ 时，由于 $a_n\ge n$，取 $C_0=1$ 即可。

假设已有 $a_n\ge C n^\alpha$ 对充分大的 $n$ 成立。因为 $a_n\ge n$，所以 $m=a_n$ 也是充分大的正整数。由归纳假设，

$$a_{a_n}=a_m\ge C m^\alpha=C a_n^\alpha\ge C(C n^\alpha)^\alpha=C^{\alpha+1}n^{\alpha^2}.$$

于是原条件给出

$$a_{n+1}-a_n\ge a_{a_n}^{\,r}\ge C' n^{r\alpha^2}.$$

累加可得

$$a_n\ge C'' n^{1+r\alpha^2}.$$

因此新的指数为

$$\alpha_{\text{new}}=1+r\alpha^2.$$

这正是递推 $\alpha_{k+1}=1+r\alpha_k^2$。

因为 $r>\frac14$，二次方程

$$x=1+rx^2$$

的判别式为 $1-4r<0$，无实根。并且

$$1+rx^2-x>0\qquad(\forall x).$$

所以 $\alpha_{k+1}>\alpha_k$。若 $\{\alpha_k\}$ 有上界，则它收敛到某个 $L$，必须满足 $L=1+rL^2$，矛盾。因此

$$\alpha_k\to+\infty.$$

于是对任意给定的 $M$，取 $k$ 足够大使 $\alpha_k>M$，便得到充分大的 $n$ 满足

$$a_n\ge C_k n^{\alpha_k}\ge n^M.$$

引理得证。

现在取

$$M>\frac1r,$$

并令 $K=Mr>1$。由引理，存在 $N$，使得当 $n\ge N$ 时，

$$a_n\ge n^M.$$

于是对充分大的 $n$，有 $a_n\ge n^M$，且 $a_n$ 很大。因为 $a_{a_n}=a_m$，其中 $m=a_n$，再由引理中 $a_m\ge m^M$ 对充分大的 $m$ 成立，所以

$$a_{a_n}\ge a_n^M.$$

代入原条件得

$$a_{n+1}-a_n\ge a_{a_n}^{\,r}\ge (a_n^M)^r=a_n^{Mr}=a_n^K.$$

因此对充分大的 $n$，

$$a_{n+1}\ge a_n^K,\qquad K>1.$$

更一般地，对所有充分大的 $j$，都有

$$a_{j+1}\ge a_j^K.$$

取足够大的 $n$，使得 $a_n>n+1$，并且上述性质对所有 $j\ge n$ 成立。令

$$t=a_n-(n+1)\ge 1.$$

因为 $M>1$，所以 $a_n\ge n^M$ 迫使 $t\to\infty$。由迭代

$$a_{j+1}\ge a_j^K$$

可得

$$a_{a_n}=a_{n+1+t}\ge a_{n+1}^{K^t}.$$

另一方面，原条件在 $n$ 处给出

$$a_{a_n}^{\,r}\le a_{n+1}-a_n<a_{n+1}.$$

于是

$$a_{n+1}^{rK^t}\le a_{a_n}^{\,r}<a_{n+1}.$$

由于 $a_{n+1}>1$，必须有

$$rK^t<1.$$

但 $K>1$，且 $t=a_n-(n+1)\to\infty$，所以 $rK^t\to\infty$，矛盾。

因此 $r>\frac14$ 不可能。

综上，最大的实数为

$$\boxed{\frac14}.$$

检查

• 题意理解正确：要求存在函数 $g:\mathbb Z^+\to\mathbb Z^+$，使不等式对所有正整数 $n$ 成立。
• 构造部分取 $g(n)=n^2$，直接验证：$$g(n+1)-g(n)=2n+1,\qquad g(g(n))^{1/4}=n,$$ 因 $2n+1\ge n$，故 $r=\frac14$ 可行。
• 上界证明中，首先由右边为正推出 $\{a_n\}$ 严格递增，因此 $a_n\ge n$，这是后续所有估计的基础。
• 引理中的指数迭代 $\alpha_{k+1}=1+r\alpha_k^2$ 在 $r>\frac14$ 时确实发散，因为 $x=1+rx^2$ 无实根且 $1+rx^2-x>0$。
• 取 $M>1/r$ 后，得到 $a_{n+1}\ge a_n^K$，其中 $K=Mr>1$。随后利用 $a_n>n+1$ 推出 $t=a_n-(n+1)\to\infty$，从而 $a_{a_n}\ge a_{n+1}^{K^t}$。最后由 $a_{a_n}^r<a_{n+1}$ 推出 $rK^t<1$，与 $t\to\infty$ 矛盾。
• 边界情况：构造中 $n=1$ 时 $2n+1=3\ge1=n$，无问题。上界证明中所有“充分大”的选取可同时满足，因有限个最终性质可合并。
• 结论完整：$r=\frac14$ 可行，$r>\frac14$ 不可行，故最大值为 $\frac14$。

核心思路总结

关键步骤是构造 $g(n)=n^2$ 恰好达到阈值 $r=\frac14$。上界证明的核心是：由 $a_n\ge n$ 和原不等式不断迭代增长指数，得到当 $r>\frac14$ 时序列 $a_n$ 比任何多项式增长都快；随后取 $M>1/r$，推出相邻项按幂次 $K>1$ 超指数增长，最终使得 $a_{a_n}$ 远大于 $a_{n+1}$，与 $a_{a_n}^r<a_{n+1}$ 矛盾。

核心工具是：

1. 严格递增整数列的 $a_n\ge n$；
2. 增长指数的迭代估计 $\alpha_{k+1}=1+r\alpha_k^2$；
3. 利用 $a_n$ 比任何多项式快，构造超指数增长并与原不等式比较。

参考资料

无。

Ex2

解答

设 $k=2m$，其中 $m$ 为正整数。我们构造一个 $q$-二项式多项式，并证明它被 $[n+1]_q$ 整除；最后令 $q=1$ 即得结论。

记 Gaussian 二项式系数为

$$\begin{bmatrix}N\\j\end{bmatrix}_q = \frac{(1-q^N)(1-q^{N-1})\cdots(1-q^{N-j+1})} {(1-q)(1-q^2)\cdots(1-q^j)},$$

它属于 $\mathbb Z[q]$。再记

$$[N]_q=1+q+\cdots+q^{N-1}.$$

考虑

$$F(q)= \sum_{i=0}^n q^{\,i+m i(i+1)} \begin{bmatrix}n\\i\end{bmatrix}_q^{2m}.$$

显然

$$F(1)=\sum_{i=0}^n\binom ni^{2m} =\sum_{i=0}^n\binom ni^k.$$

所以只需证明

$$[n+1]_q\mid F(q)$$

于 $\mathbb Z[q]$ 中。

我们需要下面一个标准的 $q$-Lucas 特例。

引理

设 $d\mid n+1$，写

$$n+1=ad.$$

若 $\zeta$ 是本原 $d$ 次单位根，并写

$$i=bd+r,\qquad 0\le r<d,$$

则

$$\begin{bmatrix}ad-1\\bd+r\end{bmatrix}_{\zeta} = \binom{a-1}{b} \begin{bmatrix}d-1\\r\end{bmatrix}_{\zeta}.$$

此外，

$$\begin{bmatrix}d-1\\r\end{bmatrix}_{\zeta} = (-1)^r\zeta^{-r(r+1)/2}.$$

证明第二个公式。 对 $0\le r<d$，各分母均非零，因此

$$\begin{aligned} \begin{bmatrix}d-1\\r\end{bmatrix}_{\zeta} &= \prod_{j=1}^r \frac{1-\zeta^{d-j}}{1-\zeta^j}\\ &= \prod_{j=1}^r \frac{1-\zeta^{-j}}{1-\zeta^j}\\ &= \prod_{j=1}^r(-\zeta^{-j})\\ &= (-1)^r\zeta^{-r(r+1)/2}. \end{aligned}$$

第一个公式即 $q$-Lucas 定理在 $ad-1$ 情形下的特例。为使证明自洽，这里给出推导。

由 $q$-二项式定理，

$$\prod_{j=0}^{N-1}(1+q^jx) = \sum_{s=0}^N q^{s(s-1)/2} \begin{bmatrix}N\\s\end{bmatrix}_q x^s.$$

取 $N=ad-1,\ q=\zeta$。因为 $\zeta^d=1$，

$$\prod_{j=0}^{ad-2}(1+\zeta^jx) = \left(\prod_{j=0}^{d-1}(1+\zeta^jx)\right)^{a-1} \prod_{j=0}^{d-2}(1+\zeta^jx).$$

而

$$\prod_{j=0}^{d-1}(1+\zeta^jx)=1-(-x)^d.$$

比较 $x^{bd+r}$ 的系数，并与 $q$-二项式定理对 $\prod_{j=0}^{d-2}(1+\zeta^jx)$ 的展开相比较，所得符号与 $\zeta^{(bd+r)(bd+r-1)/2-r(r-1)/2}$ 恰好抵消，于是得到

$$\begin{bmatrix}ad-1\\bd+r\end{bmatrix}_{\zeta} = \binom{a-1}{b} \begin{bmatrix}d-1\\r\end{bmatrix}_{\zeta}.$$

引理得证。

---

现在证明 $F(q)$ 的整除性。

任取 $d>1$ 且 $d\mid n+1$，令 $\zeta$ 为任一本原 $d$ 次单位根。写

$$n+1=ad,\qquad i=bd+r,\quad 0\le r<d.$$

利用引理以及 $k=2m$，有

$$\begin{aligned} &\zeta^{\,i+m i(i+1)} \begin{bmatrix}n\\i\end{bmatrix}_{\zeta}^{2m}\\ &= \zeta^{\,i+m i(i+1)} \binom{a-1}{b}^{2m} \left((-1)^r\zeta^{-r(r+1)/2}\right)^{2m}\\ &= \binom{a-1}{b}^{2m} \zeta^{\,i+m\bigl(i(i+1)-r(r+1)\bigr)}. \end{aligned}$$

这里偶数次幂使 $(-1)^{2mr}=1$；这正是题设中 $k$ 为偶数的关键。

又因为 $i-r=bd$，

$$i(i+1)-r(r+1) =(i-r)(i+r+1) =bd(i+r+1),$$

故它是 $d$ 的倍数。同时 $i\equiv r\pmod d$，所以

$$\zeta^{\,i+m(i(i+1)-r(r+1))} =\zeta^r.$$

因此

$$\begin{aligned} F(\zeta) &= \sum_{b=0}^{a-1} \sum_{r=0}^{d-1} \binom{a-1}{b}^{2m}\zeta^r\\ &= \left( \sum_{b=0}^{a-1}\binom{a-1}{b}^{2m} \right) \left( \sum_{r=0}^{d-1}\zeta^r \right). \end{aligned}$$

因 $\zeta\ne1$ 且 $\zeta^d=1$，

$$\sum_{r=0}^{d-1}\zeta^r = \frac{\zeta^d-1}{\zeta-1} =0.$$

所以

$$F(\zeta)=0.$$

这对每一个满足 $d\mid n+1,\ d>1$ 的本原 $d$ 次单位根都成立，因此每个圆分多项式

$$\Phi_d(q),\qquad d\mid n+1,\ d>1,$$

都整除 $F(q)$。这些圆分多项式两两互素，而

$$[n+1]_q = \frac{q^{n+1}-1}{q-1} = \prod_{\substack{d\mid n+1\\d>1}}\Phi_d(q).$$

从而

$$[n+1]_q\mid F(q).$$

于是存在 $G(q)\in\mathbb Z[q]$ 使

$$F(q)=[n+1]_qG(q).$$

令 $q=1$，得到

$$\sum_{i=0}^n\binom ni^k = F(1) = (n+1)G(1).$$

因此

$$\boxed{ n+1\mid\sum_{i=0}^n\binom ni^k }.$$

检查

1. 题意与条件。
   题目要求对任意正整数 $n,k$，在 $k$ 为偶数时证明整除性。证明中写成 $k=2m$，其中 $m\ge1$，完整使用了偶数条件。

2. 偶数条件使用位置。
   关键处为

   $$\left((-1)^r\zeta^{-r(r+1)/2}\right)^{2m}.$$

   因指数 $2m$ 为偶数，符号 $(-1)^r$ 被消去。若 $k$ 为奇数，这一步不成立；事实上命题对奇数 $k$ 一般也不成立，例如

   $$n=2,\quad k=3,\qquad 1^3+2^3+1^3=10\not\equiv0\pmod3.$$

   因而偶数条件确实不可随意删去。

3. 指数均为整数。
   因 $k=2m$，

   $$i+m i(i+1)$$

   是非负整数，所以 $F(q)$ 确为 $\mathbb Z[q]$ 中的多项式。

4. 单位根处的计算。
   对 $i=bd+r$，

   $$i(i+1)-r(r+1) =(i-r)(i+r+1)$$

   是 $d$ 的倍数，因此相应的 $\zeta$ 次幂确实可约去；剩余项为 $\zeta^r$。

5. 指标范围。
   因 $n=ad-1$，每个

   $$0\le i\le ad-1$$

   唯一写成

   $$i=bd+r,\qquad 0\le b\le a-1,\quad 0\le r\le d-1,$$

   所以将双重求和分成 $b,r$ 两层没有遗漏或重复。

6. 从单位根到多项式整除。
   $F(q)$ 在每个本原 $d$ 次单位根上为零，所以 $\Phi_d(q)\mid F(q)$；再利用

   $$[n+1]_q = \prod_{\substack{d\mid n+1\\d>1}}\Phi_d(q)$$

   及圆分多项式两两互素，即得 $[n+1]_q\mid F(q)$。

7. 最后取 $q=1$。
   Gaussian 二项式满足

   $$\begin{bmatrix}n\\i\end{bmatrix}_1=\binom ni,$$

   且

   $$[n+1]_1=n+1,$$

   所以最后确切得到题目要求的整数整除结论。

综上，证明中的指标、符号、单位根计算和整除推理均一致，结论完整。

核心思路总结

最关键的构造是把原来的整数和提升为

$$F(q)= \sum_{i=0}^n q^{\,i+\frac{k}{2}i(i+1)} \begin{bmatrix}n\\i\end{bmatrix}_q^k.$$

这个看似特殊的指数

$$i+\frac{k}{2}i(i+1)$$

是专门为了在本原 $d$ 次单位根 $\zeta$ 处抵消

$$\begin{bmatrix}d-1\\r\end{bmatrix}_{\zeta}^k$$

产生的二次相位。由于

$$\begin{bmatrix}d-1\\r\end{bmatrix}_{\zeta} = (-1)^r\zeta^{-r(r+1)/2},$$

而 $k$ 为偶数，符号消失，整个被加项最终恰好化成 $\zeta^r$。

于是求和中出现完整的几何级数

$$1+\zeta+\cdots+\zeta^{d-1}=0,$$

从而得到每个 $\Phi_d(q)$ 都整除 $F(q)$，最终得到

$$[n+1]_q\mid F(q).$$

令 $q=1$ 就回到原命题。

核心工具是：

• Gaussian 二项式系数；
• $q$-Lucas 定理在单位根处的特例；
• 圆分多项式分解$$[n+1]_q=\prod_{\substack{d\mid n+1\\d>1}}\Phi_d(q);$$
• 单位根的几何级数求和。

其中最有创造性的部分，是选择恰当的 $q$-权

$$q^{\,i+\frac{k}{2}i(i+1)}$$

把单位根处的二次相位完全消掉。

参考资料

在独立推导过程中检索到 Ji-Cai Liu 与 Xue-Ting Jiang 的论文 On the divisibility of sums of even powers of q-binomial coefficients（arXiv:2110.09906），其中研究了更强的相关 $q$-整除问题；该资料提示了从 $q$-二项式整除角度处理本题的方向。

链接：https://arxiv.org/abs/2110.09906

本文解答中的具体多项式 $F(q)$、单位根计算以及上述证明均在此基础上独立整理推导，未直接调用论文中的主要定理。