初等数论基础：原根的存在与特性

本节介绍正整数原根的概念并探讨正整数原根存在的充要条件.

定义7.2.1　设a，m∈Z，m＞1，（a，m）=1.若a对模m的阶为φ（m），则称a是模m的原根.易见，若a是模m的原根，则与a关于模m同余的任意整数也都是模m的原根.这表明，找模m的原根只需在模m的一个简化剩余系中找即可.

值得注意的是，并不是任意正整数均有原根.例如，8就没有原根.事实上，在模8的简化剩余系1，3，5，7中，有

11≡1（mod8），32≡1（mod8），52≡1（mod8），72≡1（mod8），

但φ（8）=4.鉴于这种情况，一个自然的问题是：什么样的正整数有原根？本节的目的就是解决这一问题.先看一个预备结果.

引理7.2.2　设a，β∈Z，β≥3，（a，2β）=1.则≡1（mod2β）.

证明　由（a，2β）=1知a为奇数.于是，

a≡1（mod8），a≡3（mod8），a≡5（mod8），a≡7（mod8）

中有且仅有一个成立.这表明a2≡1（mod23）.故β=3时命题成立.设

则存在u∈Z使得故

由归纳法原理知结论成立.证毕.

命题7.2.3　设m∈Z且m＞1.若模m有原根，则m只能为2，4，pα，2pα，其中p是奇素数，α是正整数.

证明　情形1：m无奇素因数.此时设m=2β.若β≥3，则由引理7.2.2知对任意a∈Z，（a，2β）=1蕴含由2β-2＜φ（2β）=2β-1知β≥3时模m无原根.故β只能为1，2，即m只能为2和4.

情形2：设m有奇素因数.此时设

若a是模m的原根，则a对模m的阶为设

则l≤φ（m）.另一方面，由欧拉定理知

由于l是的最小公倍数且两两互素，故al≡1（modm）.但a对模m的阶为φ（m），从而l≥φ（m）.这表明l=φ（m），即

这导致两两互素.

若k≥2，则

均为偶数，这与两两互素矛盾.故k=1而若α≥2，则均为偶数，这又与

两两互素矛盾.故α只能为0或1而m只能是或证毕.

下面证明命题7.2.3的逆命题也成立.

命题7.2.4　设p是奇素数.则模p有原根.

证明　设1，2，…，p-1对模p的阶为δ1，δ2，…，δp-1并记δ=［δ1，δ2，…，δp-1］.又设δ的标准分解式为则对任一均存在及ai∈Z使得

据命题7.1.5知对模p的阶为注意到诸两两互素，据命题7.1.6知x=x1x2…xk对模p的阶为δ.据推论7.1.4知δ≤φ（p）=p-1.另一方面，由于1，2，…，p-1对模p的阶为δ1，δ2，…，δp-1且δ=［δ1，δ2，…，δp-1］，故(www.xing528.com)

这表明xδ≡1（modp）有p-1个解.由推论5.4.6知p-1≤δ.故δ=p-1=φ（p）.于是x就是模p的原根.证毕.

命题7.2.5　设p是奇素数，α是大于1的整数，g是模p的原根.

（1）存在t0，u0∈Z使得

（2）若整数t0，u0满足条件（7.2.1），则g+pt0是模pα的原根.

证明　　　（1）由g是模p的原根知（g，p）=1和gp-1≡1（modp）.故可设

由于（g，p）=1，从而（gp-2，p）=1.于是关于t的同余方程gp-2t≡T0（modp）只有一解，从而必存在t0∈Z使得gp-2t0≢T0（modp），即于是

其中

显然，由知

（2）由（7.2.1）知

和类似可得

由于（g+pt0，p）=（g，p）=1，从而（g+pt0，pα）=1.故g+pt0对模pα的阶存在，设这个阶为δ.则

于是（g+pt0）δ≡1（modp）.由g是模p的原根知g+pt0也是模p的原根.据原根定义及定理7.1.3知p-1=φ（p）|δ.另一方面，由δ的定义及推论7.1.4知可知δ|φ（pα）=pα-1（p-1）.这表明δ=pr-1（p-1），其中r是1，2，…，α中的某个数.将δ=　pr-1（p-1）带入（7.2.2）并结合（7.2.3）可得1+prur-1≡1（modpα），进而有prur-1≡0（modpα）.由知pr≡0（modpα），而由r是1，2，…，α中的某数可知α=r.故δ=pα-1（p-1）=φ（pα）.这证明了g+pt0是模pα的原根.证毕.

推论7.2.6　设p是奇素数，α是大于1的整数，g是模p的原根.若-1，则g是模pα的原根，否则，g+p是模pα的原根.

证明　首先，由g是模p的原根知p|gp-1-1.若，则存在u0∈Z使得

于是，（g+p·0）p-1=1+pu0，据命题7.2.5知g=g+p·0是pα的原根.另一方面，由g是模p的原根知g+p也是模p的原根.若p2|gp-1-1，则

于是存在v0∈Z使得

由（g，p）=1知（gp-2，p）=1.记u0=pv0-gp-2.则（g+p·1）p-1=1+pu0，据命题7.2.5知g+p=g+p·1是pα的原根.证毕.

引理7.2.7　设p是奇素数，α是正整数.则对任一正奇数x及正整数γ，

命题7.2.8　设p是奇素数，α是正整数，g是模pα的原根.则g和g+pα中的奇数是模2pα的原根.

证明　由g是模pα的原根知g+pα也是模pα的原根.故模pα总有奇数原根a.于是

据引理7.2.7及φ（2pα）=φ（pα）知

这表明a是模2pα的原根.证毕.

容易看出，模2和模4必有原根.故由命题7.2.3，7.2.4，7.2.5和7.2.8可得以下结论.

定理7.2.9　设m是大于1的整数.则模m存在原根当且仅当m=2，4，pα，2pα，其中p是奇素数，α是正整数.