《初等数论基础》：计算原根的具体方法

本节的主要目的是探讨原根的具体计算方法.如本章第1节指出的那样，求原根只需在某个简化剩余系中求即可.下面的结论指出了原根与简化剩余系的紧密联系.

命题7.3.1　设m是大于1的整数，g是模m的原根，则1，g，g2，…，gφ（m）-1是模m的简化剩余系.

证明　由g是模m的原根知（g，m）=1，从而

（gi，m）=1，i=0，1，…，φ（m）-1.

若

gi≡gj（modm），φ（m）-1≥i＞j≥0，

则由（gj，m）=1知gi-j≡1（modm）.这与g对模m的阶为φ（m）矛盾.这表明1，g，g2，…，gφ（m）-1是与m互素的两两对模m不同余的φ（m）个数.据命题4.3.4知它们构成模m的简化剩余系.证毕.

下面确定模m的对模m互不同余的原根（若原根存在的话）的个数.

命题7.3.2　设m是大于1的整数，g是模m的原根.则gi对模m的阶为

于是，对模m的简化剩余系1，g，g2，…，gφ（m）-1来说，gi是原根当且仅当（i，φ（m））=1.这表明模m的对模m互不同余的原根的个数为φ（φ（m））.

证明　首先，有

其次，若γ是正整数且（gi）γ≡1（modm），则由g对模m的阶为φ（m）知φ（m）|iγ，从而

由　互素知这表明故gi对模m的阶为δ.证毕.

下面的命题给出了求模m的原根的一个指导性方案.

命题7.3.3　设m，g∈Z，m＞1，（g，m）=1且φ（m）的所有不同的素因数为q1，q2，…，qk.则g是模m的原根当且仅当

证明　必要性由原根定义立得.反之，设命题条件成立而g对模m的阶δ小于φ（m）.据推论7.1.4知是大于1的整数，从而存在某个进而存在正整数u使得这导致

这与定理假设条件矛盾.证毕.

例7.3.4　求模43的最小正原根并据此求出43α，2·43α的一个原根，其中α是正整数.

解　首先，有φ（43）=2×3×7.其次由=16384≡1（mod43）知2不是模43的原根.注意到

36≡-2（mod43），314≡36（mod43），321≡-1（mod43），

据命题7.3.3知3是模43的原根，从而是模43的最小正原根.又

37=2187≡338（mod432），3382=114244≡-394（mod432），

3383≡-394×338≡-44（mod432），（-44）2≡1936≡87mod432）.

故342-1≡86（mod432）.这说明据推论7.2.6知3是43α的原根.另外由3是奇数和命题7.2.8知3也是2·43α的一原根.解毕.

上述命题7.3.3找原根的方法并不永远可以用来作实际计算.原因在于找φ（m）的素因数没有一般求法.另外，即使找到了φ（m）的素因数，命题7.3.3中条件的验证也是非常之烦琐的.事实上，可以考虑另外的方案.根据上节，求原根的问题可归结为求奇素数模的原根.遗憾的是，奇素数模的原根求起来也很困难.但对某些特殊类型的奇素数，人们还是获得了一些求原根的方法.这些方法主要是与二次非剩余联系起来.本节剩余的内容主要来自参考文献［13］.首先，有如下的基本结果.

命题7.3.5　设p是奇素数.则模p的原根皆为模p的二次非剩余.

证明　设g是模p的原根.若g是二次剩余，则据定理6.2.5有

这表明g对模p的阶不大于这与g对模p的阶为φ（p）=p-1矛盾.证毕.

命题7.3.6　设p是奇素数.则模p之全部二次非剩余全为模p的原根当且仅当p是费马数.

证明　设p是费马数.则存在n∈Z使得p=22n+1.据定理6.2.3知在模p的一个简化剩余系中，二次非剩余有个.据命题7.3.2知模p的一个简化剩余系中原根数为

由命题7.3.5，模p的全部二次非剩余全为模p的原根.反之，若模p的全部二次非剩余全为模p之原根，则φ（p-1）=设p=2t·s+1，s是奇数.则

这导致φ（s）=s，从而s=1.因p是素数，据第习题1.4的第6题可知t是2的方幂，即p是费马数.证毕.(www.xing528.com)

设p是奇素数.据命题7.3.5知，若能找出模p的全部二次非剩余并能较快的排除其中的非原根，则模p的原根就求出来了.事实上，对某些类型的素数，这是容易做到的.下面介绍形如2p1+1，4p1+1和8p1+1的素数的全部原根的求法，这里p1是任一奇素数.

定理7.3.7　设p=2p1+1是素数，p1是奇素数.则在模p的简化剩余系1，2，…，p-1中除p-1以外的二次非剩余就是模p的所有原根.

证明　由知p-1是模p的二次非剩余，而由及知p-1不是模p的原根.由于模p的原根均为模p的二次非剩余，而在1，2，…，p-1中二次非剩余有个，故在1，2，…，p-1中原根至多有p1-1个.但据命题7.3.2知在1，2，…，p-1中模p的原根个数为

φ（φ（p））=φ（p-1）=φ（2p1）=p1-1.

于是在1，2，…，p-1中除p-1以外的二次非剩余就是模p的所有原根.证毕.

例7.3.8　求模23的最小正原根并据此求出23α，2·23α的一个原根，其中α是正整数.

解　由23=2×11+1及定理7.3.7知模23的最小正简化剩余系中最小的二次非剩余就是其最小正原根.由于

故5是模23的最小正原根.又

52≡25（mod232），（23+2）11≡11×23×210+211≡323（mod232），

从而522-1≡322（mod232）.这说明据推论7.2.6知5是23α的一原根.另外由5是奇数和命题7.2.8知5也是2·23α的一原根.解毕.

下面考察4p1+1及8p1+1型素数，p1是奇素数.先介绍几个基本结论.

命题7.3.9　设p是4n+1型素数，g∈Z，（g，p）=1.则g和p-g或同为模p的二次剩余或同为模p的二次非剩余.

证明　由p是4n+1型素数知是偶数.于是

据定理6.2.5知结论成立.证毕.

命题7.3.10　设p是4n+1型素数，g∈Z，（g，p）=1.若g是模p的原根，则p-g也是模p的原根.

证明　由（g，p）=1知（p-g，p）=1.设p-g对模p的阶为l.则

另外，据推论7.1.4知l|φ（p）=p-1.于是

由于g对模p的阶是φ（p）=p-1，据定理7.1.3知p-1|2l.故存在s，t∈Z，s，t＞0使得p-1=sl，（p-1）t=2l.于是st=2.这导致l=p-1或若则由p是4n+1型素数知l为偶数，从而

这与g是模p的原根矛盾.故l=p-1=φ（p），即p-g是模p的原根.证毕.

定理7.3.11　设p=4p1+1是素数，p1是奇素数.若，0＜f＜p，则在模p的简化剩余系1，2，…，p-1中除f及p-f以外的二次非剩余就是模p的所有原根.

证明　由

知f是模p的二次非剩余，据命题7.3.9知p-f也是模p的二次非剩余.据欧拉定理及事实，有

由4＜φ（p）=p-1=4p1知f不是模p的原根，据命题7.3.10知p-f也不是模p的原根.类似于定理7.3.7的证明可知1，2，…，p-1中除f及p-f以外的二次非剩余就是模p的所有原根.证毕.

例7.3.12　求模29的最小正原根并据此求出29α，2·29α的一个原根，其中α是正整数.

解　注意到29=4×7+1和27=128≡12（mod29），据定理7.3.11知模29的最小正简化剩余系中除去12，17以外的最小的二次非剩余就是其最小正原根.由

知2是模29的最小正原根.又

25≡32（mod292），225≡325≡（29+3）5≡5×29×34+35≡214（mod292），

从而228-1≡29（mod292）.这说明据推论7.2.6知2是29α的原根.另外由2是偶数和命题7.2.8知2+29α是2·29α的原根.解毕.

对于8p1+1型素数（p1是奇素数）的情况，有下面复杂的结果，其证明类似于定理7.3.11.

定理7.3.13　设p=8p1+1是素数，p1是奇素数.又设h是模p的任一二次非剩余，，0＜f1＜p，而a为适合的模p的二次剩余且，0＜f2＜p.则在模p的简化剩余系1，2，…，p-1中除f1，f2及p-f1，p-f2以外的二次非剩余就是模p的所有原根.