电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

辗转相除法与裴蜀定理VIP免费

辗转相除法与裴蜀定理_第1页
1/6
辗转相除法与裴蜀定理_第2页
2/6
辗转相除法与裴蜀定理_第3页
3/6
第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的质因数...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

辗转相除法与裴蜀定理

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部