初等数论整数的可除性

1、第一章 整数的可除性§1 整 除整数集对于加、减、乘三种运算都是封闭的，但是对于除法运算不封闭。为此，我们引进整除的概念。定义1 设a,bZ，b0，如果存在qZ，使得等式a=bq成立，那么称b整除a或a被b整除，记作：b|a，此时称b为a的因数（约数），a为b的倍数。如果不存在满足等式a=bq的整数q，那么称b不能整除a或a不被b整除，记作ba。定理1 设a,b,cZ，b0，c0，则（1）如果c|b，b|a，那么c|a；（2）如果b|a，那么bc|ac；反之亦真；（3）如果c|a，c|b，那么，对于任意m,nZ，有c|(ma+nb)；（4）如果b|a，a0，那么|b|a|；（5）如果

2、b|a，a|b，那么|b|=|a|。证明 可选证。定理2（带余除法） 设a,bZ，b0，则存在q,rZ，使得a=bq+r，0r<|b|，并且q及r是唯一的。证明 当b|a时，取q=a/b，r=0即可。当b!|a时，考虑集合E=a-bk|kZ ，易知E中有正整数，因此E中有最小正整数，设为r=a-bk>0，下证：r<|b|。因为b!|a，所以r|b|，若r>|b|，则r=r-|b|>0，又rE，故与r的最小性矛盾，从而存在q,rZ，使得a=bq+r，0r<|b|。唯一性。设另有q,rZ，使得a=bq+r，0r<|b|，则b(q-q)=r-r，于是b|(r

3、-r)，但由于0|r-r|<|b|，故r-r=0，即r=r，从而q=q。定义2 等式a=bq+r，0r<|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，kZ。类似地，任一整数可表示为3k，3k+1，3k+2三种形式之一。例3 设a=2t-1

4、，若a|2n，则a|n。例4设a,bZ，a0，b0，有x,yZ，使ax+by=1，证明：若a|n，b|n，则ab|n。§2 最大公因数与最小公倍数定义1 设a1,a2,an是n (n2)个整数，若整数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，则它们的公因

5、数只有有限多个，从而它们的最大公因数必然存在而且唯一。（§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是任意三个不全为零

6、的整数，且a=bq+c，其中qZ，则a,b与(b,c)有相同的公因数，从而(a,b)= (b,c)。定理4 设a1,a2,an是不全为零的整数，则a1,a2,an的整线性组合的集合S=a1x1+a2x2+anxn| xiZ ，i=1,2,n恰由(a1,a2,an)的所有倍数组成。证明 因为S中有正整数，所以S中有最小正整数，设为D= a1x1+a2x2+anxn，则对于任意的a1x1+a2x2+anxnS，有a1x1+a2x2+anxn =( a1x1+a2x2+anxn)q+r，其中0r< a1x1+a2x2+anxn，于是r=a1(x1-x1q)+ a2(x2-x2q)+ an(xn-xnq)S，若r>0，则与D是最小正整数矛盾，故r=0，即S中任一整数都是D的倍数。反之，D的倍数也属于S，故S=DZ=Da|aZ。设d=(a1,a2,an)，下证：D=d。由于DS，又d|ai，i=1,2,n，故d|D，即dD；另一方面，因为a1,a2,anS，所以D|ai，i=1,2,n，从而Dd。因此，D=d。推论 设a1,a2,an是不全为零的整数，则存在整数x1,x2,xn，使得a1x1+a2x2+anxn=(a1,a2,an)，这一等式称为裴蜀（Bezout）等式。特别地，(a1,a2,an)=1的充分必要条件为存在整数x1,x2,xn，使得a1x1+a2