初等数论 整数的可除性.docx

第一章整数的可除性
§1整除
整数集对于加、减、乘三种运算都是封闭的，但是对于除法运算不封闭。为此，我们引进整除的概念。
定义1设a,b∈Z，b≠0，如果存在q∈Z，使得等式a=bq成立，那么称b整除a或a被b整除，记作：b|a，此时称b为a的因数（约数），a为b的倍数。
如果不存在满足等式a=bq的整数q，那么称b不能整除a或a不被b整除，记作ba。
定理1设a,b,c∈Z，b≠0，c≠0，则
（1）如果c|b，b|a，那么c|a；
（2）如果b|a，那么bc|ac；反之亦真；
（3）如果c|a，c|b，那么，对于任意m,n∈Z，有c|(ma+nb)；
（4）如果b|a，a≠0，那么|b|≤|a|；
（5）如果b|a，a|b，那么|b|=|a|。
证明可选证。
定理2（带余除法）设a,b∈Z，b≠0，则存在q,r∈Z，使得a=bq+r，0≤r<|b|，并且q及r是唯一的。
证明当b|a时，取q=a/b，r=0即可。
当b!|a时，考虑集合E={a-bk|k∈Z}，易知E中有正整数，因此E中有最小正整数，设为r=a-bk>0，下证：r<|b|。因为b!|a，所以r≠|b|，若r>|b|，则r’=r-|b|>0，又r’∈E，故与r的最小性矛盾，从而存在q,r∈Z，使得a=bq+r，0≤r<|b|。
唯一性。设另有q’,r’∈Z，使得a=bq’+r’，0≤r’<|b|，则b(q-q’)=r’-r，于是b|(r’-r)，但由于0≤|r’-r|<|b|，故r’-r=0，即r=r’，从而q=q’。
定义2等式a=bq+r，0≤r<|b|中的整数q称为a被b除所得的（不完全）商，整数r称为a被b除所得的余数。
注r=0的情形即为a被b整除。
例1设b=15，则
当a=255时，a=17b+0，故q=17，r=0；
当a=417时，a=27b+12，故q=27，r=12；
当a=-81时，a=-6b+9，故q=-6，r=9。
例2整数被2除的余数有两种可能：0和1，一个整数被2整除称为偶数，否则称为奇数，分别记作2k和2k+1，k∈Z。
类似地，任一整数可表示为3k，3k+1，3k+2三种形式之一。
例3设a=2t-1，若a|2n，则a|n。
例4设a,b∈Z，a≠0，b≠0，有x,y∈Z，使ax+by=1，证明：若a|n，b|n，则ab|n。

§2最大公因数与最小公倍数
定义1设a1,a2,…,an是n(n≥2)个整数，若整数d满足d|ai，i=1,2,…,n，则称d为a1,a2,…,an的一个公因数；
整数a1,a2,…,an的公因数中最大的一个称为最大公因数，记作：(a1,a2,…,an)；
若(a1,a2,…,an)=1，则称a1,a2,…,an互质（互素）；
若a1,a2,…,an中每两个整数互质，则称a1,a2,…,an两两互质。
注1任意整数a1,a2,…,an必有公因数（如±1）。
注2若a1,a2,…,an不全为0，则它们的公因数只有有限多个，从而它们的最大公因数必然存在而且唯一。（§1定理1之(4)）
注3最大公因数一定是正整数。
注4(a1,a2,…,an)=1相当于a1,a2,…,an的公因数只有±1。
注5两两互质必互质，反之未然。
定理1若a1,a2,…,an是任意n个不全为零的整数，则
(1)a1,a2,…,an与|a1|,|a2|,…,|an|的公因数相同；
(2)(a1,a2,…,an)=(|a1|,|a2|,…,|an|)。
定理2若b是任一正整数，则
(1)0与b的公因数就是b的因数，反之亦然；
(2)(0,b)=b。
推论若b是任一非零整数，则(0,b)=|b|。
定理3设a,b,c是任意三个不全为零的整数，且a=bq+c，其中q∈Z，则a,b与(b,c)有相同的公因数，从而(a,b)=(b,c)。
定理4设a1,a2,…,an是不全为零的整数，则a1,a2,…,an的整线性组合的集合S={a1x1+a2x2+…+anxn|xi∈Z，i=1,2,…,n}恰由(a1,a2,…,an)的所有倍数组成。
证明因为S中有正整数，所以S中有最小正整数，设为D=a1x1’+a2x2’+…+anxn’，则对于任意的a1x1+a2x2+…+anxn∈S，有a1x1+a2x2+…+anxn=(a1x1’+a2x2’+…+anxn’)q+r，其中0≤r<a1x1’+a2x2’+…+anxn’，于是r=a1(x1-x1’q)+a2(x2-x2’q)+…+an(xn-xn’q)∈S，若r>0，则与D是最小正整数矛盾，故r=0，即S中任一整数都是D的倍数。反之，D的倍数也属于S，故S=DZ={Da|a∈Z}。
设d=(a1,a2,…,an)，下证：D=d。
由于D∈S，又d|ai，i=1,2,…,n，故d|D，即d≤D；另一