数论研究的拓展：同余式当中任意次二项方程的解的情况

定义：

\[\begin{align*} f_n(m)=\begin{cases} 1 \,\,\,\,\,\,\text{ if } (模 m的完系)^n也是模m的完系 \\ 0 \,\,\,\,\,\,\text{ otherwise } \end{cases} \end{align*}\]

仿照前文可得如下定理，证明略：

theorem 对于任意素数 $p$，对于任意整数 $a>1$，$f_n(p^a)=0$

theorem $m_1,m_2,…,m_r$ 是两两互素的正整数，$m=m_1m_2…m_r$ ，则 $f_n(m)=f_n(m_1)f_n(m_2)…f_n(m_r)$，即 $f_n(m)$ 是积性函数

theorem $m_1,m_2,…,m_r$ 是两两互素的正整数，$m=m_1m_2…m_r$ ，对于特定非零整数 $a$，令 $g_n(m)$ 等于 $x^n \equiv a \pmod{m}$ 的解的个数，则 $g_n(m)=g_n(m_1)g_n(m_2)…g_n(m_r)$，即 $g_n(m)$ 是积性函数。

theorem 对于任意素数 $n$，对于任意素数p满足 $f_n(p)=0$，对于任意非零整数 $a$，$x^n \equiv a \pmod{p}$ 有 $n$ 个或0个不同余的解，且有 $n$ 整除 $p-1$，$x^n$ 模p下共有 $\frac{p-1}n$ 个不同的值。对于任意素数n，对于任意素数p满足 $f_n(p)=1$，对于任意非零整数 $a$， $x^n \equiv a \pmod{p}$ 总有唯一解。

根据拉格朗日定理可知原式至多有 $n$ 个解。

设 $x^n \equiv a \pmod{p}$ 存在解且有小于 $n$ 个解。 设 $x$ 的一个解为 $x \equiv t \pmod{p}$。 则对于任意整数 $c$，

\[(t^c)^n \equiv (t^n)^c \equiv 1 \pmod{p}\]

则对于任意整数 $c$， $t^c$ 均为原方程的解。 取 $1\le c \le n$ 的 $n$ 个解，由抽屉原理，存在重复解，即存在 $t^m \equiv t^q \pmod{p}$（其中 $1 \leq q < m \leq n$）。 此时 $t^{m-q} \equiv 1 \pmod{p}$，则序列 $t, \dots, t^n \pmod{p}$ 的周期为 $m-q$，因此 $m-q$ 整除 $n$ 。因为 $n$ 为素数，$m-q=1$ 。 由此可得 $t \equiv 1 \pmod{p}$。因此，方程 $x^n \equiv 1 \pmod{p}$ 有 $n$ 个解或唯一解 $x \equiv 1 \pmod{p}$。

考虑方程 $x^n \equiv a^n \pmod{p}$。若 $x^n \equiv 1 \, (\text{mod } p)$ 有 $d$ 个解，则 $x^n \equiv a^n$ 也有 $d$ 个解。这是因为后者的解与前者的解的 $a$ 倍一一对应。令 $a$ 遍历模 $p$ 的完全剩余系可得，对于 $a^n$ 可取到的值，$x^n$ 总有 $d$ 个解。而对于 $a^n$ 取不到的值，$x$ 总无解。当 $f_n(p)=1$，即 (模 $p$ 的完系)$^n$ 也是模 $p$ 的完系时，$x$ 总有唯一解。当 $f_n(p)=0$ 时，一定有 $a^n$ 取不到的值，此时 $x$ 无解。当同余式右侧取遍完系时，$x$ 的解的个数之和一定等于 $n$，因此，$d$ 一定大于 1，由上文的结论可得 $d=n$。$\Box$

由此可得：

corollary 存在 $a$ 使 $x^n \equiv a \pmod{p}$ 无解 $\iff$ $f_n(p) = 0$

我们还可以得到一个有意思的结论。取 $n>p$，显然不能有 $n$ 个解，于是有：

corollary 素数 $n>p$ 时，$f_n(p)=1$ 。

theorem 若 $n_1 \equiv n_2 \pmod{p-1}$，则$f_{n_1}(p)=f_{n_2}(p)$ 。$f_{n}(p)$ 关于n是周期为 $p-1$ 的周期函数。

由费马小定理易得。

theorem $f_n(p)=1\iff \gcd(n,p-1)=1$

proof 1 先考虑当n为素数时。充分性是显然的，无论怎样都有$\gcd(n,p-1)=1$

再证必要性。

lemma $km+h$ 的等差数列中，$k=1,2,…$，若 $\gcd(m,h)=1$，则其中必存在素数大于m+1

由迪利克雷定理可直接得出。$\Box$

可以证明此引理与迪利克雷定理是等价的。若迪利克雷定理不成立，设 $km+h$ 中最大素数为 $p$，构造数列 $kpm+m+p$ ，其所有元素大于 $p$，则其中无素数，矛盾。更一般地，不要求素数大于m+1也是成立的。

对于等差数列 $k(p-1)+n$，必存在素数 $p_1$ 大于p，$f_{p_1}(p)=1$，则 $f_{n}(p)=1$

由此易证n为合数时定理成立。$\Box$

proof 1 用到迪利克雷定理导致证明变得很臃肿，因此在这里用另外的方法给出证明。

proof 2 当 $n<p$ 且 $n$ 为素数时，相当于证明 $f_n(p)=0 \iff p \equiv 1 \pmod{n}$：

$f_n(p)=0 \Rightarrow p \equiv 1 \pmod{n}$ 由上文命题可直接得出。

若 $p \equiv 1 \pmod{n}$ ，设 $p - 1 = \alpha n$， $x^n \equiv a \pmod{p}$，则 $x^{\frac{p-1}{\alpha}} \equiv a \pmod{p}$， $x^{p-1} \equiv a^\alpha \pmod{p}$ , $a^{\alpha} \equiv 1\pmod{p}$。根据拉格朗日定理可知a至多有 $\alpha$ 个解。而 $p-1>\alpha$, 则存在 $a$ 使 $x^n \equiv a \pmod{p}$ 无解 ，因此 $f_n(p) = 0$

由此易证n为合数时和 $n\ge p$ 时定理成立。$\Box$

此时我们惊奇地发现， $f$ 竟然是迪利克雷主特征！$f_n(p)=\chi_1(n)\pmod {p-1}$。这是否暗示着它与迪利克雷定理有某种联系？

对于角标 $n$ ，我们可以从两个方向得到证明：

theorem $n_1,n_2,…,n_r$是正整数，$n=n_1n_2…n_r$ ，则 $f_n(m)=f_{n_1}(m)f_{n_2}(m)…f_{n_r}(m)$，即 $f_n(m)$ 关于n是完全积性函数。

proof 1 从定义出发。令 $A=$ 模 $m$ 的完系，$A^n=\{\hat x^n|\hat x\in A\}$。 若 $f_{n_1}(m)=f_{n_2}(m)=1$，则 $A^{n_1}=A^{n_2}=A$，则 $A^n=A^{n_1n_2}=\left(A^{n_1}\right)^{n_2}=A^{n_2}=A$，则 $f_n(m)=1$。若存在 $n_i$ 使得 $f_{n_i}(m)=0$ ，不失一般性地，设 $f_{n_1}(m)=0$ ，则 $A^{n_1}\subset A$，则 $A^n=A^{n_1n_2}=\left(A^{n_1}\right)^{n_2}\subset A^{n_2}\subseteq A$，则 $A^n\ne A$，则 $f_n(m)=0$。

proof 2 因为 $n$ 与 $m$ 互素当且仅当 $n$ 的每个因数与 $m$ 互素。因此由上文定理易证。根据迪利克雷特征的性质也可得。$\Box$

由上述定理，我们可以得到f有关的表现。$f_n(p^a)=0$， $f_n(m)$ 是积性函数， $f_n(m)$ 关于 $n$ 是完全积性函数， $f_n(p)$ 是周期为 $p-1$ 的周期函数。当 $n<p$ 且 $n$ 为素数时， $f_n(p)=0 \iff p \equiv 1 \pmod{n} \iff x^n \equiv a \pmod{p} 有n个或0个不同余的解$。$n>p\Rightarrow f_n(p)=1\iff \gcd(n,p-1)=1 \iff x^n \equiv a \pmod{p} 有1个不同余的解$