2020年大学初等数论考前密押卷题库及超全答案解析

2020年大学初等数论考前密押卷题库及超全答案解析

一、单项选择题（每题2分，共20分）1.若整数a满足a≡5(mod7)且a≡3(mod11)，则a模77的最小正剩余为A.38B.47C.59D.682.设p为素数，则模p的原根个数为A.p−1B.φ(p−1)C.pD.13.若n>1且2n+1为素数，则n必为A.奇数B.偶数C.素数D.合数4.勒让德符号(6/17)的值为A.1B.−1C.0D.25.若x2≡1(mod24)的解的个数为A.2B.4C.6D.86.设a,b为正整数，则gcd(2a−1,2b−1)=A.2gcd(a,b)−1B.gcd(a,b)C.2gcd(a,b)+1D.17.若p为奇素数，则(−1/p)=A.1B.−1C.0D.p8.同余式x2≡2(mod7)的解的个数为A.0B.1C.2D.39.若n为无平方因子奇数，则φ(n)为偶数的充要条件是A.n>1B.n为素数C.n为合数D.n≡1(mod4)10.设p≡3(mod4)为素数，则−1是模p的A.二次剩余B.二次非剩余C.原根D.单位二、填空题（每题2分，共20分）11.若a≡3(mod7)，则a100模7的剩余为________。12.满足φ(n)=12的最小正整数n为________。13.若p=13，则模p的最小正原根为________。14.设n=2020，则φ(n)=________。15.同余式7x≡5(mod11)的解为x≡________(mod11)。16.若p=17，则(3/p)=________。17.设a=105，则a模11的阶为________。18.若n=2k·3l·5m且φ(n)=288，则k+l+m=________。19.若p≡1(mod4)为素数，则(−1/p)=________。20.设n=561，则n是Carmichael数的依据是对于所有与n互素的a有________。三、判断题（每题2分，共20分）21.若a≡b(modm)且d|m，则a≡b(modd)。22.对于任意奇素数p，2都是模p的原根。23.若gcd(a,m)=1，则aφ(m)≡1(modm)。24.若n>2，则φ(n)必为偶数。25.若p为素数，则xp−x≡0(modp)有p个解。26.若a为模m原根，则a2也是模m原根。27.若p≡3(mod4)，则x2≡−1(modp)无解。28.若n为无平方因子数，则μ(n)2=1。29.若p为素数，则φ(p2)=p2−p。30.若a≡b(modm)，则ka≡kb(modkm)对任意正整数k成立。四、简答题（每题5分，共20分）31.叙述中国剩余定理并给出构造性证明思路。32.说明欧拉函数φ(n)的积性性质并举例验证。33.给出模奇素数p的二次剩余计数公式并推导。34.解释Carmichael数的定义并写出最小一例及其检验方法。五、讨论题（每题5分，共20分）35.讨论原根的存在性条件，并说明为何模2k(k≥3)无原根。36.比较勒让德符号与雅可比符号的异同，并指出计算优势。37.探讨RSA加密中选取的模数n=pq需满足哪些数论条件以保证安全与效率。38.分析素性测试中费马小定理的局限性，并说明Miller-Rabin如何弥补。答案与解析一、单项选择题1.C2.B3.B4.B5.B6.A7.B8.C9.A10.B二、填空题11.212.1313.214.80015.716.−117.1018.719.120.a560≡1(mod561)三、判断题21.√22.×23.√24.√25.√26.×27.√28.√29.√30.×四、简答题31.中国剩余定理：设m1,…,mk两两互素，则对任意整数a1,…,ak，同余组x≡ai(modmi)有唯一解模M=∏mi。构造：令Mi=M/mi，求逆元yi使Miyi≡1(modmi)，则x=∑aiMiyimodM。32.φ(n)积性：若gcd(m,n)=1则φ(mn)=φ(m)φ(n)。例：φ(3)=2，φ(4)=2，φ(12)=4=2×2。33.模奇素数p的二次剩余个数为(p−1)/2。证：取原根g，偶次幂给出剩余，奇次幂给出非剩余，各半。34.Carmichael数：合数n满足对所有(a,n)=1有an−1≡1(modn)。最小例561=3×11×17，检验：验证a560≡1对a=2,5,7等成立。五、讨论题35.原根存在当且仅当模m为2,4,pk,2pk(p奇素)。模2k(k≥3)无原根因乘法群结构为C2×C2k−2，非循环。36.勒让德符号限奇素数p，雅可比符号推广至合数n，保持乘法性，计算免分解，但为1不一定真剩余。37.RSA模数n=pq需p,q大素数且差大，