

原根

前置知识¶

前置：费马小定理，欧拉定理，拉格朗日定理。

这里只给出拉格朗日定理的证明。

拉格朗日定理：设为素数，对于模意义下的整系数多项式

的同余方程在模意义下至多有个不同解。

证明：对使用归纳法。当时，由于，故无解，定理对的多项式都成立。

若命题对于的都成立，由反证法，假设存在一个满足题目条件的在模意义下有着至少个不同的解。

可设，则在模意义下是一个至多次的多项式。现在由都是的解，知对，都有

而，故，从而有至少个根，与归纳假设矛盾。

所以，命题对次多项式也成立，定理获证。

证毕

阶¶

阶：由欧拉定理可知，对，，若，则。

因此满足同余式的最小正整数存在，这个称作模的阶，记作。

性质¶

性质：模两两不同余。

证明：考虑反证，假设存在两个数，且，则有。

但是显然的有：，这与阶的最小性矛盾，故原命题成立。

证毕

性质：若，则。

证明：对除以作带余除法，设。

若，则

这与的最小性矛盾。故，即。

证毕

据此我还可以推出：

若，则有。

还有两个与四则运算有关的重要性质。

性质：设，，，则

的充分必要条件是

证明：

必要性

由及，可知

由前面所述阶的性质，有

又由于，故

即。

充分性

由可知

故。结合即得

对称地，同理可得

所以

另一方面，有

故

综合以上两点即得

证毕

性质：设，，，，则

证明：注意到：

另一方面，由，可知：

故：

综合以上两点，得：

证毕

原根¶

原根：设，。若，且，则称为模的原根。

原根判定定理¶

原根判定定理：若一个数是模的原根，则有对于任何大于且不为自身的因数，都有。

证明： 假设存在一个使得且。

由裴蜀定理得，一定存在一组满足；由欧拉定理/费马小定理得；故有：

又有，故。

又，故必至少整除中的至少一个，设，则。

故假设不成立，原命题成立。

证毕

原根个数¶

若一个数有原根，则它原根的个数为。

证明：若有原根，则：

所以若，则有：，即也是模的原根。

而满足且的有个。所以原根就有个。

证毕

原根存在定理¶

原根存在定理：一个数存在原根当且仅当，其中为奇素数，。

我们来证明它，分成、、与，四个部分。

，原根显然存在。
，其中为奇素数，。

定理 1：对于奇素数，有原根。

证明：先证一个引理：

引理：设与是与互素的两个整数，则存在使得。

证明：我们先将表示成质因数分解的形式：

接着将它们表示成如下形式：

其中：

则由阶的性质，可得：

同理：

又因为显然有，，则再由阶的性质，可得：

于是令则原命题得证。

证毕

回到原命题，对依次两两使用引理，可知存在使得

这表明，所以都是同余方程

的根。由拉格朗日定理，可知方程的次数。

又由费马小定理，易知，故。

综上可知为模的原根。

证毕

定理 2：对于奇素数，，有原根。

证明：一个基本的想法是将模的原根平移。

先证明一个引理：

引理：存在模的原根，使得。

证明：事实上，任取模的原根，若不满足条件，我们认定满足条件。

易知也是模的原根。

我们有

证毕

回到原题，我们证明若是一个满足引理条件的原根，则对任意，是模的原根。

首先，证明下面的结论：对任意，都可设

这里。事实上，时，由的选取可知结论成立。现设上式对时成立，则

结合可知命题对成立。

所以命题对任意都成立。

其次，记，则由欧拉定理，可知。

而由为模的原根，及。

所以可设，这里。

现在利用之前的结论，可知：