t1a1?t2a2???tnan?1.
定理1. 7 设a1,a2,?,an是任意n个整数.且(a1,a2)?d2，(d2,a3)?d3,? ,
(dn?1,an)?dn，那么(a1,a2,?,an)?dn.
性质定理1.2 i) 如果(a,b)ii) 如果(a,b)iii) 如果(a,c)?1,则(ac,b)?(c,b)； ?1，且bac，则bc；
?1，且(c,b)?1，则(ab,c)?1；
(a,b)?a?，进而有?,b??1. c?(a,b)(a,b)?iv) 如果c,b???c?0?是a与b的公约数,则?acc以上性质均易证明(请读者自证).以下我们讨论最小公倍数: 定义1. 5 设a1,a2,?,an是n(n?2)个整数.
i) 如果d是每个ai的倍数，则称d是这n个数的公倍数； ii)
a1,a2,?,an的一切公倍数中的最小正整数称为它们的最小公倍数，记为
[a1,a2,?,an].
由于任意正数均不是0的倍数，所以任意包含0的一组整数其最小公倍数均不存在. 性质定理1.3 设a1,a2,?,an是n个全不为零的整数，则有 i) ii) iii)
0?[a1,a2,?,an]?|a1a2?an|. [a1,a2,?,an]?[|a1|,|a2|,?,|an|]. [a1k,a2k,?,ank]?[a1,a2,?,an]|k|.
以上性质请读者自证.
定理1. 8 设a,b是任意两个全不为零的整数，若m是a,b的任意一公倍数，则有 i) ii)
[a,b]|m；
[a,b](a,b)?ab (ab?0);
iii)
m?mm?. ,????ab?[a,b] 6
类似于定理1. 7，我们有：
定理1. 9 设
a1,a2,?,an是n个全不为零的整数，[a1,a2]?m2，[m2,a3]?m3，?，
[mn?1,an]?mn，则有 [a1,a2,?,an]?mn.
例1. 4 i）求[136,221,391]?? 解 i)
?136,221,391??[[136,221],391]?[?136?221,391]??1768,391?.
171768?391?40664. （其中因为?136,221??17）. ▋
17练习1. 3
1. 对给定正整数a,b,c，证明
1) 如果a2) 如果a3)
b，那么abc. b且ac，那么a2bc.
ab当且仅当acbc，其中c?0.
2. 对于任意的正整数a，则三个整数a, a?2, a?4中必有一个能被3整除. 3. 对于任意的正整数a，证明2|a(a?1)，3|a(a?1)(a?2). 4. 设n是正整数，证明[an,bn]?[a,b]n.
5. 证明[a1,a2,?,ak,ak?1,?,an]?[[a1,a2,?,ak],[ak?1,?,an]]. 6. 证明下列结论
1) 如果a是奇数，那么24|a(a2?1)；
22) 如果a,b都是奇数，那么a|(a?b2)；
23) 对于任意的整数a，都有360|a(a2?1)(a2?4).
§1. 4 质数与合数
我们可以将整数分成两类，即奇数类与偶数类；当我们讨论正整数时，也可以将大于1的正整数分为两类，对于任何一个正整数a,它至少有两个正约数，即1与a, 称a得当然约数.有些正整数只是这两个当然约数，如3，5，7等，而另一些正整数则还有其它正约数，如6，还有约数2与3，这类约数称非当然约数或真约数.
7
定义1. 6 设a是一个大于1的正整数，如果a只有当然约数，则称a为质数或素数；若a有真约数，则称a为合数.
于是，正整数={1}?质数集?合数集. 性质定理1.4 设
p是任一质数，则有
i) 对任一整数a, 有(a,ii) 如果iii) 如果
p)?1或p|a.
p|ab, 则p|a或p|b.
p|a1a2?an则存在某i, 使p|ai.
p)|p, 而p为质数，于是(a,p)?1或p, 若(a,p)?p，即有pa.
证 i） 因为(a,ii) 如果
p?a, 则由（i）知(a,p)?1，由已知pab，于是由性质定理1. 4知pb.
iii) 此条是ii）的推广. ▋ 例1. 5 如果m是合数，试证nm证 设m?1?1也是合数. ?m?ab，那么
10m?1?(10a)b?1?(10a?1)(10?即
ab?1????10a?1)
9?1?1?9?1?1?(10a(b?1)???10a?1). ??m个a个所以1?1是nm的因数. ▋ ?a个练习1. 4
1. 证明奇素数可表示为两个自然数的平方差. 2. 设n是大于2的整数，则如果23. 试证正整数10?01是合数. ?2000个n?1和2n?1中有一为素数，那么另一数必为合数.
4. 设
p和pn+1均为素数，则p?2且n为2的方幂.
§1. 5 整数的分解—算术基本定理
任一大于1的整数a或者是素数，或者是合数，如果a是一个合数，设约数，则
p1是a的大于1的最小的正
p1是一个素数，且存在正整数q1使a?p1q1,(1?q1?a). 如果q1是一个素数，则a就表
p2，于是a?p1p2a2.如果a2是素数，则就表成
8
成了两个素数之积，如果q1非素数，则q1有素因数
三个素数之积，否则a2有素因数p3，如此继续下去，可知a一定可以表成若干个素数之积.
算术基本定理 设a是任一大于1的整数，则a能表成若干个素数的积： a=
其中
p1p2?pn, p1?p2???pn. (1.5.1)
p1,p2,?,pn是素数，且表达式(1.5.1)是唯一的.
我们将相同的pi可能有相同的，
算术基本定理也可以称为整数的唯一分解定理.(1.5.2)式中的素数素因数合写成方幂的形式，则有
a?p1?1p2?2?pk?k,?i?0,(i?1,2,?,k),其中pi?pj(i?j)是素数.
推论1.4 设a与b是任意两个正整数，其标准分解式为
a?p1?1p2?2?ps?s,?i?0,(i?1,2,?,s), a?p1?1p2?2?ps?s,?i?0,(i?1,2,?,s),
则
(a,b)?p1?1p2?2?ps?s,，其中?i?min(?i,?i) (1.5.4) [a,b]?p1?1p2?2?ps?s,其中?i?max(?i,?i) (1.5.5)
及
(a,b)[a,b]?ab.
练习1. 5
1. 分别求2160及99?99的标准分解式. ?????12个2. 利用Maple或Mathematica函数求8203513468500的标准分解式. 3. 设a,b,c是任意整数，则有
1）max(min(a,b),min(a,c))?min(a,max(b,c))； 2)
[(a,b),(a,c)]?(a,[b,c]).
§1. 6 Euler函数
定义1. 7 对任意正整数n, 定义?(n)为不超过n且与n互质的正整数的个数. 则?为?的一个函数, 称为Euler(L.Euler,1707—1783)函数.
如?(1)?1, ?(2)?1, ?(4)?1, ?(10)?4. 易知Euler函数有如下性质：
9
?n?是定义域
Euler函数的基本性质定理1.5： i). 若
p是素数, 则?(p)?p?1; 反之亦成立. 即若p为合数, 则有?(p)?p?2；
ii) 不超过n且与n互质的所有自然数的和为1n?(n)；
2iii) 若
p是素数, 则?(pk)?pk?1(p?1)；
iv) 若m?m1m2, 且(m1,m2)?1, 则?(m)??(m1)?(m2)； v) 若n?p1?1p2?2?pt?t是n的质数分解, 则
?(n)?n(1?1)(1?1)?(1?1)
p1p2pt?n?(1?1)或n?(1?1)（p为素数）;
ppip|ni?1证 i) 显然.成立. ii) 若a1,a2,?,a?t?n?是不超过n且与n互质的所有自然数, 则
(n?a1),(n?a2),?,(n?a??n?)
亦是不超过n且与n互质的所有自然数, 因此必有
a1?a2???a??n??(n?a1)?(n?a2)???(n?a?(n)).
于是
2(a1?a2???a?(n))??(n)?n,
即ii) 成立.
iii) 因为不超过个整数, 故不超过
pk且与
pk不互素, 即与
p不互素的所有自然数为p,2p,?,pk?1p, 共为pk?1kk?1p?p, 即
pk且与
pk互素的所有正整数的个数为
?(pk)?pk?1(p?1).
iv) 我们运用概率知识来证明该条. 记???1,2,?,m?;E??x??|(x,m)?1?; Ei??x??|(x,mi)?1?,i?1,2. 则
??m,E??(m),E1?m2?(m1),E2?m1?(m2).
设事件
A指从?中随机取一数, 该数属于E；事件Ai指从?中随机取一数, 该数属于Ei(i?1,2).
A发生当且仅当事件A1因为任意的x??,有(x,m)?1当且仅当且(x,m1)?1,(x,m2)?1, 即事件
10