初等数论第一章整数的可除性.doc
初等数论 第一章 整数的可除性第一章 整数的可除性§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)如果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-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,若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,则它们的公因数只有有限多个,从而它们的最大公因数必然存在而且唯一。(§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,其中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+a2x2+anxn=1。§3 算术基本定理定义 一个大于1的整数,如果它的正因数只有1及它本身,那么称之为质数;否则称为合数。注 正整数分为三类:1,质数类,合数类。§4 函数x,x及其在数论中的一个应用13 / 13