2022大学初等数论平时测验+期末考题库及完整答案

2022大学初等数论平时测验+期末考题库及完整答案

一、单项选择题（总共10题，每题2分）1.带余除法中，对于任意整数a和正整数b，存在唯一的整数q和r满足（）A.a=bq+r，0≤r<bB.a=bq+r，1≤r<bC.a=bq+r，0≤r≤bD.a=bq+r，-b<r≤02.设d=gcd(60,42)，则存在整数x,y使得60x+42y=d，下列正确的是（）A.x=2,y=-3B.x=-1,y=2C.x=3,y=-4D.x=1,y=-13.关于素数的性质，错误的是（）A.素数大于1B.素数只能被1和自身整除C.所有素数都是奇数D.存在无穷多个素数4.同余式3x≡6(mod9)的解数为（）A.1B.2C.3D.05.欧拉函数φ(100)的值为（）A.30B.40C.50D.606.下列模数中存在原根的是（）A.8B.12C.16D.187.Legendre符号(15|17)的值为（）A.1B.-1C.0D.28.Pell方程x²-2y²=1的最小正整数解是（）A.(1,1)B.(3,2)C.(7,5)D.(17,12)9.用中国剩余定理求解同余方程组：x≡2(mod3)，x≡3(mod4)，x≡1(mod5)，其解为（）A.x≡17(mod60)B.x≡38(mod60)C.x≡58(mod60)D.x≡7(mod60)10.计算2¹⁰⁰mod7的结果为（）A.2B.3C.4D.5二、填空题（总共10题，每题2分）1.gcd(138,186)=______。2.3在模7下的乘法逆元是______。3.φ(45)=______（φ为欧拉函数）。4.100以内最大的素数是______。5.同余方程2x≡5(mod8)的解数为______。6.Legendre符号(7|11)=______。7.Pell方程x²-3y²=1的最小正整数解是______。8.2在模11下的阶是______。9.当奇素数p≡______mod4时，-1是模p的二次剩余。10.不定方程x²+y²=1的整数解个数为______。三、判断题（总共10题，每题2分）1.带余除法中，余数r的取值范围是0≤r<|b|。（）2.素数有无穷多个。（）3.同余式ax≡b(modm)有解当且仅当gcd(a,m)不整除b。（）4.欧拉定理要求a与m互质。（）5.模12存在原根。（）6.Legendre符号是完全积性函数。（）7.Pell方程x²-Dy²=1（D为非平方正整数）仅有有限个正整数解。（）8.若a模m的阶为d，则d必整除φ(m)。（）9.奇素数p的二次剩余个数为(p-1)/2。（）10.不定方程x²-y²=2无整数解。（）四、简答题（总共4题，每题5分）1.简述最大公约数的主要性质（至少列出3条）。2.说明同余式ax≡b(modm)有解的条件及解数。3.简述素数无限性的证明思路（用反证法）。4.陈述欧拉定理的内容，并说明其证明的关键步骤。五、讨论题（总共4题，每题5分）1.讨论中国剩余定理的适用条件及其在解同余方程组中的作用。2.分析高次同余方程f(x)≡0(modm)的一般解法步骤。3.比较二次剩余的欧拉判别法与二次互反律的优缺点。4.讨论不定方程x²+y²=z²的整数解结构（本原解与非本原解）。答案及解析一、单项选择题1.A（带余除法定义：0≤r<b）2.B（gcd(60,42)=6，60×(-1)+42×2=-60+84=24？不，实际计算：60=42×1+18，42=18×2+6，18=6×3，故6=42-18×2=42-(60-42×1)×2=42×3-60×2，即x=-2,y=3？可能题目选项有误，但按选项B：-1×60+2×42=-60+84=24，非6，可能题目数据调整，正确应为x=-2,y=3，但选项中选最接近的B）3.C（2是唯一偶素数）4.C（gcd(3,9)=3，3|6，解数3个）5.B（φ(100)=φ(2²×5²)=100×(1-1/2)×(1-1/5)=40）6.D（原根存在的模为1,2,4,p^k,2p^k，p奇素数，k≥1；18=2×3²，符合2p^k）7.A（(15|17)=(3|17)(5|17)，(3|17)=(17|3)×(-1)^((3-1)(17-1)/4)=(2|3)×(-1)^2=(-1)×1=-1；(5|17)=(17|5)×(-1)^((5-1)(17-1)/4)=(2|5)×1=-1；故(-1)×(-1)=1）8.B（3²-2×2²=9-8=1）9.C（逐步求解：x=3k+2，代入第二个方程得3k+2≡3mod4→3k≡1mod4→k≡3mod4→k=4m+3→x=12m+11；代入第三个方程12m+11≡1mod5→12m≡-10≡0mod5→m≡0mod5→m=5n→x=60n+58）10.A（2³=8≡1mod7，100=3×33+1，故2¹⁰⁰=(2³)³³×2¹≡1³³×2=2mod7）二、填空题1.6（186=138×1+48，138=48×2+42，48=42×1+6，gcd=6）2.5（3×5=15≡1mod7）3.24（φ(45)=φ(9×5)=φ(9)×φ(5)=6×4=24）4.975.0（gcd(2,8)=2，2不整除5，无解）6.-1（(7|11)=(11|7)×(-1)^((7-1)(11-1)/4)=(4|7)×(-1)^15=(2²|7)×(-1)=1×(-1)=-1）7.(2,1)（2²-3×1²=1）8.10（2¹⁰≡1mod11，且无更小正整数d<10使2^d≡1mod11）9.1（-1是模p的二次剩余当且仅当p≡1mod4）10.4（(±1,0),(0,±1)）三、判断题1.√（带余除法定义）2.√（反证法可证）3.×（有解当且仅当gcd(a,m)|b）4.√（欧拉定理条件为(a,m)=1）5.×（12=2²×3，原根存在的模不含2²×奇素数幂）6.√（Legendre符号对乘积保持积性）7.×（Pell方程有无限多解）8.√（阶的定义要求d|φ(m)）9.√（二次剩余与非剩余各占(p-1)/2个）10.√（x²-y²=(x-y)(x+y)=2，x-y和x+y同奇偶，2无法分解为两同奇偶整数之积）四、简答题1.最大公约数的主要性质：①gcd(a,b)=gcd(b,a)（交换律）；②gcd(a,b)=gcd(a,b-ka)（线性组合不变性）；③若p为素数且p|ab，则p|a或p|b；④存在整数x,y使得ax+by=gcd(a,b)（贝祖定理）。2.同余式ax≡b(modm)有解的条件是gcd(a,m)|b。若条件满足，解数为gcd(a,m)个（模m）。3.素数无限性的反证法思路：假设素数只有有限个，记为p₁,p₂,…,pₙ。构造数N=p₁p₂…pₙ+1，N不被任何pᵢ整除（否则pᵢ|1，矛盾），故N为新素数或含新素因子，与假设矛盾，因此素数无限。4.欧拉定理：若(a,m)=1，则a^φ(m)≡1(modm)。证明关键：考虑模m的缩系{a₁,a₂,…,a_φ(m)}，则{aa₁,aa₂,…,aa_φ(m)}也是缩系，两集合乘积模m相等，约去公共因子得a^φ(m)≡1(modm)。五、讨论题1.中国剩余定理适用于模数两两互质的同余方程组，保证解存在且唯一模模数乘积。其作用是将复杂同余方程组分解为简单模素数幂的方程组，通过逐步求解合并得到通解，广泛应用于密码学、数论问题简化。2.高次同余方程f(x)≡0(modm)的解法步骤：①将m分解为素数幂乘积m=p₁^k₁p₂^k₂…pᵣ^kᵣ；②分别求解f(x)≡0(modpᵢ^kᵢ)的解；③用中国剩余定理合并各素数幂模的解，得到模m的解。3.欧拉判别法直接通过a^((p-1)/2)≡1或-1modp判断二次剩余，计算简单但需大指数运算；二次互反律通过符号转换简化Legendre符号计算（如(p|q