初等数论练习题一
一、填空题
1、τ(2420)=27；?(2420)=_880_
2、设a ，n 是大于1的整数，若a n -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
8、??? ??10365 =-1。
9、若p 是素数，则同余方程x p - 1≡1(mod p )的解数为二、计算题
1、解同余方程：3x 2+11x -20≡0 (mod 105)。
解：因105 = 3?5?7，
同余方程3x 2+11x -20≡0 (mod 3)的解为x ≡1 (mod 3)，
同余方程3x 2+11x -38 ≡0 (mod 5)的解为x ≡0，3 (mod 5)，
同余方程3x 2+11x -20≡0 (mod 7)的解为x ≡2，6 (mod 7)，
故原同余方程有4解。
作同余方程组：x ≡b 1 (mod 3)，x ≡b 2 (mod 5)，x ≡b 3 (mod 7)，
其中b 1 = 1，b 2 = 0，3，b 3 = 2，6，
由子定理得原同余方程的解为x ≡13，55，58，100 (mod 105)。
2、判断同余方程x 2≡42(mod 107)是否有解？
11074217
271071107713231071107311072107
710731072107732107422110721721107213)(=∴-=-=-==-=-=-==??≡-?--?-）（）（）（）（），（）（）（）（），（）（））（）（（
）（解： 故同余方程x 2≡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 为奇数时，a p-1+(p-1)a ≡0 (mod p)；
（2）当a 为偶数时，a p-1-(p-1)a ≡0 (mod p)。
证明：由欧拉定理知a p-1≡1 (mod p)及(p-1)a ≡-1 (mod p)立得（1）和（2）成立。
2、设a 为正奇数，n 为正整数，试证n 2a ≡1(mod 2n+2)。 (1)
证明 设a = 2m +1，当n = 1时，有
a 2 = (2m +1)2 = 4m (m +1)+1≡1 (mod 23)，即原式成立。
设原式对于n = k 成立，则有k a
2≡1 (mod 2k +2) ?k a 2= 1+q 2k +2， 其中q ∈Z ，所以12+k a = (1+q 2k +2)2 = 1+q '2k +3≡1 (mod 2k +3)，
其中q '是某个整数。这说明式(1)当n = k +1也成立。
由归纳法知原式对所有正整数n 成立。
3、设p 是一个素数，且1≤k ≤p-1。证明：k
p 1C -≡ （-1 ）k (mod p )。
证明：设A=!
)()2(1C 1k k p p p k
p ---=- ）（ 得： k!·A =（p-1）(p-2)…（p-k ）≡（-1）(-2)…（-k ）(mod p )
又（k!，p ）=1，故A=k
p 1C -≡ （-1 ）k (mod p )
4、设p 是不等于3和7的奇质数，证明：p 6≡1(mod 84)。
说明：因为84=4×3×7，所以，只需证明：
p 6≡1(mod 4) p 6≡1(mod3) p 6≡1(mod 7) 同时成立即可。 证明：因为84=4×3×7及p 是不等于3和7的奇质数，所以
（p ，4）=1，（p ，3）=1，（p ，7）=1。
由欧拉定理知：p ?(4)≡p 2≡1(mod 4)，从而 p 6≡1(mod 4)。
同理可证：p 6≡1(mod3) p 6≡1(mod 7)。故有p 6≡1(mod 84)。
注：设p 是不等于3和7的奇质数，证明：p 6≡1(mod 168)。（见继源p86）
初等数论练习题二
一、填空题
1、τ(1000)=_16_；（除数函数：因数的个数）σ(1000)=_2340_.（和函数：所有因数的和）
2、2010!的规分解式中，质数11的次数是199__.
3、费尔马(Fermat)数是指Fn=n
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、??
? ??10146=_1__. 9、若p 是质数，n ∣p -1，则同余方程x n ≡ 1 (mod p ) 的解数为n .
二、计算题
1、试求200420032002被19除所得的余数。
解：由2002≡7 (mod 19)20022≡11(mod 19)20023≡1 (mod 19)
又由20032004≡22004≡（22）1002≡1 (mod 3)可得：
200420032002≡20023n+1≡(20023)n ×2002≡7(mod 19)
2、解同余方程3x 14+4x 10+ 6x -18 ≡0 (mod 5)。
解：由Fermat 定理，x 5≡x (mod 5)，因此，原同余方程等价于2x 2+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 应为其中使5x ≡ 1 (mod12)成立的最小数，经计算知：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 = n 1n 2，1
0 ≡-1(mod n 1)，矛盾。故n 是素数。
3、证明：设p s 表示全部由1组成的s 位十进制数，若p s 是素数，则s 也是一个素数。 证明：假设s 是合数，即s=ab ，1
M p a b a s s
s ?-=-=-==911091)10(9110111 ，其中M ＞1是正整数。 由p a ＞1也是正整数知p s 是合数，这与题设矛盾。故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的质数，证明：p 4≡1(mod 240)。（提示：可由欧拉定理证明） 证明：因为240=23×3×5，所以只需证：p 4≡1(mod 8)，p 4≡1(mod 3)，p 4≡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 使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
4、不是同余方程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。
2、数20100C 的规分解式中，质因数7的指数是_3。
3、每个数都有一个最小质因数。所有不大于10000的合数的最小质因数中，最大者是97。
4、同余方程24x ≡6(mod34)的解是x 1≡13(mod34) x 2≡30(mod34)_。
5、整数n>1，且(n-1)!+1≡0(mod n)，则n 为素数。
6、3103被11除所得余数是_5_。
7、??
? ??9760=_-1_。 三、计算题
1、判定(ⅰ) 2x 3-x 2+ 3x -1 ≡0 (mod 5)是否有三个解；
(ⅱ) x 6+2x 5- 4x 2+ 3 ≡0 (mod 5)是否有六个解？
解：(ⅰ) 2x 3-x 2+ 3x -1 ≡0 (mod 5)等价于x 3-3x 2+ 4x -3 ≡0 (mod 5)，又x 5-x = (x 3-3x 2+ 4x -3)(x 2+ 3x +5) + (6x 2-12x + 15)，其中r (x ) = 6x 2-12x + 15的系数不都是
5的倍数，故原方程没有三个解。
(ⅱ) 因为这是对模5的同余方程，故原方程不可能有六个解。
2、设n 是正整数，求1223212C ,,C ,C -n n
n n 的最大公约数。 解：设12122321212232122C C C )C ,,C ,(C ---=+++=n n n n n n n n n d ，由知d ∣22n -1，
设2k |n 且2k+1|/n ，即2k +1||n ，
则由2k +1||1122112C 2C 2C |--+=i n i n k n i
n 及，i = 3， 5， ， 2n - 1得d = 2k + 1。
3、已知a=18，m=77，求使a x ≡ 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 (mod77)成立的最小数，经计算知：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的质数，证明：p 2≡q 2(mod 24)。
证明：因为24=3×8，（3，8）=1，所以只需证明：
p 2≡q 2(mod 3) p 2≡q 2(mod 8)同时成立。
事实上， 由于（p ，3）=1，（q ，3）=1，所以p 2≡1(mod 3) ， q 2≡1(mod 3)，