初等数论基础：原根与n次剩余

本节利用原根的理论来研究n次二项同余方程xn≡a（modm），（a，m）=1.为此，需要引入指标的概念.设m∈Z，m＞1且g是模m的原根.据命题7.3.1知1，g，g2，…，gφ（m）-1是模m的简化剩余系.于是，对任意a∈Z，只要（a，m）=1，就存在唯一的整数t∈｛0，1，2，…，φ（m）-1｝使得a≡gt（modm）.此时，称t为a关于模m的以g为底的指标，记之为indga.即t=indga.

命题7.4.1　设g，g1是模m的原根，a，b∈Z且（a，m）=（b，m）=1.则

（1）indg1=0，indgg=1.

（2）indg（ab）≡（indga+indgb）（modφ（m））.

（3）indgan≡n·indga（modφ（m）），n是任意非负整数.

（4）indga≡（indg1a·indgg1）（modφ（m））.

（5）a≡b（modm）当且仅当indga≡indgb（modφ（m））当且仅当indga=indgb.

（6）若0≤t≤φ（m）-1，则indggt=t.

证明　利用定理7.1.3直接验证即可，留作习题.证毕.

下面用指标研究同余方程

xn≡a（modm），（a，m）=1.

设m≥2，n≥2.若同余方程xn≡a（modm），（a，m）=1有解，则称a为模m的n次剩余.否则称其为模m的n次非剩余.在模m原根存在的前提下，下面的结论从理论上解决了整数a是否为模m的n次剩余的问题.

定理7.4.2　设g是模m的原根，（a，m）=1，n≥2.

（1）a是模m的n次剩余当且仅当（n，φ（m））|indga.此时，同余方程xn≡a（modm）对模m有（n，φ（m））个解.

（2）模m的一个简化剩余系中恰有个模m的n次剩余.

证明　先证xn≡a（modm）有解当且仅当nx≡indga（modφ（m））有解.事实上，若有x0∈Z使得≡a（modm），则据命题7.4.1（3），（5）知n·indgx0≡indga（modφ（m））.这表明nx≡indga（modφ（m））有解.反之，若有x0∈Z使得(www.xing528.com)

nx0≡indga（modφ（m）），

则可设0≤x0≤φ（m）-1.于是由命题7.4.1（3），（6）知

利用命题7.4.1（5）知这表明xn≡a（modm）有解.

（1）据定理3.1.2及上述所证结论可知a是模m的n次剩余当且仅当（n，φ（m））|indga.此时，nx≡indga（modφ（m））关于模φ（m）有（n，φ（m））个解.设这些解为

x≡xi（modφ（m）），0≤xi≤φ（m）-1，i=1，2，…，（n，φ（m））.

据上一段的论证，是xn≡a（modm）的解，i=1，2，…，（n，φ（m））.由命题7.4.1（6）知

再据命题7.4.1（5）知这表明诸是xn≡a（modm）的两两不同的解.另外，若x≡y0（modm）是xn≡a（modm）的解，则据上段的讨论知x≡indgy0（modφ（m））是nx≡indga（modφ（m））的解.由0≤indgy0≤φ（m）-1知indgy0等于某个xi，即xi=indgy0，从而.故诸就是xn≡a（modm）关于模m的全部（n，φ（m））个解.

（2）由g是原根知1，g，g2，…，gφ（m）-1是模m的简化剩余系.据本定理的（1）及命题7.4.1（6），gi（0≤i≤φ（m）-1）是n次剩余当且仅当（n，φ（m））|indggi=i.故1，g，g2，…，gφ（m）-1中的n次剩余的个数就是0，1，2，…，φ（m）-1中能被（n，φ（m））整除的数的个数，这个数是　证毕.

例7.4.3　解同余方程x8≡3（mod11）.

解　容易验证2是模11的一个原根且

20≡1（mod11），21≡2（mod11），22≡4（mod11），

23≡8（mod11），24≡5（mod11），25≡10（mod11），

26≡9（mod11），27≡7（mod11），28≡3（mod11），29≡6（mod11）.

由于，据定理7.4.2知该方程有两个解.先解不定方程8x≡ind23（modφ（11））.这个方程实际上就是8x≡8（mod10）.易知其解为x≡1，6（mod10）.故原方程的解为x≡21，26（mod11），即x≡2，9（mod11）.解毕.

注7.4.4　如前所述，本节只是在模m原根存在的前提下，从理论上解决了整数a是否为模m的n次剩余的问题.对模m原根不存在的情况，讨论起来相对复杂，我们在此就不涉及了，有兴趣的读者可查阅参考文献［10］.