a是模数m的一个原根, 那么
a ,a2 ,? ,a?(m)
与a1 ,a2 ,? ,a?(m)按一定的顺序对应关于模m同余.
证明 因为(a,m)?1, 所以对任何k:1?k??(m), 有(ak,m)?1, 于是ak与某个ai关于模
m同余, 且集合?a,a2,?,a?(m)?中的?(m)个数关于模m两两不同余, 因此集合?a,a2,?,a?(m)?中的每个数“与且仅与”集合▋
定理1. 19 设m数.
这里略去证明，有兴趣的读者可参考其它初等数论书籍. 定理1. 20 设m集合
?a,1a2?,,?am(?)中
的某个数关于模
m同余.
?1, 若模数m有原根的充要条件是m等于2, 4, pl或2pl, 其中l?1, p为奇素
?1, 模数m有原根g, 则m恰有?(?(m))个关于模m不同余的原根,它们是由
S??gt|1?t??(m),(t,?(m))?1?
中的数给出.
证明 设g是m的一个原根, 则ordm(g)??(m). 由于?(m)个整数
1,g,?,g?(m)?1
关于模m两两不同余, 因此它们构成m的一组简化剩余系. 设a是m的任一原根, 则存在某个整数
k: 1?k??(m)，使gk?a(modm). 由定理4. 2可知a关于模的阶为
?(m)??(m).
(?(m),k)故(?(m),k)?1, 即a与S中的一个数关于模m同余. S中的任意一个数关于模m的阶均为?(m), 因而均是原根. 而S中的数关于模m两两
另一方面,
不同余, 因此S给出了关于模m全部两两不同余的原根, 共?(?(m))个. ▋
例1. 25 已知2是模数11的一个原根, 求出模数11的所有原根. 解 因为?(11)?10且2是模数11的一个原根, 所以
?1,2,?,2?是模数11的一组简化剩余系.
9 31
由于
1,2?,,中9与10
互素的整数有
?(10?)4个,它们是1,3,7,. 9所以由定理
1.20及
21?2(mod11),23?8(mod11),27?7(mod11),29?6(mod11)可得, 模数11的所有原根是
2,6,7,8. ▋
练习1. 11
1. 证明5是6的一个原根，也是7的一个原根. 2. 证明2是13的一个原根，并由此求出13的所有原根. 3. 求出41的一个原根. 4. 证明：如果素数5. 设
, 则a是p的一个原根. p?2??1, (ap)??12p是奇素数, 求同余式xp?1?1(modps), s?1的全部解.
22素数71有一个原根7, 求出71的所有原根, 并求71和2?71的一个原根.
§1.12 二次剩余
定义1.15 设m是正整数，a是整数且满足(a,m)?1, 如果同余方程
x2?a(modm) (1.12.1)
有整数解, 则称a是模m的二次剩余或平方剩余(Quadratic Residue), 记作a?QRm. 否则称a是模m的二次非剩余或平方非剩余(Non-Quadratic Residue), 记作a?NQRmm.
例如，1，3，4，5，9模11的二次剩余.2, 6，7，8，10是模7的二次非剩余.1，9，11是模14的二次剩余，3，5，13是模14的二次非剩余.
显然, 如果a?b(modm), 那么a是模m的二次剩余当且仅当b是模m的二次剩余. 因此, 一个
给定的整数是否为模m的二次剩余? 只需要考虑模m的简系中的对应元素是否为模m的二次剩余.
由于一般正整数模的二次剩余问题可转化成其不同素因子的二次剩余问题，所以下面只涉及素数模的二次剩余的情形.
例1.26 对于模剩余？
解 为了确定1,2,?,12中哪些是模13的二次剩余，需要知道，当a跑遍集合些同余方程
32
p?13, 判断1,2,?,12中哪些数是模13的二次剩余？那些数是模13的二次非
?1,2,?,12?时，哪
有解.
已知整数1,2,?,12的平方是
x2?a(mod13)
12?122?1(mod13), 22?112?4(mod13), 32?102?9(mod13), 42?92?3(mod13), 52?82?12(mod13), 62?72?10(mod13).
由上面的计算结果可知, 模13的二次剩余是1,3,4,9,10,12. 二次非剩余是▋
对于给定的奇素数
2,5,6,7,8,11.
p, Euler 给出了判断一个整数a是否为模p的二次剩余的判别方法.
p是奇素数且(a,p)?1, 那么整数a是模p的二次剩余的充分且必要
定理1.21（Euler准则） 设条件是
a(p?1)2?1(modp).
证 设a是模
p的二次剩余. 则x2?a(modp)有一个整数解, 设为x1.由Fermat小定理可得
a(p?1)2?(x12)(p?1)2?(x1)p?1?1(modp).
反之，设
a(p?1)2?1(modp), r是模
p的一个原根, 那么存在整数
k(1?k?p-1)使得
. 因此 a?rk(modp)rk(p?1)/2?a(p?1)/2?1(modp).
由r是模
p的一个原根可得(p?1)k(p?1)2, 于是k是偶数. 设k?2j, 则有
(rj)2?r2j?rk?a(modp).
这说明r是同余方程xj2?a(modp)的一个解, 即a是模p的二次剩余. ▋
p是奇素数且(a,p)?1, 那么整数a是模p的二次非剩余的充分
例1.27(Euler准则的推论) 设且必要条件是
a(p?1)2??1(modp).
证 如果
p是奇素数且(a,p)?1, 由Fermat小定理可得ap?1?1?0(modp).于是
(a(p?1)2?1)(a(p?1)2?1)?ap?1?1?0(modp)，
33
因此
a(p?1)2?1(modp) 或 a(p?1)2??1(modp)
成立，且不能同时成立.假若同时成立,则有1??1(modp)或p2，这与p是奇素数矛盾.
既然模
p的二次非剩余不满足a(p?1)2?1(modp)，那么必满足a(p?1)2??1(modp).
(p?1)2反之，若a??1(modp)，则由定理1. 21可知a是模p的二次非剩余. ▋
练习1. 12
1．分别找出素数11，13的所有二次剩余. 2. 分别找出整数7，11的所有二次非剩余. 3．证明对于奇素数
?12p，模p的二次剩余与整数12,22,32,?,(p2)关于模p同余.
4．证明若a是奇素数模5．证明若
p的二次剩余，那么a不是模p的原根.
(p?5)(p?1)??2?8. ???(?1)?p?p是奇素数，则
6．对于奇素数或者同为模
p, 如果ab?r(modp), 且r模p的二次剩余, 那么a,b同为模p的二次剩余,
p的二次非剩余.
7. 是奇素数. 如果
a,b同为模p的二次剩余，或者同为模
p的二次非剩余, 那么同余式
有解. a?x2?b(modp)§1.13 Legendre符号与Jacobi符号
由Euler准则我们可以判定一个整数是否为模
p的二次剩余.但是当p很大的时候，这种判断方法计算
起来有一定困难，不实用.利用下面我们介绍的勒让德（Legendre）符号，则可得到一个计算上相对简便的判别方法.
定义1. 16 设
p是奇素数，模p的勒让德（Legendre）符号定义为：
? 1 如果(a,p)?1且 a 是模数 p 的二次剩余;?a???p????1 如果(a,p)?1且 a 是模数 p 的二次非剩余; ???? 0 如果 pa.注意：如果
p是奇素数，那么同余式且
p)，而且如果x2?1(modp)只有解x??1(mod?,?????1,0,1?
???? (modp)，那么
p(????) ，因此????.特别地，如果
34
?a??a??p???(modp)，那么?p???????.
定理 1.22 ( Legendre符号性质定理) 设
p是奇素数，(a,p)?1，(b,p)?1, 那么
i) 如果a?????b(modp)，那么?a???b?；
?p??p?ii)
?a2??p??1; ???a??p?1?2(modp)(在某些教科书中, 该性质也称为Euler准则)； ?p??a???ab??a??b?rkr0rr21?p???p??p?,一般地,如果整数a的素因子分解式为a??2q1q2?qk, 那??????iii)
iv)
么
?ap????p1??? v)
证明 i）显然. ii）对于同余式x2rkr0qr1qr2q??????k212?p??p???p?； p????????1??1?p?12?(?1)，. ?1???????p??p??2??a2(modp)，a就是它的解, 因此?a??1.
?p?iii) 由定理1. 21直接可得?iv) 由ii)可得：
?a?(p?1)2(modp). ??a?p??ab?????(p?1)2(modp)?a(p?1)2?b(p?1)2(modp)??a??b?(modp). ?p??(ab)???p??p?由于勒让德符号为1或
?1,
假若
?ab??a??b?p, )矛盾. ?p???p??p, ?那么1??1(mod??????因此
?ab??a??b??p???p??p. ???????v） 由iii)直接可得. ▋ 例1. 28 设
p是奇素数，则有
35