2020初等数论期末考前突击题库及高频考题答案

2020初等数论期末考前突击题库及高频考题答案

一、单项选择题（共10题，每题2分）1.若整数a满足a≡5(mod7)且a≡3(mod11)，则amod77等于A.38B.47C.59D.682.设p为素数，则模p的原根个数为A.p−1B.φ(p−1)C.pD.13.下列同余式中无解的是A.x²≡1(mod8)B.x²≡2(mod7)C.x²≡0(mod9)D.x²≡3(mod5)4.若gcd(a,35)=1，则a^12mod35等于A.1B.aC.a^6D.无法确定5.设n>1，则n为素数的充要条件是A.φ(n)=n−1B.φ(n)=nC.τ(n)=2D.σ(n)=n+16.Legendre符号(6/11)的值为A.1B.−1C.0D.27.若p≡3(mod4)为素数，则(−1/p)等于A.1B.−1C.0D.28.设m=2^4·3^2·5，则φ(m)等于A.32B.48C.64D.969.若a≡b(modm)且d|m，则A.a≡b(modd)B.a≡b+d(modm)C.a≡b(modmd)D.a≡b+1(modd)10.最小的奇素数p使得10为模p二次剩余的是A.3B.7C.11D.13二、填空题（共10题，每题2分）11.若x≡2(mod5)且x≡4(mod9)，则xmod45=________。12.模17的所有原根之和mod17=________。13.若p=23，则(3/p)+(5/p)=________。14.设n=140，则φ(φ(n))=________。15.若a=37，则a^−1mod101=________。16.若x²≡7(mod27)有解，则最小正整数解x=________。17.若p为素数且p|a²+b²，但p∤a，则pmod4=________。18.若m=24，则模m的既约剩余系中元素个数为________。19.若a≡5(mod12)，则a^2mod144=________。20.若p=31，则2^(p−1)modp²=________。三、判断题（共10题，每题2分，正确打“√”，错误打“×”）21.若gcd(a,m)=1，则a^{φ(m)}≡1(modm)。22.对任意奇素数p，(2/p)=1当且仅当p≡±1(mod8)。23.若m>2，则模m的原根一定存在。24.若a≡b(modm)，则a^k≡b^k(modm)对任意正整数k成立。25.若p为素数，则x²≡−1(modp)有解当且仅当p≡1(mod4)。26.若n为无平方因子数，则μ(n)=±1。27.若p≡1(mod3)，则3是模p的二次剩余。28.若a≡b(modm)且c≡d(modm)，则a+c≡b+d(mod2m)。29.若m=2^k，k≥3，则模m无原根。30.若p为素数，则φ(p^k)=p^{k−1}(p−1)。四、简答题（共4题，每题5分）31.叙述中国剩余定理并给出构造性证明思路。32.写出Euler准则并说明其在判断二次剩余中的作用。33.解释为何模2^k(k≥3)不存在原根。34.给出Mobius反演公式并举例说明其用途。五、讨论题（共4题，每题5分）35.讨论RSA公钥密码体系中Euler定理如何保障解密正确性。36.比较Solovay–Strassen与Miller–Rabin素性测试的数论基础差异。37.探讨二次互反律在计算Legendre符号时的算法优势。38.分析素数定理与φ函数渐近估计在密码学参数选取中的意义。答案与解析一、1C2B3D4A5A6B7B8C9A10B二、11381281301416152716131711881925201三、21√22√23×24√25√26√27×28×29√30√四、31.中国剩余定理：设m1,…,mk两两互素，则同余组x≡ai(modmi)有唯一解modM=∏mi。构造：令Mi=M/mi，求ti使Miti≡1(modmi)，则x=∑aiMitimodM。32.Euler准则：奇素数p，a与p互素，则(a/p)≡a^{(p−1)/2}(modp)。可直接计算右边是否≡±1判断二次剩余。33.模2^k(k≥3)的既约剩余系为{奇数}，其阶均为2^{k−2}，无元素阶达φ(2^k)=2^{k−1}，故无原根。34.Mobius反演：若f(n)=∑d|ng(d)，则g(n)=∑d|nμ(d)f(n/d)。例：用μ反演由σ=id1求出id=σμ。五、35.RSA中ed≡1(modφ(n))，由Euler定理得m^{ed}≡m(modn)，保障解密。36.Solovay–Strassen基于Euler准则与Jacobi符号，Miller–Rabin利用强伪素数及2^k分解，后者误差更指数级下降。