初等数论练习题一
一、填空题
1、d(2420)=12; ?(2420)=_880_ 2、设a,n是大于1的整数，若an-1是质数，则a=_2. 3、模9的绝对最小完全剩余系是_{-4，-3，-2，-1,0,1,2,3,4}. 4、同余方程9x+12≡0(mod 37)的解是x≡11(mod 37)。
5、不定方程18x-23y=100的通解是x=900+23t，y=700+18t t?Z。. 6、分母是正整数m的既约真分数的个数为_?(m)_。 7、18100被172除的余数是_256。 8、??65?? =-1。 ?103?
9、若p是素数，则同余方程x p ? 1 ?1(mod p)的解数为 p-1 。 二、计算题
1、解同余方程：3x2?11x?20 ? 0 (mod 105)。
解：因105 = 3?5?7，
同余方程3x2?11x?20 ? 0 (mod 3)的解为x ? 1 (mod 3)， 同余方程3x2?11x?38 ? 0 (mod 5)的解为x ? 0，3 (mod 5)， 同余方程3x2?11x?20 ? 0 (mod 7)的解为x ? 2，6 (mod 7)， 故原同余方程有4解。
作同余方程组：x ? b1 (mod 3)，x ? b2 (mod 5)，x ? b3 (mod 7)，
其中b1 = 1，b2 = 0，3，b3 = 2，6，
由孙子定理得原同余方程的解为x ? 13，55，58，100 (mod 105)。 2、判断同余方程x2≡42(mod 107)是否有解？
237）（）（）1071071071071073?1107?17?1107?1 ??2310727107222?（）??1，（）?（?1）（）??（）?1，（）?（?1）22（）??（）??1107107331077742?（）?11072?3?7解：(42)?（）?（ 故同余方程x2≡42(mod 107)有解。
3、求（127156+34）28除以111的最小非负余数。
解：易知1271≡50（mod 111）。
由502 ≡58（mod 111）, 503 ≡58×50≡14（mod 111），509≡143≡80（mod 111）知5028 ≡（509）3×50≡803×50≡803×50≡68×50≡70（mod 111） 从而5056 ≡16（mod 111）。
故（127156+34）28≡（16+34）28 ≡5028≡70（mod 111） 三、证明题
1、已知p是质数，（a,p）=1，证明：
（1）当a为奇数时，ap-1+(p-1)≡0 (mod p)； （2）当a为偶数时，ap-1-(p-1)≡0 (mod p)。
证明：由欧拉定理知ap-1≡1 (mod p)及(p-1)≡-1 (mod p)立得（1）和（2）成立。 2、设a为正奇数，n为正整数，试证a2na
aa
≡1(mod 2n+2)。 …………… （1）
证明 设a = 2m ? 1，当n = 1时，有
a2 = (2m ? 1)2 = 4m(m ? 1) ? 1 ? 1 (mod 23)，即原式成立。 设原式对于n = k成立，则有 其中q?Z，所以 a2k?1a2k? 1 (mod 2k + 2) ?a2= 1 ? q2k + 2，
k= (1 ? q2k + 2)2 = 1 ? q ?2k + 3 ? 1 (mod 2k + 3)，
其中q ?是某个整数。这说明式(1)当n = k ? 1也成立。 由归纳法知原式对所有正整数n成立。
k3、设p是一个素数，且1?k?p-1。证明：Ckp?1 ? （-1 ）(mod p)。
（p?1）(p?2)?(p?k) 证明：设A=Ckp?1? 得：
k! k!·A =（p-1）(p-2)…（p-k）≡（-1）(-2)…（-k）(mod p)
k
又（k!，p）=1，故A = Ck ? （-1 ）(mod p) p?14、设p是不等于3和7的奇质数，证明：p6≡1(mod 84)。 说明：因为84=4×3×7，所以，只需证明：
p6≡1(mod 4) p6≡1(mod3) p6≡1(mod 7) 同时成立即可。 证明：因为84=4×3×7及p是不等于3和7的奇质数，所以
2
（p，4）=1，（p，3）=1，（p，7）=1。
由欧拉定理知：p?(4)≡p2≡1(mod 4)，从而 p6≡1(mod 4)。
同理可证：p6≡1(mod3) p6≡1(mod 7)。 故有p6≡1(mod 84)。
注：设p是不等于3和7的奇质数，证明：p6≡1(mod 168)。（见赵继源p86）
初等数论练习题二
一、填空题
1、d(1000)=_16_；σ(1000)=_2340_. 2、2010!的标准分解式中，质数11的次数是199__. 3、费尔马(Fermat)数是指Fn=22+1,这种数中最小的合数Fn中的n=5。 4、同余方程13x≡5(mod 31)的解是x≡29(mod 31)___ 5、分母不大于m的既约真分数的个数为?(2)+ ?(3)+…+ ?(m)。 6、设7∣(80n-1),则最小的正整数n=_6__. 7、使41x+15y=C无非负整数解的最大正整数C=__559__. 8、??46??=_1__. ?101?n9、若p是质数，n?p ? 1，则同余方程x n ? 1 (mod p) 的解数为n . 二、计算题
20031、试求20022004被19除所得的余数。
解：由2002≡7 (mod 19) 20022≡11(mod 19) 20023≡1 (mod 19) 又由20032004≡22004≡（22）1002≡1 (mod 3)可得：
200320022004≡20023n+1≡(20023)n×2002≡7(mod 19)
2、解同余方程3x14 ? 4x10 ? 6x ? 18 ? 0 (mod 5)。
解：由Fermat定理，x5 ? x (mod 5)，因此，原同余方程等价于2x2 ? x ? 3 ? 0 (mod 5) 将x ? 0，?1，?2 (mod 5)分别代入上式进行验证，可知这个同余方程解是x ? 1 (mod 5)。 3、已知a=5，m=21,求使a x ? 1 (mod m)成立的最小自然数x。 解：因为（5,21）=1，所以有欧拉定理知5?(21)≡1(mod 21)。
又由于?(21)=12，所以x|12，而12的所有正因数为1,2,3,4,6,12。
于是x应为其中使 5 x ? 1 (mod 12)成立的最小数，经计算知：x=6。
3
三、证明题
1、试证13|(54m+46n+2000)。(提示：可取模13进行计算性证明)
证明：54m+46n+2000 ? 252m+642n+2000 ?（-1）2m+（-1）2n+2000 ? 2002? 0(mod 13)。 2、证明Wilson定理的逆定理：若n > 1，并且(n ? 1)! ? ?1 (mod n)，则n是素数。 证明：假设n是合数，即n = n1n2，1 < n1 < n，由题设易知(n ? 1)! ? ?1 (mod n1)，得
0 ? ?1 (mod n1)，矛盾。故n是素数。
3、证明：设ps表示全部由1组成的s位十进制数，若ps是素数，则s也是一个素数。 证明：假设s是合数，即s=ab，1 10s?1(10a)b?110a?1 ps?11?1????M，其中M＞1是正整数。 ???999s由pa＞1也是正整数知ps是合数，这与题设矛盾。故s也是一个素数。 4、证明：若2p ? 1是奇素数，则 (p!)2 ? (?1)p ? 0 (mod 2p ? 1)。 证明：由威尔逊定理知 ?1 ? (2p)! = p!(p ? 1)?(2p) ? (?1)p(p!)2(mod 2p ? 1)， 由此得(p!)2 ? (?1)p ? 0 (mod 2p ? 1)。 5、设p是大于5的质数，证明：p4≡1(mod 240)。（提示：可由欧拉定理证明） 证明：因为240=23×3×5，所以只需证：p4≡1(mod 8)，p4≡1(mod 3)，p4≡1(mod 5)即 可。事实上，由?(8)=4，?(3)=2，?(5)=4以及欧拉定理立得结论。 初等数论练习题三 一、单项选择题 1、若n＞1，?(n)=n-1是n为质数的（ C ）条件。 A.必要但非充分条件 B.充分但非必要条件 C.充要条件 D.既非充分又非必要条件 2、设n是正整数，以下各组a，b使为既约分数的一组数是（ D ）。 A.a=n+1,b=2n-1 B.a=2n-1,b=5n+2 C.a=n+1,b=3n+1 D.a=3n+1,b=5n+2 3、使方程6x+5y=C无非负整数解的最大整数C是（ A ）。 A.19 B.24 C.25 D.30 ba4、不是同余方程28x≡21(mod 35)的解为（ D ）。 A.x≡2(mod 35) B. x≡7(mod 35) C. x≡17(mod 35) D. x≡29(mod 35) 4