2020大学初等数论裸考救星题库及考点配套答案

2020大学初等数论裸考救星题库及考点配套答案

一、单项选择题（每题2分，共20分）1.若整数a满足a≡5(mod7)且a≡3(mod11)，则a的最小正整数解为A.38B.61C.82D.1032.设p为素数，则模p的原根个数为A.p-1B.φ(p-1)C.pD.φ(p)3.下列同余式中无解的是A.x²≡1(mod8)B.x²≡2(mod7)C.x²≡0(mod9)D.x²≡3(mod5)4.若gcd(a,m)=1且a^φ(m)≡1(modm)，则称a对模m的阶为A.φ(m)B.最小正整数k使a^k≡1(modm)C.m-1D.15.勒让德符号(6/17)的值为A.0B.1C.-1D.26.设n>1，则n为卡迈克尔数的必要条件是A.n为偶数B.n无平方因子且对一切素因子p有p-1|n-1C.n为素数D.n为2的幂7.若x²≡a(modp^e)有解且p为奇素数，则解的个数为A.0B.1C.2D.48.设m=2^4·3^2·5，则φ(m)等于A.96B.120C.144D.1809.若连分数[2;3,1,4]的渐近分数p₃/q₃为A.30/11B.43/16C.49/18D.53/1910.设θ为无理数，其连分数周期为6，则其二次无理数共轭的周期为A.3B.6C.9D.12二、填空题（每题2分，共20分）11.若a≡b(modm)且c≡d(modm)，则ac≡____(modm)。12.模25下3的阶为____。13.若p为奇素数，则(-1/p)=____。14.设d为无平方因子正整数，则√d的连分数周期必为____数。15.若n=341，则2^(n-1)modn=____。16.若x²≡5(mod23)有解，则解的最小正整数为____。17.设p≡1(mod4)为素数，则∑_{k=1}^{p-1}(k/p)=____。18.若gcd(a,b)=1，则ax≡c(modb)在模b下的解数为____。19.设m=2^k，k≥3，则模m的原根____（填“存在”或“不存在”）。20.若连分数展开[1;2,3,2,3,…]的极限值为x，则x满足的一次方程为____。三、判断题（每题2分，共20分）21.若a≡b(modm)，则a²≡b²(modm²)。22.对任意奇素数p，2均为模p的原根。23.若n为素数，则φ(n)=n-1。24.若x²≡a(modp)无解，则x²≡a(modp²)也无解。25.勒让德符号(a/p)只依赖于amodp。26.若d为无平方因子正整数，则√d的连分数必纯周期。27.若m>2，则φ(m)必为偶数。28.卡迈克尔数必为无平方因子奇合数。29.若a对模m的阶为k，则k|φ(m)。30.若p≡3(mod4)，则-1为模p的二次剩余。四、简答题（每题5分，共20分）31.叙述中国剩余定理并给出唯一性说明。32.写出模素数p下二次剩余的欧拉判别法则并证明其必要性。33.说明原根存在定理中“模2^k无原根”的理由。34.给出连分数渐近分数的最佳逼近性质并简述证明思路。五、讨论题（每题5分，共20分）35.讨论RSA公钥密码中φ(n)的保密性如何依赖于大整数分解困难性。36.比较勒让德符号、雅可比符号与克罗内克符号在计算效率上的差异。37.探讨卡迈克尔数在Fermat素性检验中的“伪证”危害及补救措施。38.分析连分数在求解Pell方程x²-dy²=1中的核心作用并举例说明。答案与解析单选：1B2B3D4B5C6B7C8A9B10B填空：11bd122013(-1)^((p-1)/2)14偶15116717018119不存在20x²-3x-1=0判断：21×22×23√24√25√26×27√28√29√30×31.中国剩余定理：设m₁,…,m_r两两互素，则对任意整数a₁,…,a_r，同余组x≡a_i(modm_i)有解，且解在模M=∏m_i下唯一。唯一性：若x,y均为解，则x≡y(modm_i)对所有i成立，由互素得x≡y(modM)。32.欧拉判别：a^((p-1)/2)≡(a/p)(modp)。必要性：若a为二次剩余，存在x²≡a，则a^((p-1)/2)≡x^(p-1)≡1≡(a/p)。33.模2^k(k≥3)乘法群同构于C₂×C_{2^{k-2}}，非循环，故无单一生成元，即无原根。34.渐近分数p_n/q_n满足|θ-p_n/q_n|<1/(q_nq_{n+1})，且对任意分母≤q_n之分数，p_n/q_n为最佳逼近。证明利用连分数递推与交错不等式。35.若敌手分解n=pq可得φ(n)=(p-1)(q-1)，从而破解私钥d。分解困难则φ(n)保密，RSA安全。36.勒让德需素模，计算用欧拉判别；雅可比可合模，用二次互反，效率高；克罗内克推广到任意整数，符号规则更复杂，计算量最大。37.卡迈克尔数满足a^(n-1)≡1对所有gcd(a,n)=1成立，导致Fermat检验误判。补救：用强伪素数检验(Miller