一、整除理论 1．
证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。 2．
设p是n的最小素约数，n = pn1，n1 > 1，证明：若p >3n，则n1是素数。
p， 即p
3
证明：设不然，n1 = n2n3，n2 p，n3 p，于是n = pn2n3 3．
设3a b，证明：3a且3
r1，b = 3q2
2
2
2
2
3n，矛盾。
b。
r2知r1 = r2 = 0，即 3a且3
2
写a = 3q1 r2，r1, r2 = 0, 1或2，
r1
2
由3a b = 3Q 4．
b
证明：对于任意给定的n个整数，必可以从中找出若干个作和，使得这个和能被n整除。
设给定的n个整数为a1, a2, L, an，作 s1 = a1，s2 = a1 a2，L，sn = a1 a2 L an，
如果si中有一个被n整除，则结论已真，否则存在si，sj，i < j， 使得si与sj被n除的余数相等，于是nsj si = ai + 1 L aj
5．
[a,b,c]2(a,b,c)2?设a，b，c是正整数，证明：
[a,b][b,c][c,a](a,b)(b,c)(c,a) 因为
，故只须证明(a, b, c)(ab, bc, ca) = (a, b)(b, c) (c,
a)，此式用类似于例3的方法即可得证。
6．
k设k是正奇数，证明：1 2 …… 91 2 …… 9。
kkkkkkkkkkkkkkkkk设s = 1 2 L 9，则由2s = (1 9) (2 8) L (9 1) = 10q1及2s = (0 9) (1 8) L (9 0) = 9q2得10457．
2s和92s，于是有902s，从而1 2 L 9 =
b]。
s
设a，b是正整数，证明：(a
b)[a, b] = a[b, a
只须证，即只须证(b, a b) = (a, b)，此式显然。
8． 用扩展欧几里德算法法求整数x，y，使得1387x 162y = (1387, 162)。 作辗转相除：1387 = (162)= 1，q5 = 1，q6 = 4，x = (162
(8) 91，1)
n1
162 = 91(2) 20，91 = 204 11，20 = 111
9，11 = 91 2，9 = 24 1，2 = 12 0，由此得n = 6，q1 = 8，q2 = 2，q3 = 4，q4
Qn = 73，y = (1)nPn = 625，又(1387, 162) = rn = 1，故138773
625 = 1 = (1387, 162)
9. 若四个整数2836，4582，5164，6522被同一个大于1的整数除所得的余数相同，且不等于零，求除数和余数各是多少。 设除数为d，余数为r，则由
d4582 2836 = 1746，d5164 4582 = 582，d6522 5164 = 1358
知d(1746, 582, 1358) = 194，由此得d = 97，r = 23或d = 194，r = 120 9． 写i =
证明：在1, 2, , 2n中任取n
，i = 1, 2, L, 2n，则
1数，其中至少有一个能被另一个整除。
i为1, 2, L, 2n中的奇数，即
i只能取n个数值，在n 1
个这样的数中，必存在10．
i =
j（i j），于是易知i与j成倍数关系
k求最大的正整数k，使得10199!。
解 由定理3，199!的标准分解式中所含的5的幂指数是
[199]?[199]?[199]?... = 47，
55253而所含2的幂指数>47，所以，所求的最大整数是k = 47。
11．
设n是正整数，则[n?n?1]?[4n?2]。
解 首先，我们有 [ <所以，
若上式中的等式不成立，即 则存在整数a,使得 所以
2
]
，
.
，
, 因此
, ,
,
a-2n-1=2n+1,
2
a=4n+2.
但是，无论2|n 或2n,式(10)都不能成立，这个矛盾说明式（9）不能成立，即式(7)成立. 12．
n?2r?1]= n。 设n是正整数，x是实数，证明：?[2rr?1?由例4得
= [2x] [x]，于是
=[n] = n 。
例4 设x是正数，n是正整数，则
[x]+[x+]+[x+]+ . . . +[x+]=[nx].
解 设x=[x]+ , , 0in-1,则
[x]+[x+]+[x+]+ . . . +[x+]= n[x]+i=n[x]+[n]
=[n([x]+)]=[nx]. 13．
证明：若2
n 1是素数，则n是素数。
n设不然，则n = n1n2， 1 < n1 < n，则2 1 = 数，矛盾。 同余
< 2 + 1，表明2 1是合
nn1． 求8被13除的余数。
2123426176171234
因为8 1(mod 13)，所以8 = (8) (1) 1 12 (mod 13)，即8被13除的余数是12。 2． 已知99
由
得 = 2或
= 9，于是解关于，
62??427，求
1234
与
得
= 6或
= 15，从
的方程组
得 = 2， = 4。 3． 求n =77的个位数
我们有
12 4
7≡-3, 7≡-1, 7≡1 (mod 10), 因此, 若
7
7≡r (mod 4), (3) 则
n=
≡
7
r
7(mod
10). (4) 现在, 7≡-1,7≡1, 7≡ n=即n的个位数是3.
4． 证明：若n是正整数，则13由 4
2n+1
1
2
7
≡3 (mod 4), 所以, 由式(4)可知
3
≡ 7≡4
2n + 1
≡ -7≡ 3 (mod 10),
n + 2
3
+3=
n+2
（mod 13）得证.
5． 设m > 0是偶数，{a1, a2, …, am}与{b1, b2, …, bm}都是模m的完全剩余系，证明：{a1 b1, a2 b2, …,
am bm}不是模m的完全剩余系
因为{1,2,… ,m}与{a1,… ,am}都是模m的完全剩余系,所以
m). (10) 同理,
(mod
m). (11) 如果{a1+b1,… ,am+bm}是模m的完全剩余系,那么也有
(mod
联合上式与式(10)和(11),得到
(mod m).
0(mod m)，
这是不可能的,所以{a1+b1,… ,am+bm}不能是模m的完全剩余系.
2p6． 证明：若2p 1是奇素数，则(p!) (1) 0 (mod 2p 1)
p22p由威尔逊定理知 1 (2p)! = p!(p 1)L(2p) (1)(p!)(mod 2p 1)，由此得(p!) (1) 0 (mod 2p 1)。
7． 证明Wilson定理的逆定理：若n > 1，并且(n 1)! 1 (mod n)，则n是素数
设不然，n = n1n2，1 < n1 < n，由(n 1)! 1 (mod n1)得0 1 (mod n1)，矛盾。 8． 设m > 1，(a, m) = 1，x1, x2,…, x(m)
是模m的简化剩余系，证明：
?(m)i?1?{mi}?2?(m)。其中{x}表示
ax1x的小数部分。
写axi = mqi ri，0 ri < m，由xi通过模m的简化剩余系知ri通过模m的最小非负简化剩余系，于是
由例1得
。
例1 设整数n 2,证明 即,在数列1,2,… ,n中,与n互素的整数之和是
解 设在1,2,… ,n中与n互素的(n)个数是 a1,… ,a则
(n-ai,n)=1,1≤n-ai≤n-1, 1
i
(n),
(m)
, (ai,n)=1, 1 ai
n-1, 1 i(n),
因此，集合{a1,… ,a(m)}与集合{n-a1, ,n-a(m)}是相同的，于是
a1+a2+… +a(m))=(n-a1)+(n-a2)+ +(n-a(m)), 2(a1+… +a(m))=n(n),
a1+… +a(m)
= (n).
9． 设m与n是正整数，证明：
(mn)((m, n)) = (m, n)(m)(n)
设
，则
由此得
(mn)((m, n)) = (m,n)
= (m, n)
(m)(n)。 10．
设{x2
1, x2,…, x(m)
}是模m的简化剩余系，则(x1x2…x(m)
)
1 (mod m)
设{x1, x2,…, x(m)
}是模m的简化剩余系，则(x1x2…x(m)
)2
1 (mod m)。
解 记P = x1x2…x(m)
，则(P, m) = 1。又记
yPi =
x，1 i (m)， i则{y1, y2, …, y(m)
}也是模m的简化剩余系，因此
??(m)?(m)xPi?(mod m)，
i?1?i?1xi再由Euler定理，推出
P2 P(m)
1 (mod m)。
11． 证明：1978103
19783
能被103
整除。 因103 = 2353，显然1978103 19783 0 (mod 23)，再由1978100 1 (mod 53)得1978103 19783
53)，故1978103 19783 0 (mod 103
)。
12． 设p，q是两个不同的素数，证明：pq 1 qp 1
1 (mod pq)。
由费马定理qp
1
1 (mod p)，pq
1
1 (mod q)，pq 1
qp
1
1 (mod p)，pq
1
1
1 (mod q)，故pq
1
qp
1
1 (mod pq)。
13．
计算(mod 37909)
二、同余方程
1． 解同余方程 325x 20 (mod 161) 解：方程即是
3x≡20(mod 161). 解同余方程
161y≡-20(mod 3), 即
2y≡1(mod 3),
qp
0 (mod
研究生基础数学1考试复习资料数论练习题
