故同余方程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成立，则有
2其中q?Z，所以 ak?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成立。
k
3、设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 = Ckp?1 ? （-1 ）(mod p)
4、设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的奇质数，所以
（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。
三、证明题
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) 5、设a是整数，(1)a≡0(mod9) (2)a≡2010(mod9) (3)a的十进位表示的各位数字之和可被9整除 (4)划去a的十进位表示中所有的数字9，所得的新数被9整除 以上各条件中，成为9|a的充要条件的共有（ C ）。 A.1个 B.2个 C.3个 D.4个 二、填空题 1、σ(2010)=_4896____；?(2010)=528。 202、数C100的标准分解式中，质因数7的指数是_3。 3、每个数都有一个最小质因数。所有不大于10000的合数的最小质因数中，最大者是97。 4、同余方程24x≡6(mod34)的解是x1≡13(mod34) x2≡30(mod34)_。 5、整数n>1，且(n-1)!+1≡0(mod n),则n为素数。 6、3103被11除所得余数是_5_。 7、??60??=_-1_。 ?97?三、计算题 1、判定 (ⅰ) 2x3 ? x2 ? 3x ? 1 ? 0 (mod 5)是否有三个解； (ⅱ) x6 ? 2x5 ? 4x2 ? 3 ? 0 (mod 5)是否有六个解？ 解：(ⅰ) 2x3 ? x2 ? 3x ? 1 ? 0 (mod 5)等价于x3 ? 3x2 ? 4x ? 3 ? 0 (mod 5)，又 x5 ? x = (x3 ? 3x2 ? 4x ? 3)(x2 ? 3x ? 5) + (6x2 ? 12x ? 15)，其中r(x) = 6x2 ? 12x ? 15的系数不都是5的倍数，故原方程没有三个解。 (ⅱ) 因为这是对模5的同余方程，故原方程不可能有六个解。 32n?12、设n是正整数，求C1 的最大公约数。 2n,C2n,?,C2n132n?1132n?12n?1 解：设(C2n,C2n,?,C2n)?d，由C2n?C2n???C2n?2知 d?22n?1， 设2k|n且2k+1?|n，即2k +1||n ， 则由2k +1||C2n及22k + 1。 3、已知a=18,m=77,求使ax? 1 (mod m)成立的最小自然数x。 解：因为（18,77）=1，所以有欧拉定理知18?(77)≡1(mod 77)。 又由于?(77)=60，所以x|60，而60的所有正因数为1,2,3,4,5,6,10,12,15,20,30, 60。 于是x应为其中使18x ? 1 (mod 77)成立的最小数，经计算知：x=30。 四、证明题 1、若质数p?5,且2p+1是质数，证明：4p+1必是合数。 证明：因为质数p?5,所以（3，p）=1，可设p=3k+1或p=3k+2。 当p=3k+1时，2p+1=6k+3是合数，与题设矛盾，从而p=3k+2， 此时2p+1是形如6k+5的质数，而4p+1=12k+9=3(4k+3)是合数。 注：也可设p=6k+r，r=0,1,2,3,4,5。再分类讨论。 2、设p、q是两个大于3的质数，证明：p2≡q2(mod 24)。 证明：因为24=3×8，（3,8）=1，所以只需证明： p2≡q2(mod 3) p2≡q2(mod 8)同时成立。 事实上， 由于（p，3）=1，（q，3）=1，所以p2≡1(mod 3) ， q2≡ 1(mod 3)， 于是p2≡q2(mod 3)，由于p，q都是奇数，所以p2≡1(mod 8) ， q2≡1(mod 8)， 于是p2≡q2(mod 8)。故p2≡q2(mod 24)。 1k?1|Ci2n?2ni?1C2n?1，i = 3, 5, ?, 2n ? 1 得d = i