第1页共6页二、辗转相除法与裴蜀定理4、辗转相除法与裴蜀定理定义对于整数a，b，若ab,则称a是b的约数;而b是a的倍数.定义对于不全为零的整数(1,2,,)iainL，若aia对1,2,,inL都成立,则称a是12,,naaaL的公约数.定义对于非零整数(1,2,,)iainL，若iaa对1,2,,inL都成立,则称a是12,,naaaL的公倍数.定义整数(1,2,,)iainL的公约数中，最大的一个，称为整数(1,2,,)iainL的最大公约数，记作12(,,)naaaL.整数(1,2,,)iainL的公倍数中，最小的一个，称为整数(1,2,,)iainL的最小公倍数，记作[12,,naaaL].定义若(a,b)=1,则称a,b互质或互素.显然有下列性质：性质1(a,b)=(b,a)=(a,-b)=(-a,-b)；性质2ab=(a,b)[a,b],特别地当a>0,b>0时，ab=(a,b)[a,b].下面我们介绍辗转相除法与裴蜀定理定理若a=qb+r，则(a,b)=(b,r).注：本定理也可写成：(a,b)=(abq,b),就是说，在计算(a,b)时，可用b的任意整数倍数bq去减a.下面我们介绍辗转相除法，对于给定的整数a,b(b>0)，我们反复运用带余除法就有：a=q1b+b1,0b10，则可以选择u>0，v<0或u<0，而v>0.证明：必要性显然，下面证明充分性.对于整数a,b，存在整数u,v使得ua+vb=1，我们设(a,b)=d，则da,db，于是d1，又d1，所以d=1，即(a,b)=1.若ab>0，则a,b同号，所以要使ua+vb=1成立，u,v必须异号，所以u>0，v<0或u<0，而v>0.综上所述，裴蜀定理成立.5．最大公约数与最小公倍数的性质性质1若(a,b)=1,且abc，则ac；性质2若(a,b)=1,则(a,bc)=(a,c)；性质3若(ai,bj)=1,1,2,,1,2,imjnLL,则1212(,)1mnaaabbbLL性质4若(a,b)=1,且n,m是非负整数，则(an,bm)=1；性质5若ma,mb，则m(a,b)；性质6设正整数a,b的质因数分解式如下a=kkppp2121，b=kkppp2121,其中第2页共6页i、i(i=1,2,⋯,k)都是非负整数，记ti=min(i,i),si=max(i,i),i=1,2,⋯,k,则有(a,b)=ktkttppp2121；[a,b]=kskssppp2121性质7(ma,mb)=|m|(a,b)；[ma,mb]=|m|[a,b]。性质8(,)1(,)(,)ababab性质9若p为素数，则,|(,)1,ppapapa.6、最小非负余数性质1两个4k+3形式的数的乘积一定是4k+1形式的数；性质2一个平方数被4除，所得的最小非负余数只可能是0，1；性质3一个平方数被8除，所得的最小非负余数只可能是0，4；性质4一个平方数被3除，所得的最小非负余数只可能是0，1；性质5一个平方数被9除，所得的最小非负余数只可能是0，1，8；从上述性质我们容易知道：对任意整数x,y，有2243xyk;2283,86,87xykkk;3393,94,95,96xykkkk.例1对任意整数x,y,证明：(1)8222xy;(2)若2xy，则222xyn；(3)若3xy，则222xyn;(4)若222xyn,则6|xy.例2设a2是给定的正整数，那么任一正整数n必可唯一表示为1110kkkknrarararL其中整数k0,01,0,1,2,,,0ikraikrL*我们称1110kkkknrarararL为n的a进制表示.例3设p是素数，证明：(1)|,1,2,,1ippipCL。(2)对任意正整数a,|ppaa(3)若(a,p)=1，则1|1ppa。例4设k是正整数，证明：(1)(,)(,)kkkabab;(2)设a,b是正整数，(a,b)=1，ab=ck,则a=(a,c)k,b=(b,k)k.例5设p是素数，(a,b)=p，求(a2,b),(a3,b)，(a2,b3)所可能取的值.例6设正整数n的质因数分解式为n=kkppp2121，其中i(i=1,2,⋯,k)都是非负整数,求n的正约数个数(n)。例7设正整数n的正约数个数为(n)，所有这样的约数的和为(n),所有这样的约数的积为(n),求证：(1)(n)=2)(nn；(2)(n)n2；(3)nnn)()(.[想一想]设正整数n的质因数...
