数论讲课补题记录

P10

题面

给定整数 \(k \geqslant 2\). 令 \(a_1=1\), 对每个整数 \(n \geqslant 2\), 令 \(a_n\) 为大于 \(a_{n-1}\) 且满足下式

\[x=1+\sum_{i=1}^{n-1}\left\lfloor\sqrt[k]{\frac{x}{a_i}}\right\rfloor \]

的最小的 \(x\). 证明: 每个素数都在上述数列 \(a_1, a_2, \cdots\) 中出现.

P11

题面

求所有正整数组 \((a, b, c)\) 使得

\[ab-c, \quad bc-a, \quad ca-b \]

都是 \(2\) 的方幂.

P12

题面

求所有三元组 \((p, x, y)\), 满足 \(p\) 是素数, \(x, y\) 是正整数, 且 \(x^{p-1}+y\) 与 \(x+y^{p-1}\) 都是 \(p\) 的方幂.

P13

这题老师没时间讲了。补一个我自己的做法。用时 \(20\) min。

题面

设正整数 \(a\) 不是完全平方数. 令 \(A\) 为由所有形如 \(k=\frac{x^2-a}{x^2-y^2}(x, y \in Z, x>\sqrt{a})\) 的正整数 \(k\) 所构成的集合. 令 \(B\) 为由所有形如 \(k=\frac{x^2-a}{x^2-y^2}(x, y \in Z, 0 \leqslant x<\sqrt{a})\) 的正整数 \(k\) 所构成的集合. 证明: \(A=B\).

解答

一个丢番图方程，初看没有思路，考虑先手玩一下。

\(k=\frac{x^2-a}{x^2-y^2}\)，我们可以将其变形为：

\[k(x^2 - y^2) = x^2 - a \]

\[kx^2 - ky^2 = x^2 - a \]

\[ky^2 - (k-1)x^2 = a \quad \cdots\cdots (*) \]

题目要求的是正整数 \(k\) 的集合。
首先考虑 \(k=1\) 的情况。若 \(k=1\)，代入方程 \((*)\) 得到 \(y^2 = a\)。因为题目已知 \(a\) 不是完全平方数，所以 \(y\) 不可能有整数解。因此 \(k=1\) 既不属于 \(A\) 也不属于 \(B\)。

所以接下来的分析力我们默认 \(k \geqslant 2\)。

同时，对于任意满足 \((*)\) 式的整数解 \((x, y)\)，由于 \(a\) 不是完全平方数，不可能有 \(x^2 = y^2\) （否则 \(a = ky^2 - (k-1)y^2 = y^2\)，矛盾）。因此分母 \(x^2 - y^2 \neq 0\) 总是成立的，我们不用担心分母为零的问题。
另外，由于方程式中 \(x\) 和 \(y\) 均以平方的形式出现，如果 \((x, y)\) 是解，那么 \((\pm x, \pm y)\) 也是解。

我们下面默认 \(x \geqslant 0\) 且 \(y > 0\)

为了在集合 \(A\) 和 \(B\) 之间建立联系，可以自然地想到构造一组变换。注意到常数 \(k(k-1)\)，考虑如下的变换：
对于满足 \((*)\) 式的解 \((x, y)\)，定义新的数偶 \((x', y')\) 为：

\[\begin{cases} x' = (2k-1)x + 2ky \\ y' = 2(k-1)x + (2k-1)y \end{cases} \]

及其逆变换构造的新数偶 \((x'', y'')\) 为：

\[\begin{cases} x'' = (2k-1)x - 2ky \\ y'' = -2(k-1)x + (2k-1)y \end{cases} \]

我们验证这两个新数偶是否也满足原方程 \((*)\)。以 \((x', y')\) 为例：

\[k(y')^2 - (k-1)(x')^2 \]

\[= k[2(k-1)x + (2k-1)y]^2 - (k-1)[(2k-1)x + 2ky]^2 \]

展开并合并同类项，交叉项 \(xy\) 的系数为：

\[k \cdot 2 \cdot 2(k-1)(2k-1) - (k-1) \cdot 2 \cdot (2k-1)2k = 0 \]

\(x^2\) 的系数为：

\[4k(k-1)^2 - (k-1)(2k-1)^2 = (k-1)[4k^2 - 4k - (4k^2 - 4k + 1)] = -(k-1) \]

\(y^2\) 的系数为：

\[k(2k-1)^2 - (k-1)4k^2 = k[4k^2 - 4k + 1 - (4k^2 - 4k)] = k \]

所以 \(k(y')^2 - (k-1)(x')^2 = ky^2 - (k-1)x^2 = a\)。
同理可证 \((x'', y'')\) 也满足方程 \((*)\)。
这意味着，只要我们找到一个解，就可以通过这两个变换生成一串解。

然后感觉差不多就有思路了。

证明 \(A \subseteq B\)

假设 \(k \in A\)，那么方程 \((*)\) 存在整数解 \((x_0, y_0)\)，满足 \(x_0 > \sqrt{a}\) 且 \(y_0 > 0\)。
我们通过逆变换构造一个解的序列。定义：

\[x_{n+1} = |(2k-1)x_n - 2ky_n| \]

\[y_{n+1} = -2(k-1)x_n + (2k-1)y_n \]

由于方程只包含平方项，\((x_{n+1}, y_{n+1})\) 依然是方程 \((*)\) 的解。

Lemma 1：只要 \(x_n \geqslant 0, y_n > 0\)，就有 \(y_{n+1} > 0\)。

我们要证 \((2k-1)y_n > 2(k-1)x_n\)。因为两边非负，等价于证明其平方不等式：

\[(2k-1)^2 y_n^2 > 4(k-1)^2 x_n^2 \]

将 \(y_n^2 = \frac{a + (k-1)x_n^2}{k}\) 代入左边：

\[(2k-1)^2 \frac{a + (k-1)x_n^2}{k} = \frac{(2k-1)^2 a}{k} + \frac{(4k^2 - 4k + 1)(k-1)x_n^2}{k} \]

\[= \frac{(2k-1)^2 a}{k} + \frac{4k(k-1)^2 + (k-1)}{k} x_n^2 = \frac{(2k-1)^2 a}{k} + 4(k-1)^2 x_n^2 + \frac{k-1}{k} x_n^2 \]

显然，由于 \(a>0, k \geqslant 2\)，该式严格大于 \(4(k-1)^2 x_n^2\)。断言 1 成立。这意味着我们可以不断迭代而不用担心 \(y\) 变成负数。

Lemma2：只要 \(x_n > \sqrt{a}\)，就有 \(x_{n+1} < x_n\)。

我们需要证明 \(-x_n < (2k-1)x_n - 2ky_n < x_n\)。
右边不等式：\((2k-1)x_n - 2ky_n < x_n \iff 2(k-1)x_n < 2ky_n \iff (k-1)x_n < ky_n\)。
因为两边均为正，平方得：

\[(k-1)^2 x_n^2 < k^2 y_n^2 = k[a + (k-1)x_n^2] = ka + k(k-1)x_n^2 \]

\[(k^2 - 2k + 1)x_n^2 < ka + (k^2 - k)x_n^2 \iff (1-k)x_n^2 < ka \]

因为 \(k \geqslant 2\)，左边 \(\leqslant 0\)，右边 \(>0\)，此不等式永远成立。
左边不等式：\(-x_n < (2k-1)x_n - 2ky_n \iff 2ky_n < 2kx_n \iff y_n < x_n\)。
平方得：

\[y_n^2 < x_n^2 \iff \frac{a + (k-1)x_n^2}{k} < x_n^2 \iff a + (k-1)x_n^2 < kx_n^2 \iff a < x_n^2 \iff x_n > \sqrt{a} \]

这正是我们的前提条件。所以断言 2 成立。

由 Lemma 2 可知，只要 \(x_n > \sqrt{a}\)，非负整数序列 \(\{x_n\}\) 就是严格递减的。由于非负整数不可能无限严格递减，所以序列必然会在某一步终止满足条件，即存在某个 \(m\)，使得 \(x_m \leqslant \sqrt{a}\)。
因为 \(a\) 不是完全平方数，所以 \(x_m \neq \sqrt{a}\)，故 \(0 \leqslant x_m < \sqrt{a}\)。
此时 \((x_m, y_m)\) 是方程的一组解，且满足 \(0 \leqslant x_m < \sqrt{a}\)，故 \(k \in B\)。
这就证明了 \(A \subseteq B\)。

证明 \(B \subseteq A\)

假设 \(k \in B\)，那么方程 \((*)\) 存在整数解 \((X_0, Y_0)\)，满足 \(0 \leqslant X_0 < \sqrt{a}\)。同样我们取 \(Y_0 > 0\)。
我们通过正向变换构造解的序列。定义：

\[X_{n+1} = (2k-1)X_n + 2kY_n \]

\[Y_{n+1} = 2(k-1)X_n + (2k-1)Y_n \]

考察序列 \(X_n\) 的单调性：

\[X_{n+1} - X_n = 2(k-1)X_n + 2kY_n \]

因为 \(k \geqslant 2, X_n \geqslant 0, Y_n \geqslant 1\)，所以 \(X_{n+1} - X_n \geqslant 2k \cdot 1 > 0\)。
这说明 \(\{X_n\}\) 是一个严格递增的整数序列。
既然它严格递增并趋向于无穷大，那么必然存在某个下标 \(m\)，使得 \(X_m > \sqrt{a}\)。
由于 \((X_m, Y_m)\) 也是方程 \((*)\) 的解，我们找到了满足 \(x > \sqrt{a}\) 的解，因此 \(k \in A\)。
这就证明了 \(B \subseteq A\)。

证毕。