【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《广东石油化工学院数学2009级初等数论复习资料》，欢迎阅读！
1．设r是正奇数，证明：对任意的正整数n，有
n 2|1r 2 r n r。
解 对于任意的正整数a，b以及正奇数k，有
ak bk = (a b)(ak 1 ak 2b ak 3b2 bk 1) = (a b)q， 其中q是整数。记s = 1r 2 r n r，则
2s = 2 (2 r n r) (3 r (n 1)r) (n r 2 r) = 2 (n 2)Q，
其中Q是整数。若n 2s，由上式知n 22，因为n 2 > 2，这是不可能的，所以n 2 |s。
2．证明：存在无穷多个正整数a，使得
n4 a（n = 1, 2, 3, ） 都是合数。
解 取a = 4k4，对于任意的nN，有
n4 4k4 = (n2 2k2)2 4n2k2 = (n2 2k2 2nk)(n2 2k2 2nk)。
因为
n2 2k2 2nk = (n k)2 k2 k2，
所以，对于任意的k = 2, 3, 以及任意的nN，n4 a是合数。
3．证明：若a被9除的余数是3，4，5或6，则方程x3 y3 = a没有整数解。 解 对任意的整数x，y，记
x = 3q1 r1，y = 3q2 r2，0 r1, r2 < 3。
则存在Q1, R1, Q2, R2Z，使得
x3 = 9Q1 R1，y3 = 9Q2 R2 ，
其中R1和R2被9除的余数分别与r13和r23被9除的余数相同，即
R1 = 0，1或8，R2 = 0，1或8。 (1)
因此
x3 y3 = 9(Q1 Q2) R1 R2 。
又由式(1)可知，R1 R2被9除的余数只可能是0，1，2，7或8，所以，x3 y3不可能等于a 。
4．证明：若n是正整数，则
21n4
是既约分数。
14n3
解 (21n 4, 14n 3) = (7n 1, 14n 3) = (7n 1, 1) = 1。 注：一般地，若(x, y) = 1，那么，对于任意的整数a，b，有
(x, y) = (x ay, y) = (x ay, y b(x ay)) = (x ay, (ab 1)y bx)， 因此，
xay
是既约分数。
(ab1)ybx
5．用辗转相除法求(125, 17)，以及x，y，使得
125x 17y = (125, 17)。
解 做辗转相除法：
125 = 717 6，q1 = 7，r1 = 6， 17 = 26 5， q2 = 2，r2 = 5， 6 = 15 1， q3 = 1，r3 = 1， 5 = 51， q4 = 5。
由定理4，(125, 17) = r3 = 1。
利用定理2计算（n = 3）
1 / 14
P0 = 1，P1 = 7，P2 = 27 1 = 15，P3 = 115 7 = 22， Q0 = 0，Q1 = 1，Q2 = 21 0 = 2，Q3 = 12 1 = 3，
取x = (1)3 1Q3 = 3，y = (1)3P3 = 22，则
1253 17(22) = (125, 17) = 1。
6．求(12345, 678)。
解 (12345, 678) = (12345, 339) = (12006, 339) = (6003, 339)
= (5664, 339) = (177, 339) = (177, 162) = (177, 81) = (96, 81) = (3, 81) = 3。 7．写出51480的标准分解式。 解 我们有
51480 = 225740 = 2212870 = 236435
= 2351287 = 2353429
= 23532143 = 233251113。
8．求最大的正整数k，使得10k199!。
解 由定理3，199!的标准分解式中所含的5的幂指数是
[199][199][199]
5
52
53
所以，所求的最大整数是k = 47。
9．设x与y是实数，则
= 47，
[2x] [2y] [x] [x y] [y]。 (1)
解 设x = [x] ，0 < 1，y = [y] ，0 < 1，则
[x] [x y] [y] = 2[x] 2[y] [ ]， (2) [2x] [2y] = 2[x] 2[y] [2] [2]。 (3)
如果[ ] = 0，那么显然有[ ] [2] [2]； 如果[ ] = 1，那么与中至少有一个不小于
1
，于是 2
[2] [2] 1 = [ ]。
因此无论[ ] = 0或1，都有[ ] [2] [2]，由此及式(2)和式(3)可以推出式(1)。
10．若a > 1，a n 1是素数，则a = 2，并且n是素数。 解 若a > 2，则由
an 1 = (a 1)(an 1 an 2 1) 可知a n 1是合数。所以a = 2。
若n是合数，则n = xy，x > 1，y > 1，于是由
2xy 1 = (2x 1)(2x(y 1) 2x(y 2) 1) 以及2x 1 > 1可知2n 1是合数，所以2n 1是素数时，n必是素数。
注：若n是素数，则称2n 1是Mersenne数。
11．求N =an1an2
a1a0被7整除的条件，并说明1123456789能否被7整除。
a1a0a2a1a0100a5a4a3103
(mod7)，
。
解 100 1，101 3，102 2，103 1 (mod 7)，因此
Nan1an2
即
a2a1a0a5a4a3a8a7a6
7N 7a2a1a0a5a4a3a8a7a6
2 / 14
由于
789 456 123 1 = 455，7455，
所以71123456789。
12．说明225
1是否被641整除。 解 依次计算同余式
22 4，24 16，28 256，216 154，232 1 (mod 641)。
因此
225
1 0 (mod 641)，
即641225
1。
13．求(25733 46)26被50除的余数。 解 利用欧拉定理有
(25733 46)26 (733 4)26 = [7(72)16 4]26
[7( 1)16 4]26 = (7 4)26
326 = 3(35)5 3(7)5 = 37(72)2 21 29 (mod 50)，
即所求的余数是29。
14．求n =777
的个位数。 解 我们有
71 3，72 1，74 1 (mod 10)，
因此，若
77 r (mod 4)，
则
n =777
77
(mod 10)。 现在77
(1)7 1 3 (mod 4)，所以由式(1)得到
n =777
73 (3)3 7 3 (mod 10)，
即n的个位数是3。
注：一般地，若求abc
对模m的同余，可分以下步骤进行： (ⅰ) 求出整数k，使ak 1 (mod m)；
(ⅱ) 求出正整数r，r < k，使得bc
r (mod k)； (ⅲ) abc
a r (mod m)。
15．证明：若n是正整数，则1342n + 1 3 n + 2 。 解 由
42n + 1 3 n + 2 = 442n 93 n = 416n 93 n
43n 93 n = 133 n
0 (mod 13)
得证。
16．证明：若2|
a，n是正整数，则 a2n
1 (mod 2n + 2)。 解 设a = 2k 1，当n = 1时，有
a2 = (2k 1)2 = 4k(k 1) 1 1 (mod 23)，
即式(4)成立。
设式(1)对于n = k成立，则有
a2k 1 (mod 2k + 2) a2k
= 1 q2k + 2，
3 / 14
(1)
(1)
其中qZ，所以
= (1 q2k + 2)2 = 1 q 2k + 3 1 (mod 2k + 3)，
其中q 是某个整数。这说明式(4)当n = k 1也成立。
由归纳法知式(1)对所有正整数n成立。
17．设n的十进制表示是13xy45z，若792n，求x，y，z。 解 因为792 = 8911，故
792n 8n，9n及11n。
我们有 以及
8n 845z z = 6，
a
2k1
9n 91 3 x y 4 5 z = 19 x y 9x y 1， (1) 11n 11z 5 4 y x 3 1 = 3 y x 113 y x。 (2)
由于0 x, y 9，所以由式(1)与式(2)分别得出
x y 1 = 9或18， 3 y x = 0或11。
这样得到四个方程组：
xy1a
，
3yxb
其中a取值9或18，b取值0或11。在0 x, y 9的条件下解这四个方程组，得到x = 8，y = 0，z = 6。
18．设整数n 2，证明：
1in(i,n)1
i
1
n(n)， 2
1
n(n)。 2
即在数列1, 2, , n中，与n互素的整数之和是
解 设在1, 2, , n中与n互素的(n)个数是
a1, a2, , a(n)，(ai, n) = 1，1 ai n 1，1 i (n)，
则
(n ai, n) = 1，1 n ai n 1，1 i (n)，
因此，集合{a1, a2, , a(n)}与集合{n a1, n a2, , n a(n)}是相同的，于是
a1 a2 a(n) = (n a1) (n a2) (n a(n))，
2(a1 a2 a(n)) = n(n)，
因此
a1 a2 a(n) =
19．设nN，证明：
(ⅰ) 若n是奇数，则(4n) = 2(n)； (ⅱ) (n) =
1
n(n)。 2
1
n的充要条件是n = 2k，kN； 2
4 / 14
(ⅲ) (n) =n的充要条件是n = 2k3l，k, lN； (ⅳ) 若6n，则(n)
13
1n； 3
13
(ⅴ) 若n 1与n 1都是素数，n > 4，则(n) n。 解 (ⅰ) 我们有
(4n) = (22n) = (22)(n) = 2(n)；
(ⅱ) 若n = 2k，则
(2k) =2k(1
若(n) =
1
)2k11n， 22
1
n，设n = 2kn1，2|n1，则由 2
1
n= (n) = (2kn1) = (2k)(n1) =2k 1(n1) 2
1k(n1)1(n1) =2n1 n2n12n1
1l
)3(11)1n。 233
推出(n1) = n1，所以n1 = 1，即n = 2k；
(ⅲ) 若n = 2k3l，则
(n) = (2k)(3l) =2k(1
|n1，则由 若(n) =n，设n = 2k3ln1，6
1
3
11(n1)
n(n)(2k3ln1)(2k)(3l)(n1)n
33n1
推出(n1) = n1，所以n1 = 1，即n = 2k3l；
|n1，则 (ⅳ) 设n = 2k3ln1，6
(n) = (2k)(3l)(n1) =2k3l(n1)
1
31kl1
23n1n； 33
(ⅴ) 因为n > 4，所以n 1与n 1都是奇素数，所以n是偶数。
因为n 1 > 3，所以n 1与n 1都不等于3，当然不被3整除，所以3n，因此6n。再由上面已经证明的结论(ⅳ)，即可得到结论(ⅴ)。
|1n 2n 3n 4n的充要条件是4n。 20．设n是正整数，则5
解 因为(5) = 4，所以，由定理2
k4 1 (mod 5)，1 k 4。
因此，若n = 4q r，0 r 3，则
1n 2n 3n 4n 1r 2r 3r 4r 1r 2r (2)r (1)r (mod 5)，(1)
用r = 0，1，2，3，4分别代入式(1)即可得出所需结论。
21．将211 1 = 2047分解因数。
解 由例5，若p211 1，则p 1 (mod 22)，即p只能在数列
23，45，67，，22k 1，
5 / 14
中。逐个用其中的素数去除2047，得到
232047，2047 = 2389。
方程x2 dy2 = 1的解。
22．求不定方程3x 6y = 15的解。 解 (3, 6) = 315，所以方程有解。 由辗转相除法（或直接观察），可知x = 1，y = 1是
3x 6y = 3
的解，所以x0 = 5，y0 = 5是原方程的一个解。由定理2，所求方程的解是
x52t
5t
， tZ。 y23．求不定方程3x 6y 12z = 15的解。 解 原方程等价于
x 2y 4z = 5。 依次解方程
t 4z = 5， x 2y = t，
分别得到
t14u
， uZ，
z1u
xt2v
ytv
， vZ。 将式(2)与式(3)中的t消去，得到
x14u2vy14uv， u, vZ。
z1u24．将
19
30
写成三个分数之和，它们的分母分别是2，3和5。 解 设
1930x2y3z5
， 则
15x 10y 6z = 19。
依次解方程
5t 6z = 19， 15x 10y = 5t，
得到
t16u
， u
z45uZ，
xt2v
， vZ。 yt3v
6 / 14
(1)
(2) (3) (1) (2)
从式(1)与式(2)中消去t，得到
x16u2v
y16u3v， u, vZ。 z45u
取u = 0，v = 0，得到x = 1，y = 1，z = 4，因此
19114。 30235
25． 甲物每斤5元，乙物每斤3元，丙物每三斤1元，现在用100元买这三样东西
共100斤，问各买几斤?
解 设买甲物x斤，乙物y斤，丙物z斤，则
5x 3y
1
3
z = 100， x y z = 100。
消去z，得到
7x 4y = 100。 显然x = 0，y = 25是方程(1)的解，因此，方程(18)的一般解是
x4t
y257t
， tZ 因为x 0，y 0，所以
0 t 3。
即t可以取值t1 = 0，t2 = 1，t3 = 2，t4 = 3。相应的x，y，z的值是
(x, y, z) = (0, 25, 75)，(4, 18, 78)，(8, 11, 81)，(12, 4, 84)。 26．求不定方程x 2y 3z = 7的所有正整数解。 解 依次解方程
t 3z = 7， x 2y = t，
得到
t13u
z2u， uZ，
xt2v
yv
， vZ。 从上式中消去t，得到
x13u2vy
v， u, vZ。
z2u要使x 1，y 1，z 1，则应有
3u 2v 0，v 1，1 u 0。 所以
3u 2v 2，u 1
2
3
u 1， 7 / 14
(1)
(1) (2)
即 u = 1。由此及式(2)，有
3 2v 0，v 1
2
v 1， 3
所以v = 1。将u = 1，v = 1代入式(1)，得到原方程的唯一一组正整数x = 2，y = 1，z = 1。
27．解同余方程
325x 20 (mod 161) (1)
解 同余方程(1)即是
3x 20 (mod 161)。
解同余方程
161y 20 (mod 3)， 2y 1 (mod 3)，
得到y 2 (mod 3)，因此方程(1)的解是
x
202161
3
= 114 (mod 161)。 27．解同余方程6x 7 (mod 23)。 解 依次得到
6x 7 (mod 23) 5x 73 2 (mod 23)
3x 24 8 (mod 23) 2x 8(7) 10 (mod 23) x 5 (mod 23)。
28．求整数n，它被3，5，7除的余数分别是1，2，3。 解 n是同余方程组
n 1 (mod 3)，n 2 (mod 5)，n 3 (mod 7)
的解。在孙子定理中，取
m1 = 3，m2 = 5，m3 = 7，m = 357 = 105，
M1 = 35，M2 = 21，M3 = 15， M1 = 1，M2 = 1，M3 = 1，
则
n 135(1) 2211 3151 52 (mod 105)，
因此所求的整数n = 52 + 105t，tZ。
29．解同余方程
5x2 6x 49 0 (mod 60)。 解 因为60 = 345，所以，同余方程(15)等价于同余方程组
5x2 6x 49 0 (mod 3) 5x2 6x 49 0 (mod 4) 5x2 6x 49 0 (mod 5)。 分别解同余方程(16)，(17)，(18)得到解
x1(1) 1，x2(1) 1 (mod 3)， x1(2) 1，x2(2) 1 (mod 4)， x1(3) 1 (mod 5)，
这样，同余方程(1)的解x可由下面的方程组决定：
x a1 (mod 3)，x a2 (mod 4)，x a3 (mod 5)，
其中a1 = 1或 1，a2 = 1或 1，a3 = 1。利用孙子定理，取
m1 = 3，m2 = 4，m3 = 5，m = 60， M1 = 20，M2 = 15，M3 = 12，
8 / 14
(1)
(2) (3) (4)
M1 = 2，M2 = 1，M3 = 3，
则
x 40a1 15a2 36a3 (mod 60)。
将a1，a2，a3所有可能的取值代入上式，得到方程(1)的全部解是
x1 401 151 361 1 (mod 60)，
x2 40(1) 151 361 19 (mod 60)， x3 401 15(1) 361 31 (mod 60)， x4 40(1) 15(1) 361 11 (mod 60)。
30．解同余方程
x3 3x 14 0 (mod 45)。
解 原同余方程等价于同余方程组
x3 3x 14 0 (mod 9)， (1) x3 3x 14 0 (mod 5)。 (2)
先解同余方程(1)。容易验证，同余方程x3 3x 14 0 (mod 3)的解是x 2 (mod 3)。 令x = 2 3t并代入方程(7)，得到
(2 3t)3 3(2 3t) 14 0 (mod 9)， (3)
容易看出，这是一个对于任何整数t都成立的同余式，所以，方程(9)的解是t 0，1，2 (mod 3)，于是方程(1)的解是
x 2，5，8 (mod 9)。 (4)
再解同余方程(2)。用x = 0，1，2，3，4去验证，得到(2)的解是
x 1，2 (mod 5)。
因此，原同余方程的解是下面六个同余方程组的解：
x a1 (mod 9)， a1 = 2，5，8， x a2 (mod 5)， a2 = 1，2。
利用孙子定理解这六个方程组，记
m1 = 9，m2 = 5，m = 45，M1 = 5，M2 = 9，M1 = 2，M2 = 1， 则
x 10a1 9a2 (mod 45)。
将a1和a2的不同取值代入，得到所求的解是
x1 102 91 11 (mod 45)， x2 102 92 2 (mod 45)， x3 105 91 41 (mod 45)， x4 105 92 32 (mod 45)， x5 108 91 26 (mod 45)， x6 108 92 17 (mod 45)。
31．解同余方程
2x2 13x 34 0 (mod 53)。 (1)
解 容易验证，同余方程
2x2 13x 34 0 (mod 5) (2)
有两个解x 1，2 (mod 5)。
令
x = 1 5t， (3)
代入同余方程
2x2 13 34 0 (mod 52)， (4)
得到
9 / 14
2(1 5t)2 13(1 5t) 34 0 (mod 25)，
45 45t 0 (mod 25)，
9t 9 (mod 5)，t 1 (mod 5)。 (5)
于是，将式(5)与式(3)联合，得到方程(4)的解
x = 1 5(1 5t1) = 4 25t1，t1Z。 (6)
将式(6)中的x代入同余方程(1)，得到
2(4 25t1)2 13(4 25t1) 34 0 (mod 53)，
50 725t1 0 (mod 53)， 2 29t1 0 (mod 5)， t1 2 (mod 5)。
将上式与(6)联合，得到同余方程(1)的一个解
x = 4 25t1 = 4 25(2 5t2) 54 (mod 53)。
(ⅱ) 从同余方程(2)的另一个解 x 2 (mod 5)出发利用上述方法，可以求出同余方程(11)的另一个解。（略，请读者补足）。
32．判定同余方程2x3 3x 1 0 (mod 7)是否有三个解。 解 因为24 1 (mod 7)，所以，原方程与
42x3 43x 4 0 (mod 7)
即
x3 2x 3 0 (mod 7)
等价。由于
x7 x = ( x3 2x 3)(x4 2x2 3x 4) 12x2 16x 12，
所以，原方程的解数小于3。
33．解同余方程
3x14 4x10 6x 18 0 (mod 5)。
解 由Fermat定理，x5 x (mod 5)，因此，原同余方程等价于
2x2 x 3 0 (mod 5)。 (1)
将x 0，1，2 (mod 5)分别代入方程(1)进行验证，可知这个同余方程解是x 1 (mod 5)。
34．判断方程x2 5 (mod 11)有没有解。 解 因为
111
5
()52555545321 (mod 11)， 11
方程有解。
35．已知563是素数，判定方程x2 429 (mod 563)是否有解。 解 利用已有的定理，有
(429)(31113)(
3
)(11)(13)
563563563563563
31563111156311315631
563563
(1)22()(1)22()(1)22(563)
31113
224
()()()(1)(1)1。31113
方程有解。
【例5】判断3是否是模17的平方剩余。
10 / 14
17131
317222（解）＝1＝＝－1
1733
所以，3是模17的平方非剩余。（不但如此，17也是3的平方非剩余，即2是3的平方非
剩余）
【例6】判断同余方程x≡137（mod 227）是否有解。 （解）已知137与227均为奇数，所以
2271371
1372279022＝1＝
2271371372
2325255
＝＝＝ 137137137137
＝1
13715122
1372
＝＝－1 55
所以，方程无解。
2
137901235另法： ＝＝
227227227227
2271512522722＝－＝1 2272275
＝＝－1
【例7】判断同余方程x≡－1（mod 365）是否有解，若有解，求解数。 （解）由于365＝5·73，所以
2
x12
x≡－1（mod 365） 2
x1
2
2
5
mod5
mod73
11＝＝1 573
所以方程有解，且解数为4。
【例8】判断同余方程x≡2（mod 3599）是否有解，若有解，求解数。 （解）由于3599＝59·61，所以
2
11 / 14
2x22
x≡2（mod 3599） 2
x2
mod59
mod61
因为59≡3（mod 8），即
22
x＝－1，故方程≡2（mod 59）无解，从而原方程无解。
59
x2 12345 (mod 3371) (1)
38．已知3371是素数，判断方程 是否有解。
解 利用Jacobi符号的性质，有
(12345)(2232)(
3371
3371(1)
3371218
2
)(4)(279)337133713371
337112791
22
279
2791231
23
()(1)22(279)27923
23131
323
()(1)22()1。
233
因此，方程(1)无解。
39．判断137是否为模227的平方剩余。
解：首先，227是素数。其次，计算
(1)
(23)
13722712≡－1（mod 227）
所以，137是模227的平方非剩余。 40．求ord33(4)、ord33(5)、ord33(7)的值。
（解）(33)＝20，故由推论知只需计算4、5、7（mod 33）即可，其中i＝1, 2, 4, 5, 10。
105
45≡1（mod 33），5≡23（mod 33），5≡1（mod 33）， 1075≡10（mod 33），7≡1（mod 33）
i
ii
所以，ord33(4)＝5，ord33(5)＝10，ord33(7)＝10。
41．由ord17(5)＝16可知5是模17的原根，由原根5就可以求出17的所有原根：
3551≡5（mod 17），5≡6（mod 17），5≡14，（mod 17） 11957≡10（mod 17），5≡12（mod 17），5≡11，（mod 17） 15513≡13（mod 17），5≡6（mod 17）
42．求出模25的所有原根。
12 / 14
（解）首先，(25)＝20，((25))＝(20)＝8。故25若有原根，则其必有8个原根。
计算2≡7（mod 25），2≡24≡-1（mod 25），所以2是模25的一个原根。 20的简化剩余系为{1, 3, 7, 9, 11, 13, 17, 19}，25的所有原根为：
5
10
21≡2，23≡8，27≡3，29≡12，211≡23， 213≡17，217≡22，219≡13（mod 17）
即模25的原根为：2, 3, 8, 12, 13, 17, 22, 23。 43．求模41的所有原根。
（解）(m)＝(41)＝40＝2·5，q1＝2，q2＝5，mq1＝20，mq2＝8，故
3
只需验证
g8，g20≡1？ （mod 41）
验算：2≡10，2≡1（mod 41），2不是原根。
8
20
38≡1（mod 41），3不是原根。 420＝240≡1（mod 41），4不是原根。
58≡18，520≡1（mod 41），5不是原根。 68≡10，620≡40≡－1（mod 41），6是原根。
再由(41)＝40的简化剩余系为
1，3，7，9，11，13，17，19，
21，23，27，29，31，33，37，39 共有((41))＝ (40)＝16个数，那么原根为
61≡6，63≡11，……，639≡7（mod 41）
2
44．设模数m＝41＝1681，求模m的原根。
（解）已知6是模41的原根，故由2，6或6＋41＝47是模41＝1681的原根。计算
2
640≡143≡1＋41·3（mod 412）， 4740≡1518≡1＋41·37（mod 412）
即
240
640≠1（mod 412），47≠1（mod 41）
2
所以6和47都是模1681的原根（因(41)＝1640＝41·40）。
另由定理5.2.3，6和47是所有模41的原根。
13 / 14
45．设模数m＝2·41＝3362，求模m的原根。
2
41（解）由44题知6和47是模41的原根，故由定理4知，6＋41＝1687和47是模2·
＝3362的原根。
222
14 / 14
本文来源：https://www.wddqxz.cn/59bfe4d0740bf78a6529647d27284b73f2423696.html
2022-08-04
