2024年1月4日发(作者：一九年贵州中考数学试卷)
信息安全数学基础习题答案
第一章 整数的可除性
1．证明：因为2|n 所以n=2k , kZ
5|n 所以5|2k ， 又（5，2）=1，所以5|k 即k=5 k1 ，k1Z
7|n 所以7|2*5 k1 ,又（7，10）=1，所以7| k1 即k1=7 k2，k2Z
所以n=2*5*7 k2 即n=70 k2, k2Z
因此70|n
32．证明：因为a-a=(a-1)a(a+1)
3 当a=3k，kZ 3|a 则3|a-a
3 当a=3k-1，kZ 3|a+1 则3|a-a
3 当a=3k+1，kZ 3|a-1 则3|a-a
3 所以a-a能被3整除。
3．证明：任意奇整数可表示为2 k0+1， k0Z
22 （2 k0+1）＝4 k0+4 k0+1=4 k0 (k0+1)+1
由于k0与k0+1为两连续整数，必有一个为偶数，所以k0 (k0+1)=2k
2 所以（2 k0+1）=8k+1 得证。
34．证明：设三个连续整数为a-1,a,a+1 则(a-1)a(a+1)= a-a
3 由第二题结论3|（a-a） 即3|(a-1)a(a+1)
又三个连续整数中必有至少一个为偶数，则2|(a-1)a(a+1)
又（3，2）=1 所以6|(a-1)a(a+1) 得证。
5．证明：构造下列k个连续正整数列：
(k+1)！+2, (k+1)！+3, (k+1)！+4,……, (k+1)！+(k+1), kZ
对数列中任一数 (k+1)！+i=i[(k+1)k…(i+1)(i-1)…2*1+1], i=2,3,4,…(k+1)
所以i|(k+1)！+i 即(k+1)！+i为合数
所以此k个连续正整数都是合数。
1/26．证明：因为191＜14 ,小于14的素数有2，3，5，7，11，13
经验算都不能整除191 所以191为素数。
1/2 因为547＜24 ,小于24的素数有2，3，5，7，11，13，17，19，23
经验算都不能整除547 所以547为素数。
由737=11*67 ,747=3*249 知737与747都为合数。
8．解：存在。eg：a=6,b=2,c=9
+10．证明：p1 p2 p3|n， 则n= p1 p2 p3k，kN
3 31/3 又p1≤ p2 ≤p3，所以n= p1 p2 p3k≥p1 即p1≤n
2
p1为素数 则p1≥2，又p1≤ p2 ≤p3，所以n= p1 p2 p3k≥2 p2 p3≥2p21/2 即p2≤(n/2) 得证。
1/211．解：小于等于500的所有素数为2，3，5，7，11，13，17，19，依次删除这些素数的倍数可得所求素数：
12．证明：反证法
假设3k+1没有相同形式的素因数，则它一定只能表示成若干形如3k-1的素数相乘。 (3 k1+1)(3 k2+1)=[( 3 k1+1) k2+ k1]*3+1 显然若干个3k+1的素数相乘，得
到的还是3k+1的形式，不能得出3k-1的数，因此假设不成立，结论得证。
同理可证其他。
13．证明：反证法
假设形如4k+3的素数只有有限个，记为p1, p2,…, pn
因为4k+3=4k`-1=4k-1 构造N=4*p1*p2*…*pn-1≥3*p1*p2*…*pn
所以N＞pi (i=1,2,…,n)
N为4k-1形式的素数，即为4k+3的形式，所以假设不成立。
原结论正确，形如4k+3的素数有无穷多个。
28．（1）解：85=1*55+30
55=1*30+25
30=1*25+5
25=5*5
所以(55,85)=5
（2）解：282=1*202+80
202=2*80+42
80=1*42+38
42=1*38+4
38=9*4+2
4=2*2
所以（202,282）=2
29．（1）解：2t+1=1*(2t-1)+2
2t-1=(t-1)*2+1
2=2*1
所以（2t+1,2t-1）=1
（2）解：2(n+1)=1*2n+2
2n=n*2
所以（2n,2(n+1)）=2
32．（1）解：1=3-1*2
=3-1*(38-12*3)
=-38+13*(41-1*38)
=13*41-14*(161-3*41)
=-14*161+55*(363-2*161)
=55*363+(-124)*(1613-4*363)
=(-124)*1613+551*(3589-2*1613)
=551*3589+(-1226)*1613
所以s=-1226 t=551
（2）解：1=4-1*3
=4-1*(115-28*4)
=-115+29*(119-1*115)
=29*119+(-30)*(353-2*119)
=-30*353+89*(472-1*353)
=89*472+(-119)*(825-1*472)
=(-119)*825+208*(2947-3*825)
=208*2947+(-743)*(3772-1*2947)
=951*2947+(-743)*3772
所以s=951 t=-743
36．证明：因为（a，4）=2 所以a=2*(2m+1) mZ
所以a+b=4m+2+4n+2=4(m+n)+4=4(m+n+1)
即4|a+b
所以（a+b,4）=4
37．证明：反证法
22 假设n为素数，则n| a- b=(a+b)(a-b)
由1.4定理2知n|a+b或n|a-b,与已知条件矛盾
所以假设不成立，原结论正确，n为合数。
1/21/240．证明：（1）假设是2有理数，则存在正整数p，q，使得2=p/q,且（p, q）=1
222 平方得：p=2q, 即2|p，所以p=2m, mN
22222 因此p=4m=2q q=2m q=2n, nN
则（p, q）=(2m,2n)=2(m, n)≥2与（p, q）=1矛盾
1/2 所以假设不成立，原结论正确，2不是有理数。
1/21/2 （2）假设是7有理数，则存在正整数m，n，使得7=p/q,且（m, n）=1
222 平方得：m=2n, 即7|m
将m表示成n个素数pi的乘积，m= p1 p2 p3 ……pn
， pi为素数。
因为7为素数，假设7 !| m，则7 !∈｛p1 ，p2，p3 ，……pn｝
2222 2 所以m= p1 p2 p3 ……pn=( p1 p2 p3 ……pn)( p1 p2 p3 ……pn)
22 所以7 !| m，与7|m矛盾，故7|m, m=7k
同理可知：7|n, n=7 k0
所以(m, n)=(7k,7 k0)=7(k, k0)≥7 与已知矛盾
1/2 故原结论正确，7不是有理数。
1/2（3）同理可证17不是有理数。
41．证明：假设log210是有理数，则存在正整数p, q,使得log210=p/q,且（p, q）=1
又log210=ln10/ln2=p/q
qpqp
Ln10=ln2 10=2qpqp-q
(2*5)=2 5=2 所以只有当q=p=0是成立，所以假设不成立
故原结论正确，log210是无理数。
同理可证log37，log1521都是无理数。
3250．（1）解：因为8=2, 60=2*3*5
3 所以[8,60]=2*3*5=120
1111151．（4）解：(4779101,4183101)= 41477983101=101
11111001 [4779101,4183101]= 41477983101
第二章．同余
1．解：（1）其中之一为9，19，11，21，13，23，15，25，17
（2）其中之一为0，10，20，30，40，50，60，70，80
（3）.（1）或（2）中的要求对模10不能实现。
222．证明：当m>2时，因为(m-1)=m-2m+1=m(m-2)+1
2 所以(m-1)≡1(mod m)
2222 即1与(m-1)在同一个剩余类中，故0,1,…,(m-1)一定不是模m的完全剩余系。
1236．解：2≡2(mod7), 2≡4(mod7), 2≡1(mod7)
又20080509=6693503*3
200805093 所以2=(2)6693503≡1(mod7)
20080509 故2是星期六。
7．证明：（i）因为ai≡ bi (modm),1≤i≤k 所以ai=bi+kim
又a1+a2+… +ak=∑ai=∑(bi+kim)=∑bi+m*∑ki
所以有∑ai≡∑bi (mod m)
即a1+a2+… +ak=b1+b2+… +bk (mod m)
（ii）因为ai≡ bi (mod m),1≤i≤k 所以ai(mod m)=bi (mod m)
所以（a1a2…ak）mod m≡[(a1mod m)( a2mod m)…(ak
mod m)]mod m
≡[(b1mod m)( b2mod m)…(bk
mod m)]mod m
≡（b1b2…bk）mod m
所以 a1a2…ak≡a1a2…ak(mod m)
22228．证明：如果a≡b(mod p) 则a= b+kp , kZ
22 即kp=a-b=(a+b)(a-b) 所以p|(a+b)(a-b)
又p为素数，根据1.4定理2知p|a+b或p|a-b 得证。
22229．证明：如果a≡b(mod n) 则a= b+kn , kZ
22即kn=a-b=(a+b)(a-b) 所以n|(a+b)(a-b)
22由n=pq知kpq=a-b=(a+b)(a-b)
因为n!|a-b, n!|a+b，所以p,q不能同时为a-b或a+b的素因数。
不妨设p|a-b, q|a+b ,则q!|a-b, p!|a+b 即(q, a-b)=1,(p, a+b)=1
因此(n, a-b)=(pq, a-b)=(p, a-b)=p>1
(n, a+b)=(pq, a+b)=(q, a+b)=q>1
故原命题成立。
10．证明：因为a≡b (mod c) 则a=cq+b , qZ
根据1.3定理3知(a, c)=(b, c)
17．解：（1）ak+ak-1+… +a0=1+8+4+3+5+8+1=30
因为3|30 ,9!|30 所以1843581能被3整除，不能被9整除。
（2）ak+ak-1+… +a0=1+8+4+2+3+4+0+8+1=31
因为3!|31 , 9!|31 所以184234081不能被3整除，也不能被9整除。
（3）ak+ak-1+… +a0=8+9+3+7+7+5+2+7+4+4=56
因为3!|56 , 9!|56 所以8937752744不能被3整除，也不能被9整除。
（4）ak+ak-1+… +a0=4+1+5+3+7+6+8+9+1+2+2+4+6=58
因为3!|58 , 9!|58 所以46不能被3整除，也不能被9整除。
20．解：（89878*58965）mod9≡[(89878mod9)*(58965mod9)]mod9≡(4*6)mod9
≡6(mod9) ≡5299?56270(mod9)
又5299?56270≡(45+?)mod9≡?(mod9)
所以 ?=6 即未知数字为6。
21．解：（1）因为875961*2753≡[(36mod9)(17mod9)]mod9 ≡0(mod9)
2410520633≡26(mod9) ≡8(mod9)
所以等式875961*2753=2410520633不成立
（2）因为14789*23567≡[(29mod9)(23mod9)]mod9 ≡1(mod9)
348532367≡41(mod9) ≡5(mod9)
所以等式14789*23567=348532367不成立
（3）因为24789*43717≡[(30mod9)(22mod9)]mod9 ≡3(mod9)
1092700713≡30(mod9) ≡3(mod9)
所以等式24789*43717=1092700713可能成立
（4）这种判断对于判断等式不成立时简单明了，但对于判断等式成立时，可能会较复杂。
22．解：因为7为素数，由Wilso定理知：(7-1)! ≡-1(mod7) 即6！≡-1（mod7）
所以8*9*10*11*12*13≡1*2*3*4*5*6(mod7) ≡6!(mod7) ≡-1(mod7)
31．证明：因为c1,c2,…,c(m)是模m的简化剩余系
对于任一ci，有m-ci也属于模m的简化剩余系
所以ci+(m-ci)≡0(modm)
因此c1+c2+…+c(m)≡0(modm)
(m)≡1(modm) 所以a(m)-1≡0(modm) 32．证明：因为a(m)-1=(a-1)(1+a+ a2+…+ a(m)-1) ≡0(modm) a 又（a-1,m）=1
2(m)-1 ≡0(modm) 所以1+a+ a+…+ a33．证明：因为7为素数，由Fermat定理知a ≡a(mod7)
(9)≡a6≡1(mod9) 即a7≡a(mod9) 又（a，3）=1 所以(a,9)=1 由Euler定理知a 又(7,9)=1, 所以a≡a(mod7*9)
7 即a≡a(mod63)
3234．证明：因为32760=2*3*5*7*13 又(a,32760)=1
所以(a,2)=(a,3)=(a,5)=(a,7)=(a,13)=1
(13)≡1(mod13) 即a12≡1(mod13) 有：a(8)≡a4≡1(mod8) 即a12≡1(mod8) a(5)≡a4≡1(mod5) 即a12≡1(mod5) a(7)≡a6≡1(mod7) 即a12≡1(mod7) a(9)≡a6≡1(mod9) 即a12≡1(mod9) a 又因为[5,7,8,9,13]=32760
12 所以a≡1(mod32760)
35．证明：因为(p,q)=1 p,q都为素数 所以(p)=p-1,
(q)=q-1
(q)≡1(modq) q(p)≡1(modp) 由Euler定理知：p 即p≡1(modq) q≡1(modp)
p-1q-1 又 q≡0(modq) p≡0(modp)
q-1p-1p-1q-1 所以p+q≡1(modq) q+p≡1(modp)
q-1p-1 又[p,q]=pq 所以p+q≡1(modpq)
36．证明：因为(m,n)=1
(n)≡1(modn) n(m)≡1(modm) 由Euler定理知：m(n)+n(m)≡(m(n)modn)+ (n(m)modn)≡1+0≡1(modn) 所以m(n)+n(m) ≡1(modm) 同理有：mq-1p-177
又[m,n]=mn 所以m
(n)+n(m) ≡1(modmn)
第三章.同余式
1．（1）解：因为（3，7）=1 | 2 故原同余式有解
又3x≡1（mod7） 所以 特解x0`≡5（mod7）
同余式3x≡2（mod7）的一个特解x0≡2* x0`=2*5≡3（mod7）
所有解为：x≡3（mod7）
（3）解：因为（17，21）=1 | 14 故原同余式有解
又17x≡1（mod21） 所以 特解x0`≡5（mod21）
同余式17x≡14（mod21）的一个特解x0≡14* x0`=14*5≡7（mod21）
所有解为：x≡7（mod21）
2．（1）解：因为（127，1012）=1 | 833 故原同余式有解
又127x≡1（mod1012） 所以 特解x0`≡255（mod1012）
同余式127x≡833（mod1012）的一个特解x0≡833* x0`=833*255≡907（mod1012）
所有解为：x≡907（mod1012）
3．见课本3.2例1
7．（1）解：因为（5，14）=1
由Euler定理知，同余方程5x≡3（mod14）的解为：
(14)-1*3≡9（mod14） x≡5 （2）解：因为（4，15）=1
由Euler定理知，同余方程4x≡7（mod15）的解为：
(15)-1*7≡13（mod15） x≡4 （3）解：因为（3，16）=1
由Euler定理知，同余方程3x≡5（mod16）的解为：
(16)-1*5≡7（mod16） x≡311．证明：由中国剩余定理知方程解为：
x≡a1M1M1`+ a2M2M2`+……+ akMkMk`（mod m）
因为mi两两互素，又中国剩余定理知：MiMi`≡1（mod mi）
又Mi=m/mi 所以（m，Mi）≡1（mod mi）
(mi)≡（mod mi） 所以MiMi`=Mi(m1)+ a2 M2(m2)+……+ ak Mk(mk)(mod m) 得证。 代入方程解为x≡a1 M112．（1）解：由方程组得：3x+3y≡2(mod7)
6x+6y≡4(mod7) x+y≡-4(mod7)
X≡5(mod 7) y≡5 (mod 7)
（2）解：由方程组得：2x+6y≡2(mod7) 2x-y≡2(mod7)
6x+8y≡4(mod7) x-y≡-4(mod7)
X≡6(mod 7) y≡3 (mod 7)
13．见课本3.2例4
100000014．同课本3.2例3 2≡562（mod1309）
15．（1）解：等价同余式组为：
23x≡1（mod4）
23x≡1（mod5）
23x≡1（mod7）
所以 x≡3（mod4） x≡2（mod5） x≡4（mod7）
所以x≡3*35*3 + 2*28*2 + 4*20*6≡67（mod140）
（2）解：等价同余式组为：
17x≡1（mod4）
17x≡1（mod5）
17x≡1（mod7）
17x≡1（mod11）
所以 x≡1（mod4） x≡2（mod5） x≡-3（mod7） x≡7（mod11）
所以x≡1*385*1 + 2*308*2 + (-3)*220*5 + 7*140*7 ≡557（mod1540）
9．解：3x+4x+2x+x+x+x+12x+x≡0（mod7）
776426522 左边=(x-x)( 3x+4x+2x+x+3x+4)+ x+2x+2x+15x+5x
6522 所以原同余式可化简为：x+2x+2x+15x+5x≡0（mod7）
直接验算得解为：x≡0（mod7） x≡6（mod7）
320．解：f`(x) ≡ 4x+7（mod243）
直接验算的同余式f（x）≡0(mod3)有一解：x1≡1（mod3）
3-1 f`(x1) ≡4*1*7=-1(mod3) f`(x1)≡-1(mod3)
-11 所以t1≡-f（x1）*( f`(x1)(mod3))/3≡1(mod 3)
x2≡ x1+3 t1≡4(mod 9)
-12 t2≡-f（x2）*( f`(x1)(mod3))/3≡2(mod 3)
2 x3≡ x2+3 t2≡22(mod 27)
-13 t3≡-f（x3）*( f`(x1)(mod3))/3≡0(mod 3)
3 x4≡ x3+3 t3≡22(mod 81)
-14 t5≡-f（x4）*( f`(x1)(mod3))/3≡2(mod 3)
4 x5≡ x4+3 t4≡184(mod 243)
所以同余式f（x）≡0(mod243)的解为：x5 ≡184(mod 243)
第四章．二次同余式与平方剩余
2．解：对x=0,1,2,3,4,5,6时，分别求出y
2 x=0,y≡1(mod7),y≡1,6(mod7)
2 x=4,y≡4(mod7),y≡2,5(mod7)
当x=1,2,3,5,6时均无解
5．解：对x=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16时，分别求出y
2 x=0,y≡1(mod17),y≡1,16(mod17)
2 x=1,y≡3(mod17),无解
2 x=2,y≡11(mod17),无解
2 x=3,y≡14(mod17),无解
2 x=4,y≡1(mod17),y≡1,16(mod17)
2 x=5,y≡12(mod17),无解
2 x=6,y≡2(mod17),y≡6,11(mod17)
x=7,y≡11(mod17),无解
2 x=8,y≡11(mod17),无解
2 x=9,y≡8(mod17),y≡5,12(mod17)
2 x=10,y≡8(mod17),y≡5,12(mod17)
2 x=11,y≡0(mod17),y≡0(mod17)
2 x=12,y≡7(mod17),无解
2 x=13,y≡1(mod17),y≡1,16(mod17)
2 x=14,y≡5(mod17),无解
2 x=15,y≡8(mod17),y≡5,12(mod17)
2 x=16,y≡16(mod17),y≡4,13(mod17)
(17-1)(37-1)/(2*2)10．解：(1）.（17/37）=(-1)*(37/17)=-1
(2003-1)(911-1)/(2*2) (4）.（911/2003）=(-1)*(2003/911)=1/3=1
(7-1)(20040803-1)/(2*2) (6）.（7/20040803）=(-1)*(20040803/7)=1
12．解：（1）.因为（-2/67）=(65/67)=1
所以-2是67的平方剩余
2 所以x≡-2(mod67)有2个解。
(37*37-1)/8 （4）.因为（2/37）=(-1)=-1
所以2是37的平方非剩余
2 所以x≡2(mod37)无解。
14．证明：（1）因为p为其素数，模p的所有二次剩余个数为(p-1)/2个，
设为a1, a2, a3, …a(p-1)/2
2222则a1*a2*a3…a(p-1)/2≡1*2*3…((p-1)/2)(mod p)
≡1*2*3…((p-1)/2)*(-(p-1))*(-(p-2))*…(-(p-(p-1)/2))(mod p)
(p-1)/2≡1*2*3…((p-1)/2)*(p-(p-1)/2)…*(p-2)*(p-1)(-1)(mod p)
(p-1)/2≡(p-1)!*(-1)(mod p)
(p-1)/2≡(-1)*(-1)(mod p) （2.4定理3）
(p+1)/2≡(-1)(mod p)
(p+1)/2所以模p的所有二次剩余乘积模p的剩余为(-1)得证。
（2）1，2，3,…p-1为p的一个完全剩余系
(p+1)/2(p-1)/21*2*2…*(p-1)≡-1(mod p) ≡(-1)(-1)(mod p)
(p+1)/2因为模p的所有二次剩余乘积模p的剩余为(-1)
(p－1)/2所以模p的所有非二次剩余乘积模p的剩余为(-1)
（3）当p=3时，其二次剩余只有1，所以p=3时，模p的所有二次剩余之和模p
的剩余为1
当p>3时，由（1）得a1+a2+a3…+a(p-1)/2≡p(p-1)(p+1)/24(mod p)
因为p为奇素数，所以p只能取3k-1或3k+1形式，代入上式得0
所以当p>3时，模p的所有二次剩余之和模p的剩余为0。
（4）因为模p的所有二次非剩余之和与所有二次剩余之和的和可以被p整除
所以由(3)得，当p=3时，模p的所有二次非剩余之和模p的剩余为-1;
当p>3时，模p的所有二次非剩余之和模p的剩余为0。
(227-1)(7-1)/(2*2)16．解：(1）.因为（7/227）=(-1)*(227/7)= 1
所以7是227的二次剩余
2 所以x≡7(mod227)有解
(3）.因为11对91的逆元是58
2
所以原同余方程等价于x≡16(mod91)
又16是91的平方剩余
2 所以11x≡-6(mod91)有解
21．证明：应用模重复平方法
013 11=2+2+2
令x=23,b=2,a=1
2 (1)x0=1 a0=a*b≡2(mod23) b1=b≡4(mod23)
2 (2)x1=1 a1=a0*b1≡8(mod23) b2=b1≡16(mod23)
02 (3)x2=0 a2=a1*b2≡8(mod23) b3=b2≡3(mod23)
(4)x3=1 a3=a2*b3≡1(mod23)
1111 所以2≡1(mod23) 即23|2-1
23251 47|2-1与503|2-1 应用同样的方法得证。
2第五章．原根与指标
1．解：因为(13)=12,所以只需对12的因数d=1,2,3,4,6,12,计算a(mod12)
d 因为2≡2, 2≡4, 2≡8, 2≡3, 2≡-1, 2≡1(mod13)
所以2模13的指数为12；
同理可得：5模13的指数为4，10模13的指数为6。
d2．解：因为(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算a(mod12)
因为3≡3, 3≡9, 3≡8, 3≡7, 3≡-1, 2≡1(mod13)
所以3模19的指数为18；
同理可得：7模19的指数为3，10模19的指数为18。
33．解：因为(m)=(81)=54=2*3,所以(m)的素因数为q1=2,q2=3,进而
(m)/q1=27,
(m)/q2=18
这样，只需验证：g,g模m是否同余于1。对2，4，5，6…逐个验算：
2718 因为21(mod81) 21(mod81) 根据5.2定理8得
所以2是模81的原根
stst7．证明：因为（a, m）=1, 故由ordm(a)=st知：a≡1(mod m) 即(a)≡1(mod m)
ssr 不妨令ordm(a)=r 则a≡1(mod m) 所以st|sr
st由(a)≡1(mod m)得r|t 即t＝k*r kN≥1 r≤t 所以sr≤st
所以sr=st 所以r=t
s所以ordm(a)=t
8．解：存在
举例：如n=7,d=3 因为(7)=6 d=3|6
(7)≡1(mod 7) 又23≡1(mod 7) 存在a=2 (2,7)=1, 2 所以ord7(2)=3 满足条件。
10．证明：因为p为一个奇素数，p-1/2也是一个奇素数
所以(p)=p-1=2*(p-1)/2 即(p)的不同素因数为2，p-1/2
(p)/2=ap-1/21(mod p) a(p)/[(p-1)/2]=a21(mod p) 又因为a 根据5.2定理8得a是模p的原根。
2734612
15．证明：反证法
m 假设n是一个合数，令ordn(a)=m 则a≡1(mod n)
n-1 因为a≡1(mod n) 所以由5.1定理1得m|n-1 即n-1=k*m
对n-1的所有素因数q，必可找到一个q1使m|((n-1)/q1)
n-1/qm*t 所以a=a≡1(mod n) 与已知条件矛盾，故假设不成立，原结论得证。
16．解：因为d=(n,(m))=(22,(41))=(22,40)=2 ind5=22
所以(n,(m))|ind5，同余式有解
等价同余式为22indx≡ind5(mod40) 即11indx≡11(mod20)
解得：indx=1,21(mod40)
所以原同余式解为x=6,35(mod41)
17．解：因为d=(n,(m))=(22,(41))=(22,40)=2 ind29=7
(2,7)=1 所以原同余式无解。
第六章．素性检验
1．证明：因为91=13*7是奇合数， (3,91)=1
691-190615 又3=729≡1(mod91) 则3=3≡(3)≡1(mod91)
则91是对于基3的拟素数。
2．证明：因为45=5*3*3是奇合数， (17,45)=1
42 由Euler定理：17≡1(mod5) 17≡1(mod3)
44 所以17≡1(mod3) 所以17≡1(mod45)
45-144411 则17=17≡(17)≡1(mod45)
则45是对于基17的拟素数。
同理45是对于基19的拟素数。
310．证明：25=5*5是奇素数 设n=25 n-1=24=2*3 则t=3 (7,25)=1
32*3 7≡18(mod25) 7≡-1(mod25)
所以25是基于7的强拟素数。
15．证明：n=561=3*11*17 为奇素数 （561,2）=1
(n-1)/2(561-1)/2280 b≡2≡2≡1(mod561)
(561*561-1)/8 (b/n)=(2/561)=(-1)=1
280 所以2≡(2/561)(mod561)
所以561是对于基2的Euler拟素数。
更多推荐
素数,成立,剩余
发布评论