一、整除理论 1．
证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。 2．
设p是n的最小素约数，n = pn1，n1 > 1，证明：若p >3n，则n1是素数。
3
证明：设不然，n1 = n2n3，n2 ? p，n3 ? p，于是n = pn2n3 ? p， 即p ?3n，矛盾。 3．
设3?a2 ? b2，证明：3?a且3?b。
由3?a2 ? b2 = 3Q ? r12 ? r22知r1 = r2 = 0，即 3?a且3?b 4．
证明：对于任意给定的n个整数，必可以从中找出若干个作和，使得这个和能被n整除。
写a = 3q1 ? r1，b = 3q2 ? r2，r1, r2 = 0, 1或2，
设给定的n个整数为a1, a2, ?, an，作 s1 = a1，s2 = a1 ? a2，?，sn = a1 ? a2 ? ? ? an，
如果si中有一个被n整除，则结论已真，否则存在si，sj，i < j， 使得si与sj被n除的余数相等，于是n?sj ? si = ai + 1 ? ? ? 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) 因为
用类似于例3的方法即可得证。
6．
，故只须证明(a, b, c)(ab, bc, ca) = (a, b)(b, c) (c, a)，此式
设k是正奇数，证明：1 ? 2 ? …… ? 9?1k ? 2k ? …… ? 9k。
设s = 1k ? 2k ? ? ? 9k，则由2s = (1k ? 9k) ? (2k ? 8k) ? ? ? (9k ? 1k) = 10q1及2s = (0k ? 9k) ? (1k ? 8k) ? ? ? (9k ? 0k) = 9q2得10?2s和9?2s，于是有90?2s，从而1 ? 2 ? ? ? 9 = 45?s 7．
设a，b是正整数，证明：(a ? b)[a, b] = a[b, a ? b]。
只须证，即只须证(b, a ? b) = (a, b)，此式显然。
8． 用扩展欧几里德算法法求整数x，y，使得1387x ? 162y = (1387, 162)。
作辗转相除：1387 = (?162)?(?8) ? 91，?162 = 91?(?2) ? 20，91 = 20?4 ? 11，20 = 11?1 ? 9，11 = 9?1 ? 2，9 = 2?4 ? 1，2 = 1?2 ? 0，由此得n = 6，q1 = ?8，q2 = ?2，q3 = 4，q4 = 1，q5 = 1，q6 = 4，x = (?1)n?1Qn = 73，y = (?1)nPn = 625，又(1387, 162) = rn = 1，故1387?73 ? 162?625 = 1 = (1387, 162)
9. 若四个整数2836，4582，5164，6522被同一个大于1的整数除所得的余数相同，且不等于零，求除数和余数各是多少。 设除数为d，余数为r，则由
d?4582 ? 2836 = 1746，d?5164 ? 4582 = 582，d?6522 ? 5164 = 1358 知d?(1746, 582, 1358) = 194，由此得d = 97，r = 23或d = 194，r = 120 9．
证明：在1, 2, ?, 2n中任取n ? 1数，其中至少有一个能被另一个整除。
1
写i = 10．
，i = 1, 2, ?, 2n，则?i为1, 2, ?, 2n中的奇数，即?i只能取n个数值，在n ? 1个这样的
数中，必存在?i = ?j（i ? j），于是易知i与j成倍数关系
求最大的正整数k，使得10k?199!。
解 由定理3，199!的标准分解式中所含的5的幂指数是
[199]?[199]?[199]?... = 47，
55253而所含2的幂指数>47，所以，所求的最大整数是k = 47。
11．
设n是正整数，则[n?n?1]?[4n?2]。
解 首先，我们有 [ <所以，
若上式中的等式不成立，即
则存在整数a,使得 所以
a2-2n-1=2n+1,
a2=4n+2.
但是，无论2|n 或2n,式(10)都不能成立，这个矛盾说明式（9）不能成立，即式(7)成立. 12．
n?2r?1]= n。 设n是正整数，x是实数，证明：?[r2r?1?]
，
.
，
, 因此
, ,
,
由例4得
= [2x]? [x]，于是
=[n] = n 。
例4 设x是正数，n是正整数，则
[x]+[x+]+[x+]+ . . . +[x+]=[nx].
2
解 设x=[x]+ , , 0in-1,则
[x]+[x+]+[x+]+ . . . +[x+]= n[x]+i=n[x]+[n]
=[n([x]+)]=[nx]. 13．
证明：若2n ? 1是素数，则n是素数。
< 2n + 1，表明2n ? 1是合数，矛盾。
设不然，则n = n1n2， 1 < n1 < n，则2n ? 1 = 同余
1． 求81234被13除的余数。
因为82 ? ?1(mod 13)，所以81234 = (82)617 ? (?1)617 ? ?1 ? 12 (mod 13)，即81234被13除的余数是12。 2． 已知99?62??427，求?与?
由
?2或? ? ? = 9，于是解关于?，?的方程组
得? = 2，? = 4。 3． 求n =77的个位数
我们有
71≡-3, 72 ≡-1, 74 ≡1 (mod 10), 因此, 若
77 ≡r (mod 4), (3) 则 n=
≡ 7r (mod 10). (4)
≡3 (mod 4), 所以, 由式(4)可知
7
得? ? ? = 6或? ? ? = 15，从
得? ? ? =
现在, 71≡-1,72 ≡1, 77 ≡ n=
≡ 73 ≡
≡ -7≡ 3 (mod 10),
即n的个位数是3.
4． 证明：若n是正整数，则13?42n + 1 ? 3 n + 2 由 42n+1+3n+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的完全剩余系,所以
同理,
(mod m). (10)
3
(mod m). (11)
如果{a1+b1,… ,am+bm}是模m的完全剩余系,那么也有
(mod m).
联合上式与式(10)和(11),得到
0(mod m)，
这是不可能的,所以{a1+b1,… ,am+bm}不能是模m的完全剩余系. 6． 证明：若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)。 7． 证明Wilson定理的逆定理：若n > 1，并且(n ? 1)! ? ?1 (mod n)，则n是素数 设不然，n = n1n2，1 < n1 < n，由(n ? 1)! ? ?1 (mod n1)得0 ? ?1 (mod n1)，矛盾。
?(m)8． 设m > 1，(a, m) = 1，x1, x2,…, x?(m)是模m的简化剩余系，证明：
?{mi}?2?(m)。其中{x}表示x的
i?1ax1小数部分。
写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?(m), (ai,n)=1, 1 ai
n-1, 1
i(n),
则
(n-ai,n)=1,1≤n-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)
设
，则
由此得
4
?(mn)?((m, n)) = (m,n)
= (m, n)?(m)?(n)。
10．
设{x1, x2,…, x?(m)}是模m的简化剩余系，则(x1x2…x?(m))2 ? 1 (mod m)
设{x1, x2,…, x?(m)}是模m的简化剩余系，则(x1x2…x?(m))2 ? 1 (mod m)。 解 记P = x1x2…x?(m)，则(P, m) = 1。又记
yi =
P，1 ? i ? ?(m)， xi则{y1, y2, …, y?(m)}也是模m的简化剩余系，因此
?(m)i?1?xi??xi?1?(m)Pi(mod m)，
再由Euler定理，推出
P2 ? P?(m) ? 1 (mod m)。
11． 证明：1978103 ? 19783能被103整除。 因103 = 2353，显然1978103 ? 19783 ? 0 (mod 23)，再由1978100 ? 1 (mod 53)得1978103 ? 19783 ? 0 (mod 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 ? qp ? 1 ? 1 (mod
q)，故pq ? 1 ? qp ? 1 ? 1 (mod pq)。
13．
计算12996227(mod 37909)
二、同余方程
1． 解同余方程 325x ? 20 (mod 161) 解：方程即是 3x≡20(mod 161). 解同余方程
161y≡-20(mod 3), 即
2y≡1(mod 3),
得到 y≡2 (mod 3),因此,方程(6)的解是x≡
则恰有d?mn ?1个解，mod m
=114 (mod 161).
2． 证明：同余方程a1x1 ? a2x2 ? … ? anxn ? b (mod m)有解的充要条件是(a1, a2, …, an, m) = d?b。若有解，
必要性显然，下证充分性。当n = 1时，由定理2知命题成立。假设n = k时结论已真，考虑a1x1 ? a2x2 ? ? ? akxk ? ak + 1xk + 1 ? b (mod m)，令(a1, a2, ?, ak, m) = d1，(d1, ak + 1) = d，因为同余方程ak + 1xk + 1 ? b (mod d1)有解，其解数为d，mod d1，记m = d1m1，则解数为dm1，mod m。现在固定一个解xk + 1，由归纳假定知a1x1 ? a2x2 ? ? ? akxk ? b ? ak + 1xk + 1 (mod m)有解，其解数为d1 mk ?1，mod m，从而a1x1 ? a2x2 ? ? ? akxk ? ak + 1xk + 1
5