《密码学数学基础》习题集

北京电子科技学院《密码学数学基础》习题集信息安全系密码教研室2015年10月目

录第一章带余除法...................................................................................................3一、整数的最大公因子及其表示..................................................................3二、多项式的最大公因子及其表示..............................................................7三、标准分解和最小公倍数..........................................................................9四、其他类型题............................................................................................11第二章

同余方程...............................................................................................12一、同余性质（剩余系）............................................................................12二、模幂运算................................................................................................14三、模逆运算................................................................................................16四、一次同余方程求解................................................................................18第三章原根计算.................................................................................................26一、阶、原根、指数....................................................................................26二、阶的计算................................................................................................30三、原根的计算............................................................................................32四、综合........................................................................................................36第四章二次剩余.................................................................................................38第五讲

群...........................................................................................................49一、群的概念................................................................................................49二、循环群的生成元求解(可求原根).........................................................49三、子群及其陪集........................................................................................50四、置换群上的计算....................................................................................53五、群同态....................................................................................................54第六章

环的性质...............................................................................................55一、环的概念................................................................................................55二、商环........................................................................................................57第七章

域上计算...............................................................................................58第一章带余除法重点概念：最大公因子、辗转相除法、标准分解式重点内容：用辗转相除法求解最大公因子及其表示。一、整数的最大公因子及其表示1.(288，392)＝

8

，2.设a=1435,b=3371，计算(a,b)。答：3371=2?1435+5011435=2?501+433501=433+68433=6?68+2568=2?25+1825=18+718=2?7+47=4+34=3+13=3?1所以(1435,3371)=13.用辗转相除法求整数x，y，使得1387x-162y=(1387,162)。答：用辗转相除法，如下表计算：x-yx-yq138710162018911-8171-191202-17311-760199-7712-161374173-625x=73，y=625,(1387,162)=1.4.计算：(27090,21672,11352)。答：(27090,21672,11352)=(4386,10320,11352)=(4386,1548,2580)=(1290,1548,1032)=(258,516,1032)=(258,0,0)=258。5.用辗转相除法计算以下数组的最大公因子。(1)(1046,697)(2)(20301044)解：(1)104616973496971349348349=1?348+1348=348?1因此(1046,697)=1(2)

2030=1?1044+9861044=1?986+58986=17?58因此(20301044)=586.用辗转相除法计算以下数组的最大公因子(1)(2104,2720,1046)(2)(27090,21672,11352)解：(1)先求出(2104,2720)的公因子d1，再求(d1,1046)的公因子d2，d2即为最终要求的公因子。因此：2720=1?2104+6162104=3?616+256616=2?256+104256=2?104+48104=2?48+848=6?8因此(2104,2720)=8，再求(8,1046)，1046=130?8+6，，，，8=1?6+26=3?2因此(2104,2720,1046)=2(2)先求出(27090,21672)的公因子d1，再求(d1,11352)的公因子d2，d2即为最终要求的公因子。因此：27090=1?21672+541821672=4?5418因此(27090,21672)=5418，再求(5418,11352)，11352=2?5418+5165418=10?516+258516=2?258因此(27090,21672,11352)=2587.用辗转相除法求以下数组的最大公因子，并把它表示为这些数的整系数线性组合。(1)1387,162(2)2046,1620解：(1)用列表法可求出(1387,162)的公因子及相应的系数组合，如表1所示：表1求(1387,162)的公因子及相应系数u

v

q1387

1

01629171201192

01-12-79-16

1-89-1760-77137

81131141

73

-625

20由上表可得：(1387,162)=1=1387?73+162?(-625)。(2)用列表法可求出(2046,1620)的公因子及相应的系数组合，如表2所示：表2求(2046,1620)的公因子及相应的系数组合u

v

q2046

1

01620426342846

01-34-19

1-14-524

1314140由上表可得：(2046,1620)=6=1387?(-19)+162?24。8.计算4389，5313，399的最大公因子，并把它表示为这些数的整系数线性组合。解：先求4389与5313的最大公因子，如下表3，公因子为213。再求213与399的最大公因子，如表4，公因子为21。表3求4389与5313的最大公因子

表4求213与399的最大公因子u

v

q

u

v

q5313

1

0

399

1

04389924693231

01-45

1-15-6

1413

2311686342

01-13

1-12-5

11210

21

-4

7

20又由表3、4可分别得到如下两式：231=5313?5+4389?(-6)21=399?(-4)+231?7

(1)(2)将（2）式的231用（1）式等式右边代替并化解可得如下式：21=399?(-4)+5313?35+4389?(-42)所以得到4389，5313，399的最大公因子为21，及其相应系数组合为-42，35，-4。二、多项式的最大公因子及其表示1、求有理数域上多项式的最大公因式(f(x),g(x))，其中f(x)=x5+x4+x2+2x+1,g(x)=x4+x3+x2+2x+1.答：用辗转相除法计算如下x5+x4+x2+2x+1=x(x4+x3+x2+2x+1)-x3-x2+x+1x4+x3+x2+2x+1=-x(-x3-x2+x+1)+(2x2+3x+1)-x3-x2+x+1=

12

x(2x2+3x+1)+

3x344843x33344因此(f(x),g(x))=x+12、求有理数域上多项式的最大公因式(f(x),g(x))，并计算u(x),v(x)，使得(f(x),g(x))=u(x)f(x)+v(x)g(x)，其中f(x)=x5+x3+x2+1,g(x)=x4+x2+x-1.答：由列表法可求出(f(x),g(x))的公因子及相应系数组合，如表5所示：表5求(f(x),g(x))的公因子及相应的系数组合u(x)

v(x)

q+2x2+3x+1=+2x2+3x+1=(x+)(+)=(2x+1)(x+1)x5+x3+x2+1

1

0x4+x2+x-1x+1

01

1-x

xx3-x2+2x-10因此(f(x),g(x))=x+1=(1)(x5+x3+x2+1)+(-x)(x4+x2+x-1)m(x)=1v(x)=-x3、求二元域上多项式的最大公因式(f(x),g(x))，其中f(x)=x5+x3+x2+1,g(x)=x4+x2+1.答：用辗转相除法计算如下x5+x3+x2+1=x(x4+x2+1)+x2+x+1x4+x2+1=(x2+x+1)(x2+x+1)因此(f(x),g(x))=x2+x+14、f(x),g(x)?F2[x]且有f(x)=x6+x5+x4+x3,g(x)=x5+x2+x+1.求m(x)和n(x)，使得(f(x),g(x))=m(x)f(x)+g(x)n(x)。答：由列表法可求出(f(x),g(x))的公因子及相应系数组合，如表6所示：表6求(f(x),g(x))的公因子及相应的系数组合u(x)

v(x)

qx6+x5+x4+x3

1

0x5+x2+x+1

0

1

x+1x4+1x2+1

1x

x+1x2+x+1

xx2+10因此(f(x),g(x))=x2+1=x(x6+x5+x4+x3)+(x2+x+1)(x5+x2+x+1)m(x)=xv(x)=x2+x+15.求有理数域上多项式的最大公因式（f(x),g(x)），其中f(x)=x5+x4+x2+2x+1,g(x)=x4+x3+x2+2x+1.答：(f(x),g(x))=x+1。6.求有理数域上多项式的最大公因式（f(x),g(x)），并计算u(x),v(x)，使得(f(x),g(x))=u(x)f(x)+v(x)g(x)，其中f(x)=x5+x3+x2+1,g(x)=x4+x2+x-1.答：x+1=f(x)-xg(x)。三、标准分解和最小公倍数1.[288，392]＝14112

。2．12600的标准分解式是_

2332527

。3.547是_

___.（填“素数”或“合数”）。3528的标准分解式是_2^3*3^2*7^2___。4.计算以下数组的最小公倍数。(1)[1046,697](2)[20301044](3)[195,72,90](4)[2104,2720,1046]，，解：(1)由第2题计算得(1046,697)=1，因此[1046,697]=1046?697=729062。(2)由第2题计算得(20301044)=58，因此[20301044]=2030?1044?58=36540。(3)由辗转相除法可计算得(195,72,90)=3，因此[195,72,90]=195?72?90?3=4680(4)由第3题计算得(2104,2720,1046)=2，因此[2104,2720,1046]=2104?2720?1046?2=374133280。5.求正整数a,b，使得a+b=120,(a,b)=24,[a,b]=144。答：由a+b=120及ab=(a,b)[a,b]=24?144=3456解得a=48b,=a=72,b=48。6.设a,b是正整数，证明：(a+b)[a,b]=a[b,a+b]。

7或2答：只须证(a+b)

abb(a+b)(a,b)(b,a+b)

，即只须证(b,a+b)=(a,b)此式显然。7.写出下列数的的标准分解式。(1)

22345680(2)166896912(3)22345680解：(1)

22345680=24?3?5?7?47?283。448.判断561与967是否为素数。解：由3|561，所以561不是素数，由2,3,是素数。

967，，=a(2)166896912=2?3?，，=a(2)166896912=2?3?7?13?19?2011。(3)22345680=2?3?5?7?47?283。,殛都不能整除967，所以967四、其他类型题1.证明：若m-p?mn+pq，则m-p?mq+np。答：由恒等式mq+np=(mn+pq)-(m-p)(n-q)及条件m-p?mn+pq可知m-p?mq+np。2.证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。答：在给定的连续39个自然数的前20个数中，存在两个自然数，它们的个位数字是0，其中必有一个的十位数字不是9，记这个数为a，它的数字和为s，则a,a+1,L,a+9,a+19的数字和为s,s+1,L,s+9,s+10，其中必有一个能被11整除。3.设a，b是正整数，证明：(a+b)[a,b]=a[b,a+b]。答：只须证(a+b)

ab(a,b)

=a

b(a+b)(b,a+b)

，即只须证(b,

a+b)=(a,b)，此式显然。4.求正整数a，b，使得a+b=120，(a,b)=24，[a,b]=144。答：由a+b=120及ab=(a,b)[a,b]=24?144=3456解得a=48，b=72或a=72，b=48。5.计算2050与3768的二进制表示和十六进制表示。解：2050的二进制表示：2050=(100000000010)22050的十六进制表示：2050=(802)163768的二进制表示：3768=(111010111000)23768的十六进制表示：3768=(EB8)166.证明6|n(n+1)(2n+1)，其中n为任意整数。证明：n(n+1)(2n+1)=n(n+1)(n-1+n+2)=(n-1)n(n+1)+n(n+1)(n+2)；(n-1),n,(n+1)是连续三个整数，其中必有一个是3的倍数，至少有一个是2的倍数，因此6|(n-1)n(n+1)，同理6|n(n+1)(n+2)，因此6|n(n+1)(2n+1)。7.证明：若m-p|mn+pq，则m-p|mq+np。答：由恒等式mq+np=(mn+

p)q-(

m)p-及qm-p|mn+pq条件可知m-p|m+n。8.证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。答：在给定的连续39个自然数的前20个数中，存在两个自然数，它们的个位数字是0，其中必有一个的十位数字不是9，记这个数为a，它的数字和为s，则a,a+1,L,a+9,a+19的数字和为s,s+1,L,s+9,s+10，其中必有一个能被11整除。第二章同余方程重点内容：同余的性质、完全剩余系、模逆运算、模幂运算（利用欧拉定理进行降幂，再用从右向左或者从左向右算法计算）、一次同余方程求解一、同余性质（剩余系）1.将612-1分解成素因数之积。答：612-1=5?7?13?31?37?43?97。2.①写出完全剩余系和简化剩余系（缩系）的概念，并举例说明（3分）；②写出154440的标准分解式（7分）。3.证明：1978103-19783能被103整除。答：因103=2353，显然1978103-19783?0(mod23)，再由1978100?1(mod53)得1978103-19783?0(mod53)，故1978103-19783?0(mod103)。-(n)-(n)qp4.

证明：对于任意的整数a，(a,561)=1，都有a560?1(mod561)，但561是合数。答案：因561=3?11?17，对于一切整数a，(a,561)=1，有(a,3)=1，(a,11)=1，(a,17)=1，由费马定理可得a560=(a2)280?1(mod3)，a560=(a10)56?1(mod11)，a560=(a16)35?1(mod17)，故a560?1(mod561)。5.一般地，模10的最小非负完全剩余系为{0,1,2,3,4,5,6,7,8,9}；模10的简化剩余系为（或缩系）

{1,3,7,9}。6．一般地，模6的最小非负完全剩余系为

；模6的简化剩余系为（或缩系）

。7．φ(120)-φ(100)＝________。2．φ(100)-φ(72)＝___16_______。8．一般地，模8的最小非负完全剩余系为{0,1,2,3,4,5,6,7}；模8的简化剩余系为（或缩系）{1,3,5,7}。9.写出模15，24的缩系。答：15的缩系为{1,2,4,7,8,11,13,14}；24的缩系为{1,5,7,11,13,17,19,23}。10.求19，27，40的欧拉函数值。答：j(19)=19-1=18；13112511.若(m,n)=1，证明：mj(n)+nj(m)?1(modmn)。证明：可将mn分解列出方程如下：祜mj(n)+nj(m)?0+1?1(modm)镱m+n?1+0?1(modn)

?mj(n)+nj(m)?1(modmn)12.证明：对于任意正整数m有

?d|m,d>0

f(d)=m。?j(n)j(m)?j(n)j(m)证明：当n=1时，?f(d)=1，设n=p1ad|n

pka，则?f(d)=?f(d1)d|n

?dk1|pkk

f(dk)=[1+(p1-1)+

+(p1a1-p1a1-1)][1+(pk-1)+

+(pkak-pkak-1)]=p1a1

pkak=n。13.设m与n是正整数，证明：j(mn)j((m,n))=(m,n)j(m)j(n)。证明：设m=p1a1

pkakm1，n=p1b1

pkbkn1，pi

/m1，pi/n1，(m1,n1)=1，则11

pak+bkm1n1)=pa1+b1

ki=1

1pi

)f(m1)f(n1)，11

ki=1

1pi

)，由此得ki=1

1pi

)f(m1)pbki=1

1pi

)f(n1)=(m,n)j(m)j(n)。14证明：70!?61!(mod71)。证明：由题得只需证明7?0-(9?8??1)?，因此得证。71)

6?9?

6?2

1，(即mod71)二、模幂运算242.求313159被7除的余数。答：313159=6(mod7)。3.简述一种简便模幂运算（从右向左或从左向右计算）的思路。（10分）5134.欧拉函数j(7)=

6

10

mod7。2005年7月26日是星期二，问此天后第21000天是星期几？d1|p11||pkak+bk?(1-k1pkmin{ak,bk})=(m,nd1|p11||pkak+bk?(1-k1pkmin{ak,bk})=(m,n)?(1-pka?(1-pkb?(1-11(mod1.写出欧拉定理和费马小定理（3分），用这两个定理计算5mod21（7分）。至少用两种方法计算79(mod315)。（共20分），利用欧拉定理计算1010=4解

依题意，我们需要求21000mod7，即整数21000模7的最小非负剩余。因10003333因此，第21000天是星期四。5.3408写成十进制时的最后两位数是61

。6．运用从左向右（或从右向左）的算法计算：2567mod61。答案：(2,61)=1，j(61)=60,567=60?9+27，56727用从左向右计算方法，有27的二进制表示11011，列表格计算如下：5677.用欧拉定理求下列模幂运算。246

mod8答：

1851

mod15(1)(2)

j(8)=4，因此3246?3246(mod4)?32?1mod8。j(15)=8，因此51851?51851(mod8)?53?5mod15。解答：

1025

mod15根据a

f(m)

?1(modm)计算得出31025?3(mod15)9.用快速算法求下列模幂运算。33ikiiki312^2×2=8208^2=3113^2×2=180118^2×2=38为23mod7=1，所以2mod7为23mod7=1，所以2mod7=(2999?2)mod7=((2)mod7?2mod7)mod7=2，所以2mod61=2mod61，2mod61=38(1)3(2)58.计算3(1)13mod4758答：(1)33的二进制表示：100001(2)58的二进制表示：111010三、模逆运算1、求35(mod41)的乘法逆元。-1393539?34(mod41)。2、求23(mod1800)的乘法逆元。答：利用扩展欧几里德辗转相除法列表计算如下：v

q1800

0ikix40213≡28ikix40213≡2830228≡3220232≡3710237≡60126×13≡45iikix41211×11≡5831258×11≡2020220≡6511265×11≡4400244≡60(2)11mod67(2)11mod67答：35(mod41)?35j(41)-1?35(mod41)，利用模幂快速算法可计算得23651

1-78235-313

783150因此23-1?-313?1487(mod1800)。3、求11(mod26)的乘法逆元解答：26=11?2+44=26-11?211=4?2+33=11-4?2=11-（26-11?2）?2=-2?26+5?114=3?1+11=4-3?1=（26-11?2）-（-2?26+5?11）?1=3?26-7?11-14、求5(mod14)的乘法逆元解答：14=5?2+45=4+11=5-4=5-（14-5?2）=5?3-14即5?3=14?1+15、用欧几里得算法计算1234mod4321的乘法逆元解答：QX1X2X3Y1Y2Y31043210112343011234QX1X2X3Y1Y2Y310432101123430112341-361911-3619-146151-146152-741532-74-307107541-30710752309-10821即11(mod26)即11(mod26)?-7(mod26)?19?5(mod14)?34321-1082=3239-1解答：由欧拉定理，有15?73?343(mod17)?73?3(mod17)?715?5(mod17)?715?5(mod17)。∴7-1?5(mod17)。四、一次同余方程求解1．同余方程15x≡12(mod99)关于模99的解是___14\47\80________。2.解同余方程：(1)6x?2(mod9)；(2)31x?5(mod17)；(3)3215x?160(mod235)。答：(1)因为(6,9)=3/|2，因此同余式6x?2(mod9)无解；(2)由(31,17)=1，因此x?(31)-1?5(mod17)x?11?5(mod17)x?4(mod17)(3)由(3215,235)=5|160，因此方程有5个解，先求一个解：643x?32(mod47)x?(643)-1?32(mod47)x?25?32(mod47)x?1(mod47)因此，5个解为xi?1+47i(mod235),i=0,1,2,

,43.

解同余方程组：6、计算7mod1776、计算7mod177-1?7(mod17)，其中φ(17)=16?3x?1(mod10)?答：方程可化解为?x?7(mod10)?

?x?1(mod2)??x?0(mod3)?x?b1(mod5)?4.解同余方程组：?镱x?b4(mod11)。答：x?3?462?b1+1?385?b2+1?330?b3+1?210?b4(mod2310)。解同余方程组：?x?2(mod5)??x?4(mod9)答：利用中国剩余定理方程可解得x?157(mod315)?x?8(mod15)??x?13(mod25)。答：方程等价为?x?2(mod3)??x?13(mod25)利用中国剩余定理解得：x413(mod600)。6.求解同余式组?x?2(mod9)??4x?3(mod7)解因为3-1mod5=2，4-1mod7=2，所以同余式3x?4(mod5)和4x?3(mod7)的解分别为x?3(mod5)和x?6(mod7)，?4x?3(mod15)?x?12(mod15)??x?2(mod5)?4x?3(mod15)?x?12(mod15)??x?2(mod5)?x?27(mod30)??x?b2(mod6)?x?b3(mod7)?x?3(mod7)5.解同余方程组：?x?5(mod8)?x?5(mod8)?3x?4(mod5)????因此求解原同余式组等价于求解同余式组?x?2(mod9)??x?6(mod7)m1=9,m2=5,m3=7，M1=35,M2=63,M3=45，利用乘法逆元素的性质可以分别计算M1?,M2?,M3?为M1?=M1-1mod9=35-1mod9=8；M2?=M2-1mod5=63-1mod5=2；M3?=M3-1mod7=45-1mod7=3-1mod7=5，从而同余式组的解为x?35?8?2+63?2?3+45?5?6(mod315)，即x?560+378+1350?83(mod315)。?x?2(mod7)??x?11(mod15)?x?2(mod7)?x?5(mod9)答案：方程组等价于?镱x?11(mod5)

，?x?1(mod5)??x?5(mod9)m=5?7?9=315，M1=63,M1-1?2mod5;M2=45,M2-1?5mod7;M3=35,M3-1?8mod93i=1=63?2?1+45?5?2+35?8?5(mod315)=86(mod315)?x?3(mod5)7.解同余方程组?2x?x?3(mod5)7.解同余方程组?2x?10(mod18).???x?2(mod3)即等价于?x?2(mod7)x??Mi-1Mibi(modm)??3x+5y?38(mod47)?x-y?10(mod47)?3x+5y?38(mod47)?x-y?10(mod47)

35x1-1y10-1?y??1-1??10??r+r?1-101??3510??081-3?+?016-18??016-18??x??6-17??38??11??y??6-1810??1?9.已知单表仿射加密变换为：c≡7m＋5（mod26），其中m表示明文，c表示密文；试对密文CZDFUHRZP解密。答案：解密变换：m?7-1(c-5)?15c+3(mod26)解密结果为HOWAREYOU。（2）’加密变换c=11m+2(mod26)，试对VMWZ解密。答案：解密变换m=11-1(c-2)(mod26)=19c+14(mod26)c1=21c2=12c3=22c4=25依次代入m1=m2=m3=m4=对应明文：（3）已知Hill密码（C≡MK（mod26））中明文分组长度为2，密钥K为Z26上的一个2阶可逆方阵。假设明文dont所对应的密文为ELNI，求密钥K。答案：明文dont对应Z26中3，14，13，19；密文ELNI对应Z26中4，11，13，8。根据C≡MK（mod26），有K=M-1C(mod26)，即VMWVMWZ211222258．求解同余方程组：?答案：?()()()??38(mod47)?x??8．求解同余方程组：?答案：?()()()??38(mod47)?x??35??38????????(mod47)??r12??-3?r12???3510??1-101??1-101?8-1?r2??r21r??.?1-101??106-17?得??????????(mod47)。?k11??k21

-1?=????(mod26)k22??1319??138??918??411??1311??138??109??1323?10.已知：Hill体制实际上就是仿射密码的一个特例，设n=2,密钥为，英文字母表转换成Z26的整数，若密文为CF，试确定该加密的明文。?2319??(mod26)，加密的明文为ID，即（8，3）。?819?11.设英文字母A，B，C，…，Z分别编码为0，1，2，…，25。已知Hill密码（C≡MK（mod26））?67??38??8?-3

-7??024??024??8

6??1518??1518??-3

-7??66??14

14?3鼬所以，明文M=GOOD。12.已知99?62ab427，求a与b。答：a=2，b=4。补充：1.计算32?9mod10解：由32?9mod10?33?7mod10?34?1mod10又由801=4?200+142.求15(mod26)的乘法逆元k12??314??411?=????(mod26)=??(mod26)k12??314??411?=????(mod26)=??(mod26)解：K-1=?中明文分组长度为2，密钥K=珑鼢，密文为AYPS，求明文M。答案：K－1=珑鼢，C=珑鼢，M=CK－1=珑鼢珑鼢=珑?，?3801=34?100+1=(3)200?3?1?3mod(10)=3(mod10)解：(15,26)=1?存在乘法逆元26=1?15+1115=1?11+411=2?4+34=1?3+1?1=4-3=4-(11-2?4)=3?4-11=3?(15-11)-11=3?15-4?11=3?15-4?(26-15)=7?15-4?26所以15(mod26)的乘法逆元为73.求11(mod26)的乘法逆元解：(11,26)=1?存在乘法逆元26=1?11+411=2?4+34=1?3+1?1=4-3=4-(11-2?4)=3?4-11=3?(26-2?11)-11=3?26-7?11又-7?19(mod26)?11(mod26)的乘法逆元为194.求同余方程9x?12(mod15)的解解:gcd(9,15)=3?a'=

91512334==3,m'==5,b'==4又由3-1?2(mod5)?x?2?4+k?5(mod15),k=0,1,2?同余方程9x?12(mod15)的解为8,13,35.求解下列一元一次同余方程(1)3x?2(mod7)(2)9x?12(mod15)(3)7x?1(mod31)(4)20x?4(mod30)(5)17x?14(mod21)(6)64x?83(mod105)(7)128x?833(mod1001)(8)987x?610(mod1597)(9)57x?87(mod105)(10)49x?5000(mod999)解：(1)x?3(mod7)(2)x?3(mod5)(3)x?9(mod31)(4)none(5)x?7(mod21)(6)x?62(mod105)(7)x?812(mod1001)(8)x?1596(mod1597)(9)x?31(mod35)(10)x?836(mod999)6.求解下列一元一次同余方程组(1)x?1(mod4),x?2(mod3),x?3(mod5);(2)x?4(mod11),x?3(mod17);(3)x?2(mod5),x?1(mod6),x?3(mod7),x?0(mod11);(4)3x?1(mod11),5x?7(mod13);(5)8x?6(mod10),3x?10(mod17);(6)x?7(mod10),x?3(mod12),x?12(mod15);(7)x?6(mod35),x?11(mod55),x?2(mod33).解：(1)利用中国剩余定理，x?53(mod60)；(2)利用中国剩余定理，x?37(mod60)；(3)利用中国剩余定理，x?1837(mod2310)；?x?4(mod11)(4)原式化为：?利用中国剩余定理，x?4(mod143)；?x?2(mod5)(5)原式化为：眍x?9(mod17)利用中国剩余定理，x?77(mod85)；?x?2(mod5)??x?0(mod3)利用中国剩余定理，x?27(mod60)；?x?1(mod5)(7)原式化为：?x?0(mod11)?镱x?2(mod3)矛盾，方程组无解。7.把同余方程化成同余方程组来解：(1)23x?1(mod140)(2)17x?229(mod1540)解:(1)140=4?5?7?23x?1(mod4)??23x?1(mod7)4(mod13)x侯(6)原式化为：3(mod4)x喉4(mod13)x侯(6)原式化为：3(mod4)x喉6(mod7)x??镲2(mod11)x??原方程可化为：231(mod5)x喉???x?3(mod4)??x?4(mod7)根据中国剩余定理，x?67(mod140)(2)1540=4?5?7?11?17x?229(mod4)?17x?229(mod5)原方程可化为：?镱17x?229(mod11)?x?1(mod4)?x?2(mod5)化简后得??镱x?7(mod11)根据中国剩余定理，x?557(mod1540)第三章原根计算重点概念：阶、原根、指数重点内容：原根存在性问题和基本计算方法一、阶、原根、指数1.①写出阶、原根、指数的定义（2分）；②求整数13模41的阶ord41(13)（8分）。整数5模17的阶ord17(5)=

16

。2.设整数m=7，这时j(7)=6。计算阶如下：a1a123456ordm(a)136362化简后得??x化简后得??x?2(mod5)?17x?229(mod7)?x?4(mod7)?因此，3，5是模7的原根，但1，2，4，6不是模7的原根。3.设整数m=10=2?5，这时j(10)=4。我们有因此3，7是模10的原根，但1，9不是模10的原根。4.设m>1是整数，a是与m互素的正整数，则存在整数d使得ad?1(modm)成立的充分必要条件是ordm(a)|d。证明：充分性设ordm(a)|d，那么存在整数k使得d=k?ordm(a)，因此，我们有ad=(aordm(a)

k

?1(modm)。必要性如果ordm(a)|d不成立，则由欧几里得除法可知，存在整数q,r，使得d=q?ordm(a)+r,0<r<ordm(a)，从而ar=ar(aordm(a)

q

?ad?1(modm)，这与ordm(a)的最小性矛盾，故ordm(a)|d，证毕。5.求整数5模17的阶ord17(5)。x算得到124816ord17(5)=16。这说明5是模17的原根。6.设m>1是整数，a是与m互素的正整数，s,t是两个正整数。假如ordm(a)=s?t，那么ordm(as)=t。解：(as)t?astmodm?1，所以ordm(as)|t，假设存在0<t'<t，使得ordm(as)=t'，aa1379ordm(a)1442))解：j))解：j(17)=16，16的因子有1,2,4,8,16，将这些因子代入5mod17，依次计5mod17?5,5mod17?8,5mod17?13,5mod17?-1,5mod17?1,所以5模17的阶则有(as)t'?ast'modm?1，即ordm(a)=s?t'<s?t，与题设矛盾，得证。7.设p是一个奇素数，并且

p-12

也是一个奇素数，设a是与p互素的正整数，如果p-1则a是模p的原根。

a?1,a2?1,a

2

?1(modp)，证明：

由推论4-1知道ordp(a)|j(p)，因为a?1,a2?1,a

p-12

?1(modp)，，因为p是一个奇素数，并且也是一个奇素数，所22p-12的原根。8.设a-1modm为a关于模m的乘法逆元素，则ordm(a-1modm)=ordm(a)；d-1ordm(a-1modm)=ordm(a)。9.1=a0,a,a2,L,aord(a)-1模m两两不同余，特别地，当a是模m的原根，即ordm(a)=j(m)时，这j(m)个数组成模m的简化剩余系；证明：首先，两个集合中元素个数相同；其次，因为当a是模m的原根，所以二者互素，即1=a0,a,a2,L,aord(a)-1都和m互素，且模m不同余。所以两个集合等价。10.ad?ak(modm)的充分必要条件是d?k(modj(m))；？？？证明：利用反证法证明必要性，充分性显然。11.ordm(ad)=

ordm(a)(ordm(a),d)

,d?0，进一步，如果g是模m的原根，则gd是模m的原根的充分必要条件是(f(m),d)=1；证明：设r=(ordm(a),d)，ordm(ad)=n，那么(ad)n=adn=1，根据定理1有ordm(a)|dn，因此

|rr

ordm(a)drr

ordm(a)r

|n。所以ordp(a)=/1,2,p-1p所以ordp(a)=/1,2,p-1p-1,p-1，从而ordp(a)=j(p)=p-1，即a是模p以j(p)只有四个正因数1,2,证明：对于任意整数d，总有(a-1)modm=(ad)modm式子成立，所以ordm(a)dn，又因为(,)=1，因此显然有(ad)

ordm(a)r

=1，根据定理1有n|

ordm(a)r

。因此ordm(ad)=

ordm(a)(ordm(a),d)

。如果g是模m的原根，ordm(g)=j(m)，此时有gd是模m的原根?ord(gd)=

j(m)(j(m),d)

=j(m)?(j(m),d)=1。12.如果模m存在一个原根g，则模m有j(j(m))个不同的原根；证明：由性质（5）可得。13.如果(a,m)=1,(b,m)=1，则(ordm(a),ordm(b))=1的充分必要条件是ordm(ab)=ordm(a)?ordm(b)；证明：根据定理1，可得(a)?ord(b)ord(ab)当ordm(b)|ordm(ab)ordm(a)时，(ordm(a),ordm(b))=1?ordm(b)|ordm(ab)，同理可证，当ordm(a)|ordm(ab)ordm(b)

时，(ordm(a),ordm(b))=1?ordm(a)|ordm(ab)，命题得证。14.若n|m，则ordn(a)|ordm(a)；证明：因为aord(a)=1modm，因此m|aord(a)-1，又因为n|m，存在正整数q，使得m=nq，因此nq|aord(a)-1，因此n|aord(a)-1，因此aord(a)=1modn，再根据定理1即得ordn(a)|ordm(a)。15.若(m,n)=1，则ordmn(a)=[ordm(a),ordn(a)]；证明：因为aord(a)=1modm,aord(a)=1modn，因此a[ord(a),ord(a)]=1modm，(a),ord(a),ord定理1，有ordmn(a)|[ordm(a),ordn(a)]。因为aord(a)=1modmn，且(m,n)=1，因此aord(a)=1modm，aord(a)=1modn，因此ordm(a)|ordmn(a),ord(a)|ord(，=aord(a)?ord=aord(a)?ord(b)(a)?ordabordbord(b)=1?ordm(ab)|ordm(a)?ordm(b)又(ab)=1?(ab)ord(ab)ord(a)=bord(ab)ord(a)=1?ordmmm(a)(b)|ord(ab)orda[ord(a)]=1modn，又因为(m,n)=1，因此有a[ord(a)]=1modmn，根据nmna)因此[ordm(a),ordn(a)]|ordmn(a)。命题得证。16.(1)若(m,n)=1，(a1,mn)=1，(a2,mn)=1，则存在整数a，使得ordmn(a)=[ordm(a1),ordn(a2)]；(2)若(a,m)=1,(b,m)=1，则存在整数c，使得ordm(c)=[ordm(a),ordm(b)]。证明：对于整数ordm(a)和ordm(b)，存在整数u,v，满足：u|ordm(a)，v|ordm(b)，(u,v)=1，使得uv=[ordm(a),ordm(b)]，现在令s=

ordm(a)u

，t=

ordm(b)v

，有ordm(as)=

ordm(a)(ordm(a),s)

=u，ordm(bt)=

ordm(b)(ordm(b),t)

=v，ordm(asbt)=ordm(as)?ordm(bt)=uv=[ordm(as),ordm(bt)]，因此，取c?asbt(modm)即为所求。17.设整数m=21=3?7，这时j(21)=12。我们有因此，模21没有原根。然后给出原根存在的一个充分必要条件：二、阶的计算1.计算阶ord18(5)和ord17(5)。a12a1245810111316171920ordm(a)163626623662答案：j(1=8)，66

的因子有

1,2,3,6，计算52

3

7=,5

6

mod18

1因为j(17)=16，16的正因数为1，2，4，8，16。计算51?5(mod17)，52?8(mod17)，54?13(mod17)，58?-1(mod17)，516?1(mod17)所以ord17(5)=16。2.计算阶ord99(91)。2算2345

，所以ord99(91)=5。3.计算阶ord127(31)。答案：j(127)=126=2?3?21，126的因子有2,3,6,21,42,63，计算2642所以ord127(31)=63。4.计算阶ord128(3)。答案：j(128)=64，64的因子有2,4,8,16,32，计算216所以ord128(3)=32。5.

已知2是模11的原根.（1）求ind（23）,ind（210）.解：a

0

1

2

3

4

5

6

7

8

9mo=d18mod，=所以8ord181(5)7=6,mo=d18mod，=所以8ord181(5)7=6,；51答案：j(99)=j(3)j(11)=60，60的因子有1,2,3,4,5,6,10,12,15,20,30，计91mod99?(-8)2?64,(-8)mod99?(-17),(-8)mod99?37,(-8)mod99?131mod127?72，3mod127?73，3131mod127?122，21mod127?19，3131mod127?107，63mod127?1313mod128?9，4mod128?81，33mod128?65，32mod128?1，3a

1

2

4

8

5

10

9

7

3

6有上表格可得ind（23）=8，ind（210）=5（2）ind

42mod（11-1）的值解：∵42=6?7，且11/|7?6∴ind42?ind7+ind6(mod11-1)即得ind42?16mod(11-1)。三、原根的计算1.设m>1，j(m)的所有不同素因数是q1,q2,L,qk，则g是模m的一个原根的充分必要条件是j(m)g

qi

?1(modm),i=1,2,L,k。证

必要性

若g是模m的一个原根，则ordm(g)=j(m)，但是0<

j(m)qi

<j(m)，故g

j(m)qi

?1(modm),i=1,2,L,k成立。j(m)充分性

若条件g

qi

?1(modm),i=1,2,L,k成立，假设ordm(g)<j(m)，由阶的性质可以知道ordm(g)|j(m)，所以

j(m)ordm(g)

是大于1的正整数，所以存在j(m)的某个素因数qi，使得qi|

j(m)ordm(g)

，即存在整数s使得

j(m)ordm(g)

=qis，即所以

j(m)qij(m)

=ordm(g)?s，g

qi

?1(modm)，与假设条件矛盾。所以ordm(g)=j(m)，即g是模m的一个原根。2.求模41的所有原根。解因为j(41)=40=23?5，所以40的素因数为2，5，而40/2=20，40/5=8，2(mod)112(mod)11由原根定义只需验证g8,g20模41是否为1即可，逐个计算可得：28mod41=10,220mod41=1，38mod41=1，48mod41=18,420mod41=158mod41=18,520mod41=168mod41=10,620mod41=40故6是模41的原根。根据性质(5)和(6)，当(d,j(41))=(d,40)=1时，6d是模41的原根，当d遍取40的一个简化剩余系时，6d遍历模41的所有原根，所以模41的所有原根为61mod41=6,611mod41=28,621mod41=35,631mod41=13,

63mod41=11,613mod41=24,623mod41=30,633mod41=17,

67mod41=29,617mod41=26,627mod41=12,637mod41=15,

69mod41=19,619mod41=34,629mod41=22,639mod41=7.3.求模m=412=1681的原根。解因为6是模41的一个原根，所以根据推论1的证明过程，可知6或者6+41=47是模1681的原根，事实上，我们有640mod412=143，641?20mod412=1106，641?8mod412=903；4740mod412=1518，4741?20mod412=83，4741?8mod412=370；所以6和47都是模1681的原根，它们也都是41a的原根。4.设m=2?412=3362，求模m的原根。解应用推论2可知6+1681=1687和47都是模3362的原根。5.证明：设a对模数奇素数p的阶为d，d<p-1，则al，l=1,2,3,是p的原根。

,d都不证明：因为al(l=1,2,3,,d)对模数p的阶为

d(l,d)

?d<p-1，所以al(l=1,2,3,,d)都不是p的原根。6.设a对模m的阶为l，an?1(modm),n?0，则l|n。证明：如果结论不成立，则必有两个整数q,r，使n=ql+r,0<r<lql7.设a对模m的阶为l，则1,a,a2,

,al-1对模数m两两不同余。证明：如果结论不成立，则有某对正整数j,k,0?j<k?l-1，使aj?ak(modm),则有ak-j?1(modm),而0<k-j?l-1，这与a对模m的阶为l矛盾。8.模19的原根。答案：j(19)=18=2?3?3，所以j(19)的素因数只有2，3，而1818=9,23

=6由原根定义只需验证g9,g6模19是否为1即可，逐个计算可得：68故2是模19的原根。根据性质（5）和（6），当(d,f(19))=(d,18)=1时，2d是模19的原根，当d遍取19的一个简化剩余系时，2d遍历模19的所有原根，所以模19的所有原根为21=2mod19，25=13mod19，27=14mod19，211=15mod19，213=3mod19，217=10mod19。9.求模59的原根。答案：229i而1?an?aql+而1?an?aql+r?aar?ar(modm)，这就和l的定义相违背。2mod19=7,2mod19=9余原根2mod59,(i,58)=1，共有j(58)=28个。10.求模61的原根。答案：j(61)=60=2?2?3?5，所以60的素因数为2，3，5，而60/2=30，60/3=20，60/5=12由原根定义只需验证g12,g20,g30模61是否为1即可，逐个计算可得：12