2025初等数论期末一周速成专用题库及配套答案

2025初等数论期末一周速成专用题库及配套答案

一、单项选择题（共10题，每题2分）1.下列数中能被12整除的是A.123456B.123457C.123458D.1234592.最大公约数gcd(120,168)等于A.24B.12C.36D.483.欧拉函数φ(15)的值是A.8B.9C.10D.114.根据费马小定理，若p是素数，a与p互素，则a^(p-1)模p等于A.0B.1C.aD.p-15.若a≡bmodm，c≡dmodm，则下列不一定成立的是A.ac≡bdmodmB.a+c≡b+dmodmC.a-d≡b-cmodmD.a/b≡c/dmodm6.模7的完全剩余系可以是A.0,1,2,3,4,5,6B.1,2,3,4,5,6,7C.0,2,4,6,8,10,12D.1,3,5,7,9,11,137.一次同余方程3x≡5mod7的解是A.x≡4mod7B.x≡5mod7C.x≡6mod7D.x≡3mod78.模5的平方剩余是A.1,4B.1,2C.3,4D.2,39.下列数组中是本原勾股数的是A.(3,4,5)B.(6,8,10)C.(9,12,15)D.(12,16,20)10.约数函数d(12)的值是A.6B.5C.4D.3二、填空题（共10题，每题2分）1.若a整除b且b整除c，则________2.若gcd(a,b)=d，则最小公倍数lcm(a,b)=________3.小于10的素数有________4.欧拉函数φ(8)的值是________5.若a≡3mod5，b≡4mod5，则a+b模5等于________6.模6的简化剩余系的元素个数是________7.一次同余方程ax≡bmodm有解的充要条件是________8.模7的平方非剩余是________9.不定方程x+y=5的正整数解有________组10.约数和函数σ(6)的值是________三、判断题（共10题，每题2分）1.若a整除b且a整除c，则a整除b+c（）2.gcd(a,b)乘以lcm(a,b)等于a加b（）3.2是唯一的偶素数（）4.欧拉函数φ(n)是积性函数（）5.若a≡bmodm，则m整除a-b（）6.模m的完全剩余系中恰有φ(m)个简化剩余系元素（）7.一次同余方程2x≡1mod4有解（）8.模3的平方剩余是1（）9.本原勾股数中必有一个是偶数（）10.约数函数d(n)是积性函数（）四、简答题（共4题，每题5分）1.简述辗转相除法求gcd(a,b)的步骤。2.什么是费马小定理？其应用场景有哪些？3.简述模m的完全剩余系和简化剩余系的区别与联系。4.什么是本原勾股数？如何生成本原勾股数？五、讨论题（共4题，每题5分）1.为什么2是唯一的偶素数？2.一次同余方程ax≡bmodm有解的充要条件是gcd(a,m)|b，试举例说明。3.欧拉函数φ(n)的计算方法有哪些？4.如何判断一个数是否为模p的平方剩余？（p为奇素数）答案及解析一、单项选择题答案及解析1.A解析：12=3×4，需同时被3和4整除。123456各位和21被3整除，末两位56被4整除，符合。2.A解析：辗转相除法：168÷120=1余48；120÷48=2余24；48÷24=2余0，故gcd=24。3.A解析：15=3×5，φ(3)=2，φ(5)=4，积性函数得φ(15)=2×4=8。4.B解析：费马小定理核心结论，互素时模素数p的幂为1。5.D解析：同余性质中加法、乘法、减法成立，除法无保证（需逆元存在）。6.A解析：完全剩余系含模m所有剩余类代表（0到m-1），7的完全剩余系为0-6。7.A解析：3×4=12≡5mod7，故x≡4mod7。8.A解析：1²=1，2²=4，3²=9≡4，4²=16≡1，平方剩余为1、4。9.A解析：本原勾股数gcd(a,b,c)=1，(3,4,5)gcd为1，其余为倍数（gcd≥3）。10.A解析：12的约数为1、2、3、4、6、12，共6个，故d(12)=6。二、填空题答案及解析1.a整除c解析：整除传递性，若a|b、b|c，则a|c。2.ab除以d解析：gcd(a,b)×lcm(a,b)=ab，故lcm(a,b)=ab/d。3.2、3、5、7解析：小于10的素数（仅1和自身为约数）为这四个。4.4解析：8=2³，φ(2³)=2³-2²=4。5.2解析：3+4=7，7mod5=2。6.2解析：模6的简化剩余系元素为1、5（与6互素），共2个，即φ(6)=2。7.gcd(a,m)整除b解析：一次同余方程有解的充要条件。8.2、3、5、6解析：模7平方剩余为1、2、4（3²=9≡2，2²=4），剩余为非剩余。9.4解析：正整数解为(1,4),(2,3),(3,2),(4,1)，共4组。10.12解析：6的约数和为1+2+3+6=12。三、判断题答案及解析1.√解析：整除的线性性，a|b、a|c则a|(kb+lc)（k,l为整数），取k=l=1得a|b+c。2.×解析：应为gcd(a,b)×lcm(a,b)=ab，而非a+b。3.√解析：大于2的偶数均为2的倍数，是合数，仅2为偶素数。4.√解析：若m,n互素，则φ(mn)=φ(m)φ(n)，故φ(n)是积性函数。5.√解析：同余定义：a≡bmodm等价于m|(a-b)。6.√解析：简化剩余系是完全剩余系中与m互素的元素，个数为φ(m)。7.×解析：gcd(2,4)=2，2不整除1，故无解。8.√解析：1²=1，2²=4≡1mod3，平方剩余仅1。9.√解析：勾股数不可能全奇（奇²+奇²=偶，偶²=偶；奇²+偶²=奇，奇²=奇），故必有一个偶数。10.√解析：若m,n互素，则d(mn)=d(m)d(n)，约数函数是积性函数。四、简答题答案1.辗转相除法步骤：①给定a>b的正整数，a除以b得商q₁、余数r₁（a=bq₁+r₁，0≤r₁<b）；②若r₁=0，gcd为b；③若r₁≠0，用b除以r₁得q₂、r₂（b=r₁q₂+r₂，0≤r₂<r₁）；④重复直到rₙ=0，此时rₙ₋₁为gcd。基于gcd(a,b)=gcd(b,r₁)，快速求最大公约数。2.费马小定理：若p是素数，a与p互素，则a^(p-1)≡1modp。应用：①简化模幂（指数模p-1）；②素数测试（若a^(p-1)≢1则p为合数）；③求逆元（a的逆元为a^(p-2)modp）。注意是素数必要条件（卡迈克尔数除外）。3.区别：①完全剩余系含m个元素（0到m-1），简化剩余系含φ(m)个（与m互素）；②简化剩余系元素与m互素，完全剩余系无此要求。联系：①简化剩余系是完全剩余系子集；②若c与m互素，完全剩余系乘c仍为完全剩余系，简化剩余系乘c仍为简化剩余系。4.本原勾股数：满足a²+b²=c²且gcd(a,b,c)=1的正整数组。生成：取互素的m>n>0（一奇一偶），则a=m²-n²，b=2mn，c=m²+n²。验证：a²+b²=(m²-n²)²+(2mn)²=(m²+n²)²=c²，且gcd(a,b,c)=1（m,n互素一奇一偶）。五、讨论题答案1.素数定义为大于1且仅1和自身为约数的数。偶数是2的倍数，若存在大于2的偶素数p，则p=2k（k≥2），p的约数有1、2、k、p，与素数定义矛盾。例如4=2×2、6=2×3均为合数，仅2仅能被1和2整除，故2是唯一偶素数。2.充要条件：gcd(a,m)|b。举例：①2x≡3mod4，gcd(2,4)=2不整除3，无解；②3x≡6mod9，gcd(3,9)=3整除6，解为x≡2,5,8mod9（3个解）；③5x≡10mod15，gcd(5,15)=5整除10，解为x≡2,5,8,11,14mod15（5个解）。若gcd(a,m)=d，可化简为a'x≡b'modm'（a'=a/d,m'=m/d,b'=b/d），此时gcd(a',m')=1，有唯一解modm'，原方程有d个解modm。3.欧拉函数φ(n)计算：①素数幂：n=p^k时，φ(n)=p^k-p^(k-1)；②积性函数：m,n互素时φ(mn)=φ(m)φ(n)；③质因数分解：n=p₁^k₁…p_r^k_r时，φ(n)=n×(1-1/p₁)×…×(1-1/p_r)。例如12=2²×3¹，φ(12)=12×(1-1/2)×(