【初等数论】指数、原根与不定方程

1、指数

现在我们就开始为剩余系建立“坐标”，完全剩余系是连续的，剩余类本身就是很好的坐标，所以这里我们只需讨论既约剩余系。前面已经知道 $(a,m)=1$ 时，总存 d 在使得 $a^d\equiv 1\pmod{m}$ ，满足条件的最小的 $d_0=\delta_m(a)$ 称为a对模m的阶或指数，也可简记为 $\delta(a)$ ，我们可以看出来当模 m 确定时， $d_0$ 由 a 唯一的确定，d 是 a 的函数。为了得到更进一步的结论，我们先整理一下指数的一些简单性质如下：
（1）若 $a^d\equiv 1\pmod{m}$ ，则 $\delta_m(a)\mid d$ 。从而有若 $a^h\equiv a^d\pmod{m}$ ，则 $h\equiv d\pmod{m}$ ；
（2） $\delta_m(a)|\varphi(m)$ ； $\delta_m(a^{-1})=\delta_m(a)$ 。

我们来继续研究指数的性质，首先考虑 $\delta^*=\delta_m(a^n)$ ，由 $a^{n\delta^*}\equiv 1\pmod{m}$ 知 $\delta_m(a)\mid n\delta^*$ ，故可容易有公式（1），你可以简单停留思考下，有了（1）式后我们就可以从 $\delta_m(a)$ 求 $\delta_m(a^n)$ 了。其次由定义显然有：若 $n∣m$ ，则 $\delta_n(a)\mid \delta_m(a)$ 。所以对互质分解 $m=m_1m_2\cdots m_n$ (分解模数)，总有 $\delta_{m_k}(a)\mid \delta_m(a)$ ，再根据模的性质就有公式（2）。再进一步，对任意的a1,a2,⋯,an，考虑方程组 $x\equiv a_k\pmod{m_k}$ 的唯一解 a（剩余定理），显然有 $\delta_{m_k}(a)=\delta_{m_k}(a_k)$ ，再根据公式（2）可得 a 满足公式（3）。
$\delta_m(a^n)=\dfrac{\delta_m(a)}{(\delta_m(a),n)}\tag{1}$
$\delta_m(a)=[\delta_{m_1}(a),\delta_{m_2}(a),\cdots,\delta_{m_n}(a)]\tag{2}$
$\delta_m(a)=[\delta_{m_1}(a_1),\delta_{m_2}(a_2),\cdots,\delta_{m_n}(a_n)]\tag{3}$
　
　再来研究 $\delta_m(a),a=a_1a_2\cdots a_n$ （分解底数），令 $\beta=[\delta(a_1),\cdots,\delta(a_n)]$ ，则显然有 $\delta(a)\mid \beta$ （提示：可以结合(1)式进行思考）。先看各个 $\delta(a_k)$ 互素的情况，这时 $\beta=\delta(a_1)\delta(a_2)\cdots\delta(a_n)$ ，令 $\beta_k=\dfrac{\beta}{\delta(a_k)}$ 。因为 $1\equiv a^{\delta(a)\beta_k}\equiv (a_k \times a_{!k})^{\delta(a)\beta_k}\equiv a_k^{\delta(a)\beta_k}(a_{!k}^{\beta_k})^{\delta(a)}\equiv a_k^{\delta(a)\beta_k}\pmod{m}$ ，又因为 $\delta(a_k)$ 互素。故 $\delta(a_k)\mid \delta(a)$ ，从而有公式（4）。如果 $\delta(a_k)$ 不互素，一般并没有 $\delta(a)=\beta$ 。但反过来，对任意的 $a_1,a_2,\cdots,a_n$ ，利用公式（1）和（4）构造满足公式（5）的 a 还是很容易的。
　 $\delta_m(a)=\delta_m(a_1)\delta_m(a_2)\cdots\delta_m(a_n)\tag{4}$
$\delta_m(a)=[\delta_m(a_1),\delta_m(a_2),\cdots,\delta_m(a_n)]\tag{5}$
　
　指数在研究循环小数时有个有趣的结论。对既约分数 $\dfrac{a}{b}$ ，如果有 $b=2^m\cdot 5^n\cdot k$ ，则 $\dfrac{a}{b}$ 是循环小数的充要条件是 $(10,k)=1,k>1$ 。如果 $\delta_k(10)=c$ ，则最小循环周期为 c，并且小数点后的非循环数长度为 $max(m,n)$ 。特别地，如果 $(10,b)=1$ ，则 $\dfrac{a}{b}$ 是纯循环小数。证明过程不是难，可以作为练习，提示：使用关系式 $10^c\equiv 1\pmod{k}$

2、原根

由指数的性质（2）可知 $a,a^2,\cdots,a^{\delta_m(a)}$ 是 $\delta_m(a)$ 个不同的数，特别地当 $\delta_m(a)=\varphi(m)$ 时，它们遍历 m 的既约剩余系。这种关系使得既约剩余系变得特别简单，我们也由此找到了合适的坐标。为此，当 $\delta_m(g)=\varphi(m)$ 时称 g称为模 m的原根，它便是既约剩余系的单位元，负责将剩余系串成一个线性空间。先来思考如下几个问题：
　
• 如果 $(n,\varphi(m))=1$ ，则 $x$ 遍历m的既约剩余系时， $x^n$ 也遍历既约剩余系;
• 若 $q\equiv 1\pmod{4},p=2q+1$ ，或 $q\equiv 1\pmod{2},p=4q+1$ ，都有 2 是 $p$ 的原根；
• $a^n−b^n$ 的素因子有形式 $kn+1$ 或 $a^m−b^m,(m|n)$ 。

我们自然会有问题：什么样的模数有原根？有多少个原根？如何判定？前面已经知道 $\delta(a)\mid \beta$ ，而除了 $1,2,4,p^e,2p^e$ 这5种情况外（p为奇素数），容易证明其它都有 $\beta<\varphi(m)$ ，它们肯定没有原根，因为当模数 m 不属于上面这五种情况时，必有 m 为 $2^a (a \geq3),$ 或 $2^ap_1^{a_1}···p_r^{a_r} (a \geq 2, r \geq 1)$ 或 $2^ap_1^{a_1}···p_r^{a_r} (a \geq 0, r \geq 2)$ ，而这里的 $\beta$ 由 $[2^{c_0}, \phi(p_1^{a_1}),···,\phi(p_r^{a_r})]$ 给出。这里的 $c_0$ 由下列式子给出：
　 $c_0 = \left\{\begin{matrix} & \ 0, \qquad a_0 = 0, 1;\\ & 1, \qquad a_0 = 2;\\ & a_0 - 2, \quad a_0 \geq3. \end{matrix}\right.$ 又因为我们有式子， $\delta_{2^l}(a) | \ 2^{l-2}, l \geq 3$ 故可以得到 $\beta<\varphi(m)$ ，可自行验证。

下面就需要论证那5种情况是否有原根，直接验算可知1,2,4有原根。对于模p的情况，由公式（5）知存在g使得 $\delta(g)=[\delta(1)\delta(2)\cdots\delta(p-1)]$ ，首先当然有 $\delta(g)|p-1$ 。另外因为 $x^{\delta(g)}-1\equiv 0\pmod{p}$ 有全解，则 $p-1|\delta(g)$ 。从而 $\delta(g)=p-1$ ，所以p有原根 g。

由 $g^d\equiv 1\pmod{p^e}$ 和 $g^d\equiv 1\pmod{2p^e}$ 的等价性，并且 $\varphi(p^e)=\varphi(2p^e)$ ，可知 $p^e$ 和 $2p^e$ 有相同的原根，这样一来我们就只需要讨论模 $p^e$ 是否有原根了。当g是 $p^n$ 原根时，因为 $p^n\mid p^{n+1}$ ，故 $\delta_{p^{n+1}}(g)$ 为 $φ(p^n)$ 或 $φ(p^n+1)$ 。要想g也是 $p^n+1$ 的原根，必须 $\delta_{p^{n+1}}(g)=\varphi(p^{n+1})$ ，即满足式子（6）。而如果该条件满足，用归纳法可以验算得它对一切 $g^{\varphi(p^e)},(e\geqslant n)$ 都满足，即g是所有 $p^e$ 的原根。
$g^{\varphi(p^n)}=1+r(n)p^n,\quad p\nmid r(n)\tag{6}$
　
　现在只要能证明以上条件对 $n=1$ 成立（即 $g^{p-1}=1+rp,p\nmid r$ ），我们就找到了所有模 $p^e$ 的原根，研究证明了 $p^e$ 原根的存在性。对模 p 的原根 g，考察 $g_k=g+kp,k=0,1,\cdots,p-1$ 和式子（7）中的变形。 $r+(p-1)g^{p-2}k$ 中有且仅一个是 p 的倍数，取其它任何一个值都能得到了满足条件的原根，条件得证。
$g_k^{p-1}\equiv g^{p-1}+(p-1)g^{p-2}pk\equiv 1+p(r+(p-1)g^{p-2}k)\pmod{p}\tag{7}$

至此我们已经证明了原根存在的充要条件是模为 $1,2,4,p^e,2p^e$ 之一，但如果想要找出原根，目前还没有很简单的方法。一般只能逐个尝试每个数，然而利用公式（5）的构造法是可以加快计算的，比如如果已经知道 $\delta_{41}(2)=20$ 和 $\delta_{41}(3)=8$ ，因为 $[20,8]=40$ ，故素因子 2,3 必定也是模 41 的原根的素因子，经过尝试后得 $2^4\cdot 3\equiv 7\pmod{41}$ 是 41 的原根。

如果原根存在，选定一个原根 g 后，它的幂次遍历整个既约剩余系。如果 $g^k\equiv a\pmod{m}$ ，称 k 为a 的指标，记作 $\gamma_{m,g}(a)$ ，或简记为 $\gamma_g(a)$ 和 $\gamma(a)$ 。指标将既约剩余系变成了一个完全剩余系，使其结构由分散的变为线性的，由此可以更好地研究它的性质。以下为原根的一些性质，其中性质（3）中蕴含了指数为 $d\mid \varphi(m)$ 的数有 φ(d)个，它们是 $g^{\frac{\varphi(m)}{d}k},(k,d)=1$ 。特别地共有 $\varphi(\varphi(m))$ 个原根，它们是 $g^k,(k,\varphi(m))=1$ 。

(1) $\gamma_{m,g}(ab)\equiv\gamma_{m,g}(a)+\gamma_{m,g}(b)\pmod{\varphi(m)}$
(2) $\gamma_{g_1}(a)\equiv\gamma_{g_1}(g_2)\gamma_{g_2}(a)\pmod{\varphi(m)}$ ,特别地有 $\gamma_{g_1}(g_2)\gamma_{g_2}(g_1)\equiv 1\pmod{\varphi(m)}$
(3) $\delta_m(a)=\dfrac{\varphi(m)}{(\gamma_{m,g}(a),\varphi(m))}$

我们一直想把指数当做即约剩余系的“坐标”，现在就来着手做这件事。一般的，将模m进行素数分解 $2^{e_0}\cdot p_1^{e_1}\cdot\cdots p_n^{e_n}$ ，其既约剩余系的每个数 a 在各个维度都有一个值 $a_k$ 。对 $p^{e_k}_k，前面的证明保证了它有原根$ g_k $和$ \gamma_k=\gamma_{p_k^{e_k},g_k}(a_k)$就可以看做a 在第 k 维的坐标。

但对于 $2^{e_0}$ ，除 $e_0<3$ 外是没有原根的， $e_0\geqslant 3$ 时怎么建立坐标？通过归纳法你可以证明 $\delta_{2^e}(5)=2^{e-2}$ ，并且容易知道 $\pm 5^0,\pm 5^1,\cdots,\pm 5^{2^{e-2}-1}$ 是它的一个既约剩余系。这样任何既约数都有唯一表达式（8）， $\gamma_{-1},\gamma_0$ 就可以看做它的坐标。完整的就得到任何既约数的指标表达式（9）和（10）（（10）中 $\tilde{g}_k^{\gamma_k}$ 的是（9）中的 $γ_k$ 取1、其它取0得来），使用（10）来证明威尔逊定理就简单多了。
$(-1)^{\gamma_{-1}}5^{\gamma_0},\quad (0\leqslant \gamma_{-1}<2,\:0\leqslant \gamma_0<2^{e-2})\tag{8}$
$a\equiv M_0^{-1}M_0(-1)^{\gamma_{-1}}5^{\gamma_0}+M_1^{-1}M_1g_1^{\gamma_1}+\cdots+M_n^{-1}M_ng_n^{\gamma_n}\pmod{m}\tag{9}$
$a\equiv \tilde{g}_{-1}^{\gamma_{-1}}\cdot\tilde{g}_0^{\gamma_0}\cdot\tilde{g}_1^{\gamma_1}\cdots\tilde{g}_n^{\gamma_n}\pmod{m}\tag{10}$

3、二项同余方程

最后再来看同余方程（11）它一般称为二项同余方程。如果方程有解，称a为m的n次剩余，否则称为n次非剩余。对m进行素数分解 $2^{e_0}\cdot p_1^{e_1}\cdot\cdots p_n^{e_n}$ 后，方程可以化为一个方程组，我们只需分别讨论这些方程即可。
$x^n\equiv a\pmod{m}\tag{11}$
　　
　　模 $p^e$ （p为奇素数）有原根 g，用它来分析二项方程会很简单（下面的讨论针对有原根的模m都成立）。将原根带入原方程，得到式子（12）的左侧，它显然对应于右侧的一元一次同余方程。可以先回顾一下一次方程 $ax\equiv b\pmod{m}$ 的特点，令 $d=(a,m)$ ，则 $d\mid b$ ，且方程解的周期为 $\dfrac{m}{d}$ ，请先在脑子想象一下它们的布局。回到原方程，令 $d=(n,\varphi(m))$ ，则方程有解的充要条件是 $d|\gamma(a)$ ，且共有 $\dfrac{\varphi(m)}{d}$ 个n次剩余。方程的解有d个，它们的周期是 $\dfrac{\varphi(m)}{d}$ 。
$(g^y)^n\equiv g^{\gamma(a)}\pmod{m}\:\Leftrightarrow\:ny\equiv \gamma_{m,g}(a)\pmod{\varphi(m)}\tag{12}$
　　
　　现在来把条件 $d|\gamma(a)$ 转化为与a直接相关的。因为 $a=g^\gamma(a)$ ，使用公式（1）直接有式子（13）。结合条件d|γ(a)，显然有 $\delta(a)|\dfrac{\varphi(m)}{d}$ ，它又等价于公式（14）。这就是方程有解的充要条件，明显二次剩余的判定条件只是它的特例。
$\varphi(m)=(\varphi(m),\gamma(a))\delta_m(a)\tag{13}$
$a^{\frac{\varphi(m)}{(n,\varphi(m))}}\equiv 1\pmod{m}\tag{14}$

对模 $m=2^e$ 的情景需要单独考虑，前面的讨论中说明了它的既约剩余系有两个独立的维度，故只需分别讨论两个维度就行了。令 $a=(-1)^{\gamma_{-1}}5^{\gamma_0},d=(n,2^{e-2})$ ，可知方程有解的充要条件是 $(n,2)\mid\gamma_{-1}$ 且 $d\mid\gamma_0$ ，方程解的个数为 $(n,2)d$ 。展开说就是，当 $2\nmid n$ 时有且仅有1解，既约剩余系的每个值都是n次剩余。当 $2\mid n$ 时有解的充要条件是 $a=5^{\gamma_0}$ 且 $d\mid\gamma_0$ ，并且有2d个解，共有 $\dfrac{2^{e-2}}{d}$ 个数是n次剩余。

下面把 $2∣n$ 有解的充要条件转化为与 a 相关的，首先易知必有形式 $d=2^{\lambda},(\lambda\geqslant 1)$ 。因为 $\delta_{2^{\lambda+2}}(5)=2^{\lambda}=d$ ，我们的条件 $d\mid\gamma_0$ 其实等价于 $\delta_{2^{\lambda+2}}(5)=2^{\lambda}=d$ ，这就得到充要条件为公式（15）。当然你也可以得到与 $p^e$ 类似的式子，但因为不如上式简洁，这里就不赘述了。
$a\equiv 1\pmod{2^{\lambda+2}},\quad2^{\lambda}=(n,2^{e-2}),\:(\lambda\geqslant 1)\tag{15}$

不定方程

经过前面关于初等数论的基础知识的学习和理解，这里我们就可以开始不定方程的简单论述。不定方程是初等数论向前发展直接的驱动力之一。不定方程又叫丢潘图方程，它们以整数（或有理数）为变量和参数，而且有两个以上的未知数，多以多项式形式出现。不定方程既是数论的应用，也是数论理论形成的来源，对不定方程的思考可以将前面学习过的知识和内容串起来。

4、一次不定方程

最简单的不定方程就是一次方程（1），它表现为一个多元线性方程。如果你还记得前面最大公约数的线性组合定义，就容易得到方程有整数解的充要条件是 $(a_1,a_2,\cdots,a_n)\mid c$ 。多元方程的第一步往往是降元，令 $d=(a_2,\cdots,a_n),a'_k=\dfrac{a_k}{d}$ ，则方程等价于一次方程组（2）（想想为什么？以及为什么要先抽出最大公约数？）。如果对（2）式一直做类似处理，就会得到多个二元一次方程，这样就把问题集中到了简单的情景。
$a_1x_1+a_2x_2+\cdots+a_nx_n=c\tag{1}$
$\begin{cases}\:a_1x_1+dy=c\\\:a'_2x_2+\cdots+a'_nx_n=y\end{cases}\tag{2}$

而对于二元一次方程 $ax+by=c$ ，它有明显的几何意义，方程的解就是直线方程上的整数点，所有对其讨论都可以从图形中找出。容易看出，如果已知一个解 $x_0,y_0$ ，则方程的全部解为公式（3）。至于如何求得一个特解，一般还是用辗转相除法，对于一些简单的情况，也可以直接尝试各种值。
$\begin{cases}\:x=x_0+\dfrac{b}{(a,b)}k\\\:y=y_0-\dfrac{a}{(a,b)}k\end{cases},\:k=0,\pm 1,\pm 2,\cdots\tag{3}$

5、商高方程及其扩展

5.1 商高方程

勾股定理 $x^2+y^2=z^2$ 大家都熟悉，有一个自然的问题是：如何求它的所有解？这个问题一般叫商高方程或毕达哥拉斯方程。容易证明当 $(x,y)=1$ 时方程的解两两互素，如果再限定解为正数，这样的解叫本原解。方程的解要么是平凡解 (0,0,0)，要么是本原解的倍数，因此我们只需专注于找到所有本原解。

另外，因为素数的平方只能是 $4k+1$ 的形式，可推得 x,y 必定是一奇一偶，下面就假设 y 为偶数，原方程整理为式子（4）。容易证明 $(\dfrac{z+a}{2},\dfrac{z-a}{2})=1$ （这个性质以后会经常用），故可设 $\dfrac{z+a}{2}=r^2$ 和 $\dfrac{z-a}{2}=s^2$ ，其中 $r>s>0,(r,s)=1$ 。用 $r,s$ 表示 $x,y,z$ 就得到了方程的解（5），但要注意要使得它们两两互素，还需要限定 $2\nmid r+s$ （自行证明）。
$(\dfrac{y}{2})^2=\dfrac{z+a}{2}\cdot\dfrac{z-a}{2}\tag{4}$
$\begin{cases}\:x=r^2-s^2\\\:y=2rs\\\:z=r^2+s^2\end{cases}\quad r>s>0,\:(r,s)=1,\:2\nmid r+s\tag{5}$

做一个简单的推广，形如（6）式的方程这么解？这就是著名的费马大定理（Fermat Last Theorem），当然它在1994年被彻底证明前叫费马猜想。费马发现它们并无非平凡解，并声称找到了一个绝妙的证明方法，但由于书的空白太小写不下。后来人经过了三百多年的努力，才用现代数学的方法将它攻破，大家多数倾向于认为费马的证明并不存在或并不成立。
$x^n+y^n=z^n\tag{6}$

使用类似的方法和无穷递降法，你可以证明 $x^4+y^4=z^2$ 无非平凡解，进而 $x^4+y^4=z^4$ 无非平凡解，它就是费马大定理在 $n=4$ 时的情况。下面可以思考一下如下几个问题：

• 求解 $x^2+3y^2=z^2$ 和 $2x^2-y^2=1$ ；
• 求解 $\dfrac{1}{x^2}+\dfrac{1}{y^2}=\dfrac{1}{z^2}$ ；（提示：无互质解）
• 证明 $x^n+y^n=z^{n\pm 1}$ 都有无穷多组解。（提示：构造）

5.2 $x^3+y^3=z^3$

再来看费马大定理在 $n=3$ 的情景，欧拉证明了它没有非平凡解，采用的是无穷递降法。假设 $x_0,y_0,z_0$ 是使得 $\left| xyz\right|$ 最小的一组非零解，我们的目的是构造一组值更小的解。首先当然有 $(x_0,y_0,z_0)=1$ ，并且其中仅有一个偶数，经过调整后可以使 $z_0$ 为偶数。这时可以令 $x_0+y_0=2u,x_0-y_0=2w$ ，则有 $z_0^3=2u(u^2+3w^2)$ （总结成式（7）），这个变换的重要意义在于降次。
$x_0+y_0=2u,\quad x_0-y_0=2w,\quad z_0^3=2u(u^2+3w^2)\tag{7}$

现在来研究 $x^3=a^2+3b^2$ ，其中 $2\nmid x,(a,b)=1$ ，它里面有我们熟悉的二次表达式。考察 $x$ 的每个素因子 p，因为 $\left(\dfrac{-3}{p}\right)=1$ ，故总有 $p={\alpha}^2+3{\beta}^2$ （可参考下面将要介绍的平方数分解的最后一段）。使用公式（8）（使用复数证明这类等式更容易，并且体现了范数的思想），可知总有 $x={\alpha}^2+3{\beta}^2$ 。下面证明总能找到合适的 $α,β$ ，使得关系式（9）成立。
$({\alpha_1}^2+3{\beta_1}^2)({\alpha_2}^2+3{\beta_2}^2)=(\alpha_1\beta_1\pm \alpha_2\beta_2)^2+3(\alpha_1\beta_2\mp \alpha_2\beta_1)^2\tag{8}$
$a=\alpha^3-9\alpha\beta^2,\:b=3\alpha^2\beta-3\beta^3,\quad (a,b)=1,\:(\alpha,3\beta)=1\tag{9}$

使用归纳法证明，当 $x=1$ 时，公式（9）显然成立。若结论对 $x$ 成立，则考虑 $(px)^3=a^2+3b^2$ ，我们的目的是找到表达式（9）。由前面的结论可有 $p^3=c^3+3d^3$ ，且有 $\alpha_1\beta_1$ 和 $c,d$ 满足类似（9）的关系式。与刚才的式子相乘并除以 $p^6$ 得到（10），然后证明（10）式右侧的两项可以都是整数。若记 $x^3=e^2+3f^2$ ，则由假设知存在 $\alpha_2\beta_2$ 和 $e,f$ 满足类似（9）的关系式。综合以上结论，可得到的相关结论（11），它们满足公式（9），定理得证。
$x^3=(\dfrac{ac\pm 3bd}{p^3})^2+3(\dfrac{ad\mp 3bc}{p^3})^2\tag{10}$
$a=ec+3fd,\:b=ed-fc,\quad\alpha=\alpha_1\alpha_2+3\beta_1\beta_2,\:\beta=\alpha_2\beta_1-\alpha_1\beta_2\tag{11}$

现在回过头来看式子（7）中的 $z_0$ 。当 $3\nmid u$ 时，由 $u,w$ 必为一奇一偶且互素（想想为什么）和 $z_0$ 为偶数，容易有 $(2u,u^2+3w^2)=1$ ，可以假设式子（12）左侧。而由上面的结论可知（12）的右侧成立，其中最右边三项互质，故有式子（13）。而 $|x_1y_1z_1|^3=|2u|=|x_0+y_0|<|x_0y_0z_0|^3$ 。当 $3\mid u$ 时可以得到同样的结论，由此我们得到了一组积单调递减的解，这是不可能的，所以原方程没有非平凡解。
$t^3=2u,\:s^3=u^2+3w^2,\quad s=\alpha^2+3\beta^2\:t^3=2\alpha(\alpha-3\beta)(\alpha+3\beta)\tag{12}$
$z_1^3=2\alpha,\:x_1^3=\alpha-3\beta,\:y_1^2=\alpha+3\beta,\quad x_1^3+y_1^3=z_1^3\tag{13}$

5.3 $ax^2+by^2+cz^2=0$

将商高方程在系数上进行扩展，得到一般性的 $ax^2+by^2+cz^2=0$ （ $abc≠0$ 且无平方因子），当然我们只需研究其本原解 $(x,y,z)=1$ 。首先容易有 $(a,yz)=1$ ，则存在 $y^{-1},z^{-1}$ ，变换 $by^2 \equiv -cz^2\pmod{|a|}$ 得到式子（14），从而 $−bc$ 是 $|a|$ 的二次剩余。这样我们就得到了方程有解的一个必要条件： $−bc,−ca,−ab$ 分别是 $|a|,|b|,|c|$ 的二次剩余。
$(byz^{-1})^2\equiv -bc\pmod{|a|}\tag{14}$

下面来看它们是否是方程有解的充分条件，使用的是降次法和构造法。另外，利用同余方程研究不定方程也是常见方法，这里我们可以先考虑同余方程（15）。先来看降次，首先容易判断 $(a,b,c)=1$ ，则可以有式（16）。对模 $|b|,|c|$ 也可以有类似的表达式，它们将原式表示成了两个线性表达式之积，问题也就容易转化到一次方程了。使用剩余定理可以将三个表达式的右侧统一成 $(dx+ey+fz)(d'x+e'y+f'z)$ ，再根据同余的性质就有式（17）。
$ax^2+by^2+cz^2\equiv 0\pmod{|abc|}\tag{15}$
$ax^2+by^2+cz^2\equiv b^{-1}((by)^2-(c'z)^2)\equiv (y+b^{-1}c'z)(by-c'z)\pmod{|a|}\tag{16}$
$ax^2+by^2+cz^2\equiv (dx+ey+fz)(d'x+e'y+f'z)\pmod{|abc|}\tag{17}$

要使方程（15）有解，可以先讨论 $dx+ey+fz\equiv 0\pmod{|abc|}$ ，使用鸽笼原理容易得知它有满足条件（18）的解 $x_0,y_0,z_0$ 。这样我们就得到了方程（15）的解，为方便讨论，下面假设 $a>0,b<0,c<0$ ，其它情况都可以转化为这种情况。
$dx+ey+fz,\quad(0\leqslant x\leqslant\sqrt{|bc|},\:0\leqslant y\leqslant\sqrt{|ca|},\:0\leqslant z\leqslant\sqrt{|ab|})\tag{18}$

现在令 $E=ax_0^2+by_0^2+cz_0^2$ ，比较容易推导出 $E<ax_0^2\leqslant abc$ 和 $E>by_0^2+cz_0^2\geqslant -2abc$ ，故有 $E=0$ 或 $E=−abc$ 。若 $E=0$ ，我们就得到了原不定方程的解 $x_0,y_0,z_0$ 。若 $E=−abc$ ，则乘以 ab 再配方就有式（19），不管各项是否全为零我们都能找到原方程的解。
$a(by_0+x_0z_0)^2+b(ax_0-y_0z_0)^2+c(z_0^2+ab)^2=0\tag{19}$

至此充分性证明完毕，总结结论就是： $ax^2+by^2+cz^2=0$ 有解的充要条件是 $-bc,-ca,-ab$ 分别是|a|,|b|,|c|的二次剩余。

6、平方数分解

数论中一个著名的问题是把整数表示成若干个平方数之和 $a=x_1^2+x_2^2+\cdots+x_n^2$ ，平方和常出现于范数当中，其重要性不言而喻。我们先把条件设定得宽松一点，假设 $x_k⩾0$ ，如果 $n=i$ 时对所有a成立，则显然 $n=i+1$ 时也成立，我们需要讨论有没有最小的n使得所有a都成立。当然问题还可以再做放宽，允许对有限个数不成立。当 $n=1$ 时，非平方数有无穷多个，故结论不成立。当 $n=2$ 时， $4k+3$ 都不能表示成两个平方和，结论也不成立。

当 $n=3$ 时，高斯得到过定理：自然数能表示为3个平方和的充要条件是 $a\ne 4^e(8k-1)$ ，这就说明了 $n=3$ 时我们要的结论还是不成立。高斯定理的充分性比较复杂，这里仅证明必要性。首先因为 $x^2\equiv 0,1,4\pmod{8}$ ，所以 $x_1^2+x_2^2+x_3^2\not\equiv -1\pmod{8}$ ，定理中 $e=0$ 时成立（其实这一点就已经说明了n=3时结论不成立）。下面利用归纳法，当 $e=i$ 时必要性成立，如果有 $4^{i+1}(8k-1)=x_1^2+x_2^2+x_3^2$ ，必然有 $2|x_k$ ，从而两边可同时除以 4，这与 $n=i$ 时的必要性成立矛盾，故必要性对一切e成立。

而幸运的是，当 $n=4$ 时，我们要的结论终于成立了，它就是著名的拉格朗日定理：任何正整数都可以表示为四个平方数之和（公式（20）），故也称作四平方和定理。这个定理的证明需要用到四平方和恒等式（21），两个四平方和之积也是四平方和。有了这个恒等式，我们的四平方和定理就等价于：任何素数都可以表示为四平方数之和。下面就来证明这个等价命题，注意证明的过程其实也就是寻找分解式的过程。
$a=x_1^2+x_2^2+x_3^2+x_4^2\tag{20}$
$(a_1^2+a_2^2+a_3^2+a_4^2)(b_1^2+b_2^2+b_3^2+b_4^2)=\\(a_1b_1-a_2b_2-a_3b_3-a_4b_4)^2+\\(a_1b_2+a_2b_1+a_3b_4-a_4b_3)^2+\\(a_1b_3-a_2b_4+a_3b_1+a_4b_2)^2+\\(a_1b_4+a_2b_3-a_3b_2+a_4b_1)^2\tag{21}$

先来证明 $x^2+y^2+1\equiv 0\pmod{p}$ 有解（这里的1使得表达式非零）。当 $x,y$ 各自取遍 $0,1,\cdots,\dfrac{p-1}{2}$ 时， $x^2,-y^2-1$ 各自遍历 $\dfrac{p+1}{2}$ 个不同的数，所以存在 $x_0,y_0$ 满足 $x_0^2+y_0^2+1\equiv 0\pmod{p}$ 。这个结论说明存在 $0<m<p$ 使得 $mp=x_1^2+x_2^2+x_3^2+x_4^2$ 有解，从这里开始，下面我们下面要不断缩小m至1。

首先如果 $d=(x1,x2,x3,x4)>0$ ，则显然 $d^2∣m$ ，方程两边可以约去 $d^2$ 。其次如果 $2∣m$ ，则四个数中必有偶数个奇数，它们可以两两组合为偶数，这样就得到式子（22）。经过以上两步如果仍有 $m>1$ ，将原式对 $x_k$ 取模 m，经过前面类似的整理可以有式子（23）。式（23）和原等式相乘并根据四平方和恒等式，可以有 $m'm^2p=u_1^2+u_2^2+u_3^2+u_4^2$ ，并且由恒等式容易证明 $m\mid u_k$ ，两边除以 $m2，m′<m$ 被再一次缩小。这个过程可以一直进行到 $m=1$ ，这就完成了证明。
$\dfrac{m}{2}p=(\dfrac{x_1+x_2}{2})^2+(\dfrac{x_1-x_2}{2})^2+(\dfrac{x_3+x_3}{2})^2+(\dfrac{x_3-x_4}{2})^2\tag{22}$
$m'm=y_1^2+y_2^2+y_3^2+y_4^2\quad(0<m'<m,\:0\leqslant y_k<\frac{m}{2})\tag{23}$

现在我们把定理的条件加强一点，如果要求 $x_k>0$ ，结论还成立吗？首先容易证明如果 $4∣a$ ，则必有 $4∣x_k$ ，等式两边可以除以 4。利用这个特点并使用归纳法，可以证明 $2⋅4^e$ 都不能表示为四个非零平方数之和。当把 $n=4$ 放宽为 $n=5$ 时，考虑的分解式（24）。当 $a=169+x,(x>0)$ 时，先将x表示为4个非零平方的和，然后从式（24）中选择一个分解，最终总可以将a表示为5个非零平方之和。对于 $a<169$ ，可以一一验证，除了 $1 7,9,10,12,15,18,33$ 外都可以分解为5个非零平方之和。这样就有结论，除了几个特殊值外，所有整数都能表示为5个非零平方之和，当然由证明过程知道结论对n=6也是成立的（只是特殊值会不一样）。
$169=13^2=12^2+5^2+12^2+4^2+3^3=11^2+4^2+4^2+4^2=10^2+6^2+4^2+4^2+1^2\tag{24}$

在理解了上述介绍之后，可以尝试着思考下如下这个问题：
• 给出 $a=2^k$ 时的全部解。并由此证明有无穷多个a使得方程不存在 $(x1,x2,x3,x4)=1$ 的解，有无穷多个a使得方程不存在 $x_k$ 互不相等的解。

高斯定理给出了 $n=3$ 时方程有解的充要条件，现在来看 $n=2$ 时的情景，这个问题也是非常重要的。先来看素数的情况 $p=x^2+y^2$ ，显然它有解时必定有 $p=2$ 或 $p=4k+1$ 。而当 $p=4k+1$ 时，−1是p的二次剩余，所以 $x^2+1≡0$ 有解。使用和四平方和定理完全一样的方法（当然也得益于平方和恒等式：平方和之积也是平方和），可以构造出 $p=x_0^2+y_0^2$ 。

现在回到一般整数 $a=d^2m$ ，其中m无平方因子。由刚才的结论与平方和恒等式，如果m不含素因子 $4k+3$ ，则它必定能表示为平方和。反之如果m能表示为 $x_0^2+y_0^2$ ，则它的任何素因子满足 $x_0^2+y_0^2\equiv 0(\mod p)$ ，故必有 $p=2$ 或 $p=4k+1$ 。总结以上就有结论： $a=d^2m$ 可分解为二平方和的充要条件是m不含素因子 $4k+3$ 。

对 $n=2$ 时，可以提一个跟严格的问题：方程何时有 $(x,y)=1$ 的解。其实刚才的证明中已经看出，首先奇素数因子只能为 $p=4k+1$ ，另外容易证明 $4\nmid a$ 。反之如果 $p=2$ 或 $p=4k+3$ ，前面的证明中已经表示它能表示为二互素数的平方和。接下来用归纳法可知该结果对 $p^e$ 也成立，用类似方法也能得到 $p^e$ 的组合还是成立。这样就得到结论：整数可分解为二互素数的平方和的充要条件是：不含因子4和 $4k+3$ 。

顺便提一下，对 $p=x^2+y^2$ 有解的条件，还有一个更通用的证法。首先同样有必要条件 $\left(\dfrac{-1}{p}\right)=1$ ，下面来证充分性。证明的主要思路还是构造法，对 $s^2\equiv -1\pmod{p}$ 的解 $s_0$ ，先来构造 $x_0\equiv s_0y_0\pmod{p}$ 。方法很简单，限定 $(0\leqslant x,y<\sqrt p)$ ，则 $x−s_0y$ 必有模p相等的两个数，相减即得 $x_0\equiv s_0y_0\pmod{p}$ 。然后自然就有 $x_0^2+y_0^2\equiv 0\pmod{p}$ ，又因为 $x_0^2+y_0^2<2p^2$ ，所以就有 $x_0^2+y_0^2=p$ 。同样的证法也可以得到 $x^2+dy^2=p,(d=2,3)$ 有解的充要条件是 $\left(\dfrac{d}{p}\right)=1$ ，但要注意d越大，要排除的情况越多，结论不一定成立。最后思考一些问题：
　　• 求证不能表示为整数平方和的整数也不能表示为有理数的平方和，并讨论有理数能表示为有理数平方和的充要条件；
　　• 证明 $p=x^2+y^2$ 的正解唯一。

7、佩尔方程

最后再来看一类很重要的方程：佩尔（Pell）方程 $x^2-dy^2=\pm 1$ ，其中d为非平方正数。方程经过整理可以得到表达式（25），它表示 $\dfrac{x}{y}$ 是 $\sqrt{d}$ 的近似分数。这不由得使我们想到了连分数，尤其是其精度误差，也许只有连分数能达到，下面就来证明这一猜测。令 $\dfrac{p_k}{q_k}$ 表示 $\sqrt{d}$ 的第k个连分数， $x_0,y_0$ 是方程的一组正解。

$\left|\dfrac{x}{y}-\sqrt{d}\right| =\dfrac{1}{y^2(\dfrac{x}{y}+\sqrt{d})}\leqslant\dfrac{1}{2y^2}\tag{25}$

首先假设 $q_k\leqslant y_0<q_{k+1}$ ，由 $y_0<q^{k+1}$ 并根据渐进连分数的性质有 $\left|\sqrt{d}q_k-p_k\right|\leqslant\left|\sqrt{d}y_0-x_0\right|$ ，从而 $\left|\sqrt{d}-\dfrac{p_k}{q_k}\right|<\dfrac{1}{2y_0q_k}$ 。如果 $y_0≠q_k$ ，仅从分数的性质容易得到 $\left|\dfrac{p_k}{q_k}-\dfrac{x_0}{y_0}\right|\geqslant \dfrac{1}{y_0q_k}$ ，而另一方面有式子（26），结合这两个式子可有 $y_0<q_k$ ，矛盾。所以必定有 $y=q_k$ ，接下来容易得到 $x_0=p_k$ ，从而我们知道方程的解必定是的渐进连分数的分子和分母。
$\left|\dfrac{p_k}{q_k}-\dfrac{x_0}{y_0}\right|\leqslant\left|\sqrt{d}-\dfrac{p_k}{q_k}\right|+\left|\sqrt{d}-\dfrac{x_0}{y_0}\right|<\dfrac{1}{2y_0q_k}+\dfrac{1}{2y_0^2}\tag{26}$

下面就从这些渐进分数中寻找方程的解，通过计算渐进分数，可以得到 $p_k^2-dq_k^2=(-1)^kb_k$ ，其中 $b_k$ 为余部的分母（参考课本）。并且从推导过程中可以得到 $b_k$ 仅在 $c\mid k$ 时为1而不可能为−1，其中c为连分数的循环周期。如此一来我们就得到了方程的所有解为 $p_{hc},q_{hc}$ ，但要注意方程的值只能取±1其一，规律也是明显的，以后不加区分。

到这里为止，我们似乎已经解决了问题，但方程的解其实还没有一个清晰的表达方法，从方程本身的特点出发，也许还能有进一步的结论。方程的一大特点是等式值为±1，而左边是两个共轭数 $p_k+\sqrt{d}q_k,p_k-\sqrt{d}q_k$ 之积。不妨把方程的解与复数 $x_k=p_{kc}+\sqrt{d}q_{kc}$ 一一对应起来，由刚才的讨论可知任何满足 $x\bar{x}=\pm 1$ 的x都是方程的解，并且 $x_k$ 都是方程的解。这样我们自然要问，是否每个 $x_k$ 都可以表示为 $x_1$ 的幂？

如果有 $x_1^k<x_m<x_1^{k+1}$ ，则有 $1<x_mx_1^{-k}<x_1$ ，而容易证 $x_mx_1^{-k}=x_m(\pm \bar{x}_1^k)$ 也是方程的解。但方程不可能有比 $x_1$ 小的解，矛盾，故必然有 $x_k=x^k_1$ ，即方程的所有解都可以与表达式（27）中的复数一一对应。这样只要知道第一组解，就可以得到所有解，第一组解可以通过简单的遍历尝试得到，有些书上还给出了一定范围内的解的表，可供查阅。
$p_{kc}+\sqrt{d}q_{kc}=(p_c+\sqrt{d}q_c)^k\tag{27}$
　　
　　最后来考虑一下下面这几个问题：

• 求证 $p=4k+1$ 时，讨论 $x^2-py^2=\pm 1$ 最小解下方程的取值；

• 不使用连分数理论讨论方程 $x^2-dy^2=1$ ，先证明存在m使得 $x^2-dy^2=m$ 有无穷多解，然后证明 $x^2-dy^2=1$ 有解，最后证 $(x_1+\sqrt{p}y_1)^k$ 是所有解；

• 使用佩尔方程证明，如果 $x^2-dy^2=n$ 有解，则有无穷多组解；

• 证明若佩尔方程 $x^2-dy^2=1$ 的解满足 $x_0>\dfrac{y_0^2}{2}-1$ ，则它是最小解。

至此，到这儿。我们要介绍的初等数论的理论部分就结束了，后面几篇会跟着介绍下初等数论在工程实际中的应用。