第一讲 整数与同余理论
本讲介绍有关整数的一些基本概念、性质与定理.主要包括整数的整除性、奇偶性，以及依据整除性而产生的质数与合数、带余除法、最大公约数与最小公倍数. 同时简单介绍同余式的一些最基本的知识及有关重要定理，如欧拉定理、中国剩余定理(CTR).
______________________________________________________________________________
§1. 1 整数的基本概念、性质与定理
自然数和它的相反数，以及零均称为整数. 定义1. 1 设a与b是任意两整数且b?0，若存在整数q使得a?bq，则称b整除a或a能被b整除.记作b|a；否则，称b不能整除a或a不能被b整除，此时记作b?a.
?1,?a，则称b是a如果b|a，则称b是a的约数或因数，a是b的倍数；若b是a的约数但b?的真约数或真因数.
定理1. 1 设a,b,c,m,n是整数, 则有 i)
a|a；
??b；
ii) 如果a|b且b|a，则aiii) 如果a|b且b|c，则a|c； iv) 如果a|b且a|c，则a|(mb?nc).
定理1. 2（带余除法定理） 对任意两整数a与b且b?0，则存在唯一的一对整数q与r，使得
a?qb?r，其中0?r?|b|.
q称为a被b除得到的商，r称为a被b除得到的余数.
我们借助自然数集的最小数原理来证明该定理:
自然数集的最小数原理 若S是广义的自然数集的任一非空子集，则存在a?S使得?x?S，有
a?x成立，此a称为S的最小数.
定理1.2的证明 设S=?a?kb|k??, a?kb?0?，则S是广义自然数集的非空子集，于是存
?a?qb，亦即a?qb?r.下面证明0?r?|b|且q与r是
在S的最小数r，即存在q??，使r 1
唯一的.（注：广义自然数集可包含零及正无穷大这两个元素.）
若r?|b|，则0?r?|b|?a?(q?1)b?S且r?r?|b|，这与r是S的最小数矛盾.
若存在两整数q1与r1，使得
a?q1b?r1，0?r1?|b|,
则
q1b?r1?qb?r,
即
(q1?q)b?r?r1.
若q1?q，则r?r1?|b|，这与0?r,r1?|b|?1矛盾，故q1?q，于是r?r1. ▋
显然，a被b整除的充分且必要条件是其余数为0. 例1. 1 设a??89,b?13, 则q??7, r?2.
练习1. 1
1. 证明对任意整数n有6n(n?1)(2n?1).
2. 如果2a?3b与9a?5b中有一能被17整除，那末另一数一定也能被17整除. 3. 证明：7a00a，其中a00a表示一个四位数a?{1,2,?,9}.
§1. 2 整数的奇偶性
奇偶数的定义：能被2整除的整数称为偶数；不能被2整除的整数称为奇数. 基本性质：
1）两个整数的和与差具有相同的奇偶性.
2）奇数的平方被4除余1，被8除也余1，而偶数的平方能被4整除.
3）如果若干个整数的乘积是奇数，则每个因数都是奇数；如果若干个整数之积是 偶数，则至少有一个因数是偶数.
例1. 2 在广场上有m（奇数）个学生面向南方排成一行，命令其中n（偶数）个学生向后转，称作一次“反向运动”，证明：无论作多少次“反向运动”（转向后的学生允许再转动），都不可能使所有的学生全部面向北方.
证 假设做k次“反向运动”后，可使全体学生面向北方，又设各学生“向后转”的次数分别为x1,?,xm,
2
而对每个学生来说，从面向南方变为面向北方，必须经过奇数次“向后转”，即x1,?,xm均为奇数，又m为奇数，所以x1???xm是奇数.另一方面，每次“反向运动”均是n个学生的“向后转”，所以k次“反向运动”所作的“向后转”总次数应为kn，故有x1?x2边是偶数，矛盾. ▋
???xm?kn，但该等式左边是奇数，而右
练习1. 2
1.
4?4的方格纸上填着1,9,9,8这四个数字，如图所示，问是否可能在余下的方格
内各填入一整数，使得方格纸上的每一行和每一列都构成等差数列
9 1 9 8 表1. 1
2. 已知多项式x3?bx2?cx?d的系数均为整数，且bd?cd是奇数，证明：此多项
式不可能分解成两个整系数多项式之积.
3. 将下图表1.2中任何一行或一列作全部变号操作，问可否经过若干次这样的操作使表1.2变为表1.3？
?
???????????
??? ???表1.2 表1.3
a,求证：24|(a4. 若a是奇数，且3?2?1).
§1. 3 最大公约数与最小公倍数
本节利用带余除法，引入辗转相除法，并由此介绍最大公约数与最小公倍数.
定义1. 2 设a1,a2,?,an是n(n?2)个整数.若整数d是每个ai的因数，则称d是
a1,a2,...,an的一个公因数.
定义1.3 整数a1,a2,?,an的公因数中的最大者称为它们的最大公因数，记作(a1,a2,?,an)或
3
gcd(a1,a2,?,an).
显然，若a1,a2,?,an中至少有一个非零.比如说ai??0，则(a1,a2,?,an)?ai，因而此时
a1,a2,?,an的最大公因数存在.
定义1. 4 如果
；如果i?(a1,a2,?,an)?1，则称a1,a2,?,an互素（或互质）?j时有
(ai,aj)?1，则称a1,a2,?,an两两互素（或互质）.显然，若后者成立，则前者也成立，反之则不然.
如(3,5,10)?1，但(5,10)??1.
性质定理1.1 设a1,a2,?,an是n个不全为零的整数，则有 i) ii)
(a1,a2,?,an)?(ai1,ai2,ai2,?,ain)，其中i1,i2,?,in是1,2,3,?,n的一个排列； (a1,a2,?,an)?(|a1|,|a2|,?,|an|)；
iii) 若a1,a2,?,an中有一个为1, 则它们互素； iv) 若aj1,aj2,?,ajs是a1,a2,?,an中全不为零的整数，则
(a1,a2,?,an)?(|aj1|,|aj2|,?,|ajs|).
以上性质的证明均显而易见. 定理1. 3 如果a证 设(a,b)从而
另一方面，d1从而
综合(1.3.1)与(1.3.2)即得
?bq?r,则有(a,b)?(b,r).
及(b,r)?d?d1，则一方面，da且db，于是由a?bq?r得d|r，
d?d1. (1.3.1)
|b且d1|r，以及a?bq?r得d1|a.
d1|d. (1.3.2)
d?d1. ▋
辗转相除法 设a,b是任意两个正整数，多次利用带余除法，可得下列诸等式：
4
a?bq1?r1 0?r1?b,?b?r1q2?r2 0?r2?r1,??? ? ? ?? (*) rk?2?rk?1qk?rk 0?rk?rk?1,??rk?1?rkqk?1?rk?1 rk?1?0.??由于b是有限正整数，且b?r1?r2???rk?rk?1?0，所以(*)中的正整数k是存在的.
辗转相除法(*)是我国古代筹算家的一大成就，西方Euclid(欧几里德)也推得该法则，所以又称为Euclid算法.
定理1. 4 设a,b是任意给定的两整数，则由(*)式可得，(a,b)证明 反复利用定理1. 3有
例1. 3 设a解
?rk.
(a,b)?(b,r1)?(r1,r2)???(rk?1,rk)?(rk,0)?rk. ▋
??1895, b?1573, 求(a,b)??
(a,b)??(1895,15?73)(185. 9,反复利用定理1.3，如下面的辗转相除计算图. 再由定理1. 4即得
(a,b)?(1859,1573)?143. ▋
1859 1573 1573 1430 143=r2 2=q3 1=q1
q2=5
286=r1 286 0=r3 图1.4
定理1. 5
a与b的任一公约数是(a,b)的约数.
证 设d是a与b的任一公约数，则由(*)知d是b与r1的公约数，进而知d是r1与r2的公约数，如此继续，可得d是rk的约数. ▋
定理1. 6 （扩展Euclidean等式）若(a1,?,an)?d，则必存在整数ki(i?1,?,n)使
k1a1?k2a2???knan?d.
推论1.1
(a1,a2,?,an)?1的充要条件是存在t1,t2,?,tn??使
5