《初等数论》本科

一 填空题（每空2分）

1.写出30以内的所有素数 2,3,5,7,11,13,17,19,23,29 . 2.设a,b是任意两个不为零的整数,则(a(a,b)(a,b),b)? 1 . 3.若a,b是非零整数,则a与b互素的充要条件是存在整数x,y,适ax?by?1

4.写出180的标准分解式是 22?32?5 ,其正约数个数有 (2+1)(2+1)(1+1)=18个. 5.设a与b是正整数,则在1,2,?,a中能被b整除的整数恰有 [] 个.

ba6.设a,b是非零整数,c是整数,方程ax?by?c有整数解(x,y)的充要条件是 (a,b)|c 7. 若整数集合A是模m的完全剩余系,则A中含有 m 个整数. 8.?(3)= 2 ;?(4)= 2 .

9.当p素数时,(1)?(p)? p?1 ;(2)?(pk)? pk?pk?1 . 10.设m是正整数,(a,m)?1,则a?(m)?1? 0 (momd )11.设p是素数,则对于任意的整数a,有ap?a? 0 (modp )12.已知2x?3?5(mod7),则x? 1 (mod7. )13.同余方程x2?2(mod7)的解是 4(mod7) . 14.同余方程3x2?10x?12?0(mod9)的解是 .X=6. .

p-115.若(n,p)?1,n是模p的二次剩余的充要条件是 n16.若(n,p)?1,n是模p的二次非剩余的充要条件是 n17.()= -1 ; ()= 1 . 55342p-12?1(modp). . ??1(modp). .

18.设p是奇素数,则()? (?1)8p1-1p2p?12 . .

p-1219.设p是奇素数,则()? 1 ;()? (-1)p. . 20. ()= 1 ; (95245)= -1 .

二 判断题(判断下列结论是否成立，每题2分). 1. a|b且a|c?对任意的x,y?Z有a|bx?cy.成立 2. 若(a,b)?(a,c),则[a,b]?[a,c].不成立

3. 若a2|b3,则a|b.不成立

4.a?b(modm),k?0,k?N?ak?bk(modmk). 成立 5.ac?bc(modm)?a?b(modm). 不成立

6. 若a2?b2(modm),则a?b(modm)或a??b(modm)至少有一个成立. 不成立 7. 若a?b(modm),则a2?b2(modm2).不成立

8. 若x通过模m的完全剩余系,则x?b(b是整数)通过模m的完全剩余系. 成立 9. 若{a1,a2,?,am}与{b1,b2,?,bm}都是模m的完全剩余系.不成立

则{a1?b1,a2?b2,?,am?bm}也是模m的完全剩余系.不成立

10.若(a,m)?1,x通过模m的简化剩余系,则ax?b也通过模m的简化剩余系. 不成立 11.若m1,m2?N,(m1,m2)?1,则?(m1m2)??(m1)?(m2). 成立

12. 同余方程4x2?3x?3?0(mod15)和同余方程4x2?12x?12?0(mod15)是同解的. 成立

13. 同余方程ax?b(modm)等价于不定方程ax?my?b.成立 14. 当m是奇素数时,若x2?a(modm)有解,则()?1.成立

ma15. 当m不是奇素数时,若(

三 计算题

am)?1,则方程x?a(modm)一定有解.不成立

21. 求(?1859,1573).（6分）

1.(?1859,1573)?(1859,1573)?(286,1573)?(286,1573?286?5)?(286,143)?(0,143)?143解：

2.求 [-36,108,204].（8分）

2.[?36,108,204]?[36,108,204],解：?36?22?32,108?22?33,204?22?3?17,

?[36,108,204]?2?3?17?1836.233. 求(125,17),以及x,y,使得125x+17y=(125,17).（10分）

3.由等式6?5?1起逐步回代,得解：

1?6-5?6-(17-2?6)?3?6-17?3?(125-17?7)-17?3?125-22?17.?125?3-17?22?1,x?3,y?-22.

4. 求整数x,y,使得1387x-162y=(1387,162).（10分）

4.由等式9?4?2?1起逐步回代,得1?9-4?2?9-4?(11-9)?5?9-4?11?5?(20-11)-4?11?5?20-9?11?5?20-9?(71?3?20)?32?20?9?71解：

?32?(91-71)?9?71?32?91?41?71?32?91?41?(162?91)?73?91?41?162?73?(1387?8?162)?41?162?73?1387?625?162.?1387?73?162?625?1.

5. 分解12!为质因数乘积.（8分）

6. 求最大的正整数k,使10k|199!.（8分） 7. 求[1?12?13???1100].(10分)

8. 求方程8x?17y?43的整数解.(6分)

9. 求方程19x?20y?1909的正整数解.(10分)

10. 求方程111x-321y=75的整数解.(10分) 11. 求方程15x1?10x2?6x3?61的整数解.(8分) 12. 求不定方程3x?6y?12z?15的整数解.(8分)

13. 求不定方程x?2y?3z?7的所有正整数解.(8分)

14. 将1930写成三个分数之和,它们的分母分别是2,3和5.(10分)

15. 求方程x2y?2x2?3y?7?0的整数解.(6分) 16. 求方程x3?y3?1072的整数解.(8分)

17. 求方程5(xy?yz?zx)?4xyz的正整数解.(10分)

18. 求3406的个位数字与最后两位数字(十进制).(10分)

19. 解同余方程6x?7(mod23).(8分) 20. 解同余方程12x?15?0(mod45).(8分) ?x?2(mod3)?21. 解同余式组?x?3(mod5).(6分)

?x?2(mod7)?22. 解同余式f(x)?0(mod35),f(x)?x?2x?8x?9.(10分)

4323. 解同余方程:x7?2x6?7x5?x?2?0(mod5).(6分)

24. 求出模23的所有二次剩余和二次非剩余.(8分)

25. 判断方程x2?5(mod11)有没有解.(6分)

26. 已知563是素数,判定方程x2?429(mod563)是否有解.(8分) 27. 求以3为其二次剩余的全体素数.(8分)

28. 计算:(1)(10115);(2)(7321).(8

分)

29. 计算?(300).(6分)

?x?3(mod8)?30. 解同余式组?x?11(mod20).(10分)

?x?1(mod15)?

四 证明题

1、设a,b是两个给定的非零整数,且有整数x,y,使得ax?by?1.求证:若a|n,b|n,则ab|n.(6分)

1.?n?n(ax?by)?nax?nby证明：

又 ab|na,ab|nb?abn.

2.设a1,a2,?,an是整数,且a1?a2???an?0,a1a2?an?n.则4|n.(8分)

2.若n是奇数,则n,a1,a2,?,an都是奇数,则a1?a2???an?0不可能,?2n.即在a1,a2,?,an中至少有一个偶数.如果只有一个偶数,不妨设为a1,则2不证明：整除ai(2?i?n).由a2?a3???an?-a1知,左边是(n-1)个奇数的和,右边是偶数,这是不可能的.?在a1,a2,?,an中至少有两个偶数,即4n.

3. 任给的五个整数中,必有三个数之和被3整除.(8分)

3.设ai?3qi?ri,0?ri?3,i?1,2,3,4,5.证明：(1)若在ri中数0,1,2都出现,不妨设r1?0,r2则a1?a2?a3?3(q1?q2?q3)?3r成立.?1,r3?2,则a1?a2?a3?3(q1?q2?q3)?3成立.

(2)若在ri中数0,1,2至少有一个不出现,则至少有三个ri取相同的值,令r1?r2?r3?r(r?0,1或2),4. 设a,b是整数,且9|a?ab?b,则3|(a,b).(8分)

224.?9a?ab?b,?9(a?b)?3ab,?3(a?b)?3ab,?3(a?b),?3a?b,?9(a?b),?93ab,?3ab,?3a或3b.222222证明：若3a,?3a?b,?3b.若3b.?3a?b,?3a.故3(a,b).

5. 设a,b是正整数,证明(a?b)[a,b]?a[b,a?b].(8分)

5.(a?b)[a,b]?(a?b)?ab(a,b)?a?b(a?b)(a,b),证明：

?b(a?b)?[b,a?b](b,a?b),而(b,a?b)?(a,b),?b(a?b)?[b,a?b](a,b),即b(a?b)(a,b)?[b,a?b],?结论成立

6. 当a?b(modm)时,又n?0,n?N,则an?bn(modm).(6分)

6.?a?b(modm),?ma?b,证明：又an?bn?(a?b)(an?1?an?2b?an?3b2???bn?1),

?ma?b,即a?b(modm).nnnn7. 设A?{x1,x2,?,xm}是模m的一个完全剩余系,以{x}表示x的小数部分.

m证明:若(a,m)?1,则?{i?1axi?bm}?12(m-1).(10分)

7.由定理2知,{ax1?b,ax2?b,?,axm?b}也是模m的一个完全剩余系,证明：可设axi?b?km?j(1?j?m),m

m从而?{i?1axi?bmm}??{k?m}??{m}??{m}??j?1j?1j?1kjjm?1jm?1jm?1m?m(m?1)2?m?12.j?1

8. 设n?N,证明:?(n)?k12n的充要条件是n?2,k?N.(10分)

kk8.?若n?2,则?(2)?2(1-?若?(n)?n2,设n?2t,2?|t,kkk12)?2k-1?n2.证明：则n2??(n)??(2t)??(2)?(t)?2k-1?(t)?12?2t?k?(t)t?n?(t)?, 2t即?(t)?t,?t?1,从而得证.(注?(n)?1?n?1或2)nnnn|1?2?3?4?4n.(10分) 9. 设n?N,则5?9.??(5)?4,由定理知,k?1(mod5)(1?k?4).令n?4q?r,0?r?3,则1?2?3?4?(1)?1?(2)?2?(3)?3?(4)?4nnnn4qr4qr4qr4qr4证明：?1r?2?3?4(mod5).nnnnrrrrrrr

rrrrnnnn?若5?|1?2?3?4,即得5?|1?2?3?4,?把r?0,1,2,3代入检验可知r?0,?4n;?若4n,则r?0,易知5?|1?2?3?4,?5?|1?2?3?4.10. 设m是正整数,(a,m)?1,证明:x?ba?(m)?1(modm)是同余方程ax?b(modm)的解.

10.?(a,m)?1,由Euler定理,则a?(m)?1(modm).证明：?ax?b?a?(m)b(modm),?(a,m)?1,?x?a?(m)-1

p-1b(modm).211. n是模p的二次非剩余的充要条件是n11.若(n,p)?1,则由Euler定理,np?1p?1p-1??1(modp).(10分)

?1(modp),?(n2?1)(n2?1)?0(modp),p?1p?12证明：?p是素数,则n?1?0(modp)或n2p-1?1?0(modp)中必有一个成立,

2?n是模p的二次剩余的充要条件是np?1?1(modp),?n2??1(modp).12. 设y?a1(modp),y?a2(modp)都是模p的平方剩余,

y?b1(modp),y?b2(modp)都是模p的平方非剩余.

求证:y?a1a2(modp),y?b1b2(modp)都是模p的平方剩余,y?a1b1(modp)是模p的平方非剩余.12.由定理1知,p?1p?1p?12p?1(10分)

证明：

a12?a22?1(modp),b1p?1p?1?b22??1(modp),p?12

?(a1a2)?得证.2?(b1b2)2?1(modp),(a1b1)??1(modp),13. 设p,q为两个形如4n?3的奇质数,求证:若x?p(modq)无解,则x?q(modp)有两个解.(10分)

2213.证明:?p,q均为形如4n?3的数,?又?x?p(modq)无解,?(22p?1q-1,均为奇数,22qp)?(-1)p?1q-1?22pq)??1,则((pq)??(pq)?1.22?x?q(modp)有解,设c是其一解,则因为c??-c(modp),且(-c)?c?q(modp), ?-c也是其一解,又因为二次同余方程至多有两个解,故x?q(modp)恰有两个解为?c.214. 设p是适合p?1(mod4)的素数,y?a(modp)是模p的平方剩余.

证明:y??a(modp)也是模p的平方剩余.(8分)

p?114.证明:令p?4k?1,由定理1知,ap?12?1(modp),

则(-a)2?1(modp).15. 设n是整数,证明:n2?1的任何奇因数都是4m?1的形式.(10分)

15.证明:由于奇数都可表示成奇素数之积,而且任意多个形如4m?1的整数之积也具有4m?1的形式.我们只需证明:若素数p是n?1的因数,则p具有4m?1的形式. 若p|n?1,则n??1(modp),即-1?QR(p),由以上推论知,p?4m?1.22216. 若p是素数,则同余方程xp-1?1(modp)有p-1个解.(8分)

16.证明:由费马定理(Fermat定理)可知,任意与p互质的数都是它的解.因此,这个同余方程恰好有p-1个不同的解,即x?1,2,3,?,p-1(modp).

17. 设N?an10?an-11023nn-1n???a1?10?a0,求证:9|N?9|?ai.(8

i?0n分)

17.?10?1,10?1,10?1,?,10?1(mod9),?N?an10?an?1105nn?1???a110?a0?an?an?1???a1?a0(mod9);

18. 求证:641|22?1.(8分)

18.?2?4,2?16,2?256,2?232248165?154,2?1.32??1(mod641),?1?0(mod641),?64122

19. 证明:若m,n?N,则?(mn)?(m,n)?([m,n]).(10分)

19.证明:易知mn与[m,n]有相同的素因数,设它们是pi(1?i?k).则?(mn)?mn(1-1p1)(1-1p11p2)?(1-1p21pk),1pk),?([m,n])?[m,n](1-?mn?(m,n)[m,n],)(1-)?(1-

??(mn)?(m,n)[m,n](1-1p1)(1-1p2)?(1-1pk)?(m,n)?([m,n]).20. 设p是素数,则对于任意的整数a,有ap?a(modp).(8分)

20.证明:若(a,p)?1,由Euler定理,a若(a,p)?1,则pa,?app?1?1(modp),(??(p)?p?1),?ap?a(modp).?0?a(modp),?结论成立