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

~

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

我们来继续研究指数的性质，首先考虑 ，由 知 ，故可容易有公式（1），你可以简单停留思考下，有了（1）式后我们就可以从 求 了。其次由定义显然有：若 ，则 。所以对互质分解 (分解模数)，总有 ，再根据模的性质就有公式（2）。再进一步，对任意的a1,a2,⋯,an，考虑方程组 的 唯一解 a （ 剩余定理 ），显然有 ，再根据公式（2）可得 a 满足公式（3）。



　
　 再来研究 （分解底数），令 ，则显然有 （提示：可以结合(1)式进行思考）。先看各个 互素 的情况，这时 ，令 。因为 ，又因为 互素。故 ，从而有公式（4）。如果 不互素，一般并没有 。但反过来，对任意的 ，利用公式（1）和（4）构造满足公式（5）的 a 还是很容易的。
　

　
　 指数在研究 循环小数 时有个有趣的结论。对既约分数 ，如果有 ，则 是循环小数的充要条件是 。如果 ，则最小循环周期为 c，并且小数点后的非循环数长度为 。特别地，如果 ，则 是纯循环小数。证明过程不是难，可以作为练习，提示：使用关系式

由指数的性质（2）可知 是 个不同的数，特别地当 时，它们遍历 m 的既约剩余系。这种关系使得既约剩余系变得特别简单，我们也由此找到了合适的 坐标 。为此，当 时称 g称为模 m的 原根 ，它便是既约剩余系的 单位元 ，负责将剩余系串成一个线性空间。先来思考如下几个问题：
　
• 如果 ，则 遍历m的既约剩余系时， 也遍历既约剩余系;
• 若 ，或 ，都有 2 是 的原根；
• 的素因子有形式 或 。

我们自然会有问题：什么样的 模数 有原根？有多少个原根？如何判定？前面已经知道 ，而除了 这5种情况外（p为 奇素数 ），容易证明其它都有 ，它们肯定没有原根，因为当模数 m 不属于上面这五种情况时，必有 m 为 或 或 ，而这里的 由 给出。这里的 由下列式子给出：
　 又因为我们有式子， 故可以得到 ，可自行验证。

下面就需要论证那5种情况是否有原根，直接验算可知1,2,4有原根。对于模p的情况，由公式（5）知存在g使得 ，首先当然有 。另外因为 有全解，则 。从而 ，所以p有原根 g。

由 和 的等价性，并且 ，可知 和 有相同的原根，这样一来我们就只需要讨论模 是否有原根了。当g是 原根时，因为 ，故 为 或 。要想g也是 的原根，必须 ，即满足式子（6）。而如果该条件满足，用归纳法可以验算得它对一切 都满足，即g是所有 的原根。

　
　现在只要能证明以上条件对 成立（即 ），我们就找到了所有模 的原根，研究证明了 原根的存在性。对模 p 的原根 g，考察 和式子（7）中的变形。 中有且仅一个是 p 的倍数，取其它任何一个值都能得到了满足条件的原根，条件得证。

至此我们已经证明了原根存在的充要条件是模为 之一，但如果想要找出原根，目前还没有很简单的方法。一般只能逐个尝试每个数，然而利用公式（5）的构造法是可以加快计算的，比如如果已经知道 和 ，因为 ，故素因子 2,3 必定也是模 41 的原根的素因子，经过尝试后得 是 41 的原根。

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

(1)
(2) ,特别地有
(3)

我们一直想把指数当做即约剩余系的“ 坐标 ”，现在就来着手做这件事。一般的，将模m进行素数分解 ，其既约剩余系的每个数 a 在各个维度都有一个值 。对 g_k \gamma_k=\gamma_{p_k^{e_k},g_k}(a_k)$就可以看做a 在第 k 维的坐标。

但对于 ，除 外是没有原根的， 时怎么建立坐标？通过 归纳法 你可以证明 ，并且容易知道 是它的一个既约剩余系。这样任何既约数都有唯一表达式（8）， 就可以看做它的坐标。完整的就得到任何既约数的指标表达式（9）和（10）（（10）中 的是（9）中的 取1、其它取0得来），使用（10）来证明威尔逊定理就简单多了。

最后再来看同余方程（11）它一般称为 二项同余方程 。如果方程有解，称a为m的n 次剩余 ，否则称为n次 非剩余 。对m进行素数分解 后，方程可以化为一个方程组，我们只需分别讨论这些方程即可。

　　
　　模 （p为奇素数）有原根 g，用它来分析二项方程会很简单（下面的讨论针对有原根的模m都成立）。将原根带入原方程，得到式子（12）的左侧，它显然对应于右侧的一元一次同余方程。可以先回顾一下一次方程 的特点，令 ，则 ，且方程解的周期为 ，请先在脑子想象一下它们的布局。回到原方程，令 ，则方程有解的充要条件是 ，且共有 个n次剩余。方程的解有d个，它们的周期是 。

　　
　　现在来把条件 转化为与a直接相关的。因为 ，使用公式（1）直接有式子（13）。结合条件d|γ(a)，显然有 ，它又等价于公式（14）。这就是方程有解的充要条件，明显二次剩余的判定条件只是它的特例。

对模 的情景需要单独考虑，前面的讨论中说明了它的既约剩余系有两个独立的维度，故只需分别讨论两个维度就行了。令 ，可知方程有解的充要条件是 且 ，方程解的个数为 。展开说就是，当 时有且仅有1解，既约剩余系的每个值都是n次剩余。当 时有解的充要条件是 且 ，并且有2d个解，共有 个数是n次剩余。

下面把 有解的充要条件转化为与 a 相关的，首先易知必有形式 。因为 ，我们的条件 其实等价于 ，这就得到充要条件为公式（15）。当然你也可以得到与 类似的式子，但因为不如上式简洁，这里就不赘述了。

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

最简单的不定方程就是一次方程（1），它表现为一个 多元线性方程 。如果你还记得前面最大公约数的线性组合定义，就容易得到方程有整数解的充要条件是 。多元方程的第一步往往是降元，令 ，则方程等价于一次方程组（2）（想想为什么？以及为什么要先抽出最大公约数？）。如果对（2）式一直做类似处理，就会得到多个二元一次方程，这样就把问题集中到了简单的情景。

而对于二元一次方程 ，它有明显的几何意义，方程的解就是直线方程上的整数点，所有对其讨论都可以从图形中找出。容易看出，如果已知一个解 ，则方程的全部解为公式（3）。至于如何求得一个特解，一般还是用辗转相除法，对于一些简单的情况，也可以直接尝试各种值。

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

另外，因为素数的平方只能是 的形式，可推得 x,y 必定是一奇一偶，下面就假设 y 为偶数，原方程整理为式子（4）。容易证明 （这个性质以后会经常用），故可设 和 ，其中 。用 表示 就得到了方程的解（5），但要注意要使得它们两两互素，还需要限定 （自行证明）。

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

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

• 求解 和 ；
• 求解 ；（提示： 无互质解 ）
• 证明 都有无穷多组解。（提示： 构造 ）

再来看费马大定理在 的情景，欧拉证明了它没有非平凡解，采用的是 无穷递降法 。假设 是使得 最小的一组非零解，我们的目的是构造一组值更小的解。首先当然有 ，并且其中仅有一个偶数，经过调整后可以使 为偶数。这时可以令 ，则有 （总结成式（7）），这个变换的重要意义在于 降次 。

现在来研究 ，其中 ，它里面有我们熟悉的二次表达式。考察 的每个素因子 p，因为 ，故总有 （可参考下面将要介绍的平方数分解的最后一段）。使用公式（8）（使用复数证明这类等式更容易，并且体现了范数的思想），可知总有 。下面证明总能找到合适的 ，使得关系式（9）成立。

使用归纳法证明，当 时，公式（9）显然成立。若结论对 成立，则考虑 ，我们的目的是找到表达式（9）。由前面的结论可有 ，且有 和 满足类似（9）的关系式。与刚才的式子相乘并除以 得到（10），然后证明（10）式右侧的两项可以都是整数。若记 ，则由假设知存在 和 满足类似（9）的关系式。综合以上结论，可得到的相关结论（11），它们满足公式（9），定理得证。

现在回过头来看式子（7）中的 。当 时，由 必为一奇一偶且互素（想想为什么）和 为偶数，容易有 ，可以假设式子（12）左侧。而由上面的结论可知（12）的右侧成立，其中最右边三项互质，故有式子（13）。而 。当 时可以得到同样的结论，由此我们得到了一组积单调递减的解，这是不可能的，所以原方程没有非平凡解。

将商高方程在系数上进行扩展，得到一般性的 （ 且无平方因子），当然我们只需研究其本原解 。首先容易有 ，则存在 ，变换 得到式子（14），从而 是 的二次剩余。这样我们就得到了方程有解的一个必要条件： 分别是 的二次剩余。

下面来看它们是否是方程有解的充分条件，使用的是 降次法 和 构造法 。另外，利用同余方程研究不定方程也是常见方法，这里我们可以先考虑同余方程（15）。先来看降次，首先容易判断 ，则可以有式（16）。对模 也可以有类似的表达式，它们将原式表示成了两个线性表达式之积，问题也就容易转化到一次方程了。使用剩余定理

---

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