2022学分认定考试初等数论题库及标准答案

2022学分认定考试初等数论题库及标准答案

一、单项选择题（总共10题，每题2分）1.以下哪个数能被11整除？（）A.123B.121C.125D.1272.gcd(24,36)的值为（）A.6B.12C.18D.243.同余式2x≡4mod6的解数为（）A.1B.2C.3D.44.100以内最大的素数是（）A.91B.93C.97D.995.3在模7下的逆元是（）A.2B.3C.5D.66.欧拉函数φ(12)的值为（）A.2B.4C.6D.87.用带余除法分解73除以9，余数r为（）A.1B.2C.3D.48.以下模m中存在原根的是（）A.6B.8C.5D.99.2是否是模7的二次剩余？（）A.是B.否C.无法确定D.以上都不对10.以下是勾股数（x²+y²=z²的正整数解）的是（）A.(2,3,4)B.(3,4,5)C.(4,5,6)D.(5,6,7)二、填空题（总共10题，每题2分）1.gcd(48,60)=______。2.lcm(15,20)=______。3.同余式3x≡6mod9的解为x≡______mod3。4.欧拉函数φ(16)=______。5.素数定理中π(x)（不超过x的素数个数）的渐近表达式为______。6.5在模7下的逆元是______。7.100以内的素数共有______个。8.同余方程x²≡1mod5的解为x≡______mod5。9.不定方程2x+3y=10的正整数解为______。10.模8的简化剩余系是______。三、判断题（总共10题，每题2分）1.若a|b且b|c，则a|c。（）2.两个素数的和一定是偶数。（）3.同余式ax≡bmodm有解当且仅当gcd(a,m)|b。（）4.欧拉函数φ(n)是积性函数。（）5.所有素数都是奇数。（）6.若a≡bmodm，则a+c≡b+cmodm。（）7.1是素数。（）8.模6的完全剩余系可以是{0,1,2,3,4,5}。（）9.不定方程x²+y²=3没有正整数解。（）10.勒让德符号(a|p)的值只能是0、1或-1。（）四、简答题（总共4题，每题5分）1.简述带余除法的定义。2.求解同余方程组：x≡1mod3，x≡2mod4。3.证明素数有无穷多个。4.求不定方程3x+5y=28的正整数解。五、讨论题（总共4题，每题5分）1.讨论模运算在密码学中的应用。2.分析欧拉定理的条件和结论。3.探讨素数分布的规律。4.研究不定方程x²-y²=1的正整数解。答案及解析一、单项选择题1.B（121÷11=11，能整除）2.B（24和36的最大公约数为12）3.B（2和6的最大公约数为2，2|4，故解数为2）4.C（97是100以内最大的素数）5.C（3×5=15≡1mod7）6.B（φ(12)=φ(2²×3)=12×(1-1/2)×(1-1/3)=4）7.A（73=8×9+1，余数为1）8.C（模5是奇素数，存在原根）9.A（2是模7的二次剩余，因3²=9≡2mod7）10.B（3²+4²=5²）二、填空题1.122.603.24.8（φ(16)=16×(1-1/2)=8）5.π(x)≈x/lnx6.3（5×3=15≡1mod7）7.258.1或4（1²=1，4²=16≡1mod5）9.(2,2)（2×2+3×2=10）10.{1,3,5,7}三、判断题1.√（整除的传递性）2.×（如2+3=5是奇数）3.√（同余式有解的充要条件）4.√（φ(n)是积性函数）5.×（2是唯一的偶素数）6.√（同余的加法保持性）7.×（素数定义为大于1的自然数）8.√（完全剩余系需包含模m的所有余数）9.√（1²+1²=2，1²+2²=5，均不等于3）10.√（勒让德符号定义）四、简答题1.对于任意整数a和正整数b，存在唯一的整数q和r，使得a=bq+r，且0≤r<b。其中q称为商，r称为余数。2.设x=3k+1，代入第二个方程得3k+1≡2mod4→3k≡1mod4→k≡3mod4（因3×3=9≡1mod4）。故k=4m+3，x=3(4m+3)+1=12m+10，解为x≡10mod12。3.假设素数只有有限个，设为p₁,p₂,…,pₙ。构造N=p₁p₂…pₙ+1，N不能被任何pᵢ整除（否则N≡1modpᵢ矛盾），故N有新的素因子，与假设矛盾，因此素数无穷多。4.整理得x=(28-5y)/3，要求28-5y>0且被3整除。y=2时，x=6；y=5时，x=1。故正整数解为(6,2)和(1,5)。五、讨论题1.模运算在密码学中广泛应用，如RSA加密。其核心是利用大素数乘积难以分解的特性，公钥为(n,e)，私钥为(n,d)，满足ed≡1modφ(n)。加密时计算m^emodn，解密时计算c^dmodn，依赖模指数运算的高效性和大素数的安全性。2.欧拉定理的条件是整数a与m互质（即gcd(a,m)=1），结论是a^φ(m)≡1modm。它推广了费马小定理（当m为素数p时，φ(p)=p-1，即a^(p-1)≡1modp），可用于简化大数的模指数运算（如计算末位数字）。3.素数分布逐渐稀疏，素数定理表明π(x)≈x/lnx（x→∞）。相邻素数间隔逐渐增大，但存在无穷多对孪生素数（猜想）。狄利克雷定理指出