2、,c,^Oo记作：〃=（55-…qc。）,”。3•加进制表示的具体做法将一个正整数兀表示成加进制时，主要是要确定Co，C],•…，ck_vckoYl.11若用一表示〃除*以加后，取其整数部分（也就是比一小的最大整数丿，加」m确走Co，C],…，ck_vCr的方法如下：!•冷7）=，"o=兀，刚有n=“2=2.令厂2k~]+ck_}mk~2Hc2m+Cj*_+C^,_
3、YYl^3+■••+C3A27+C?4.若坷〉血，令％]=q,i=0,l,2,・・・k—i—1k—i—2C"+Ck_}m_+・・・+ci+2m+c/+1=0，Ck~rk+4.举例借I]n=389,m=5解令n(
4、}=n=389则有389_5__5.n==77,%77_5__5.n21555=15,=3,“3fh3_5__5_n4==0,斤=4=c°5=0=C24=3=5故389=3>53+0>52+2<5,+4=(3024)5例n=389,m=2解令n{)=n=389则有®=血/2」=
5、_389/2」=194,c0=1n2=[n{/2j=[194/2」=97,c严0“3=况/2」=L97/2J=4&c2=1n4=L®/2」=L48/2J=24,C3=0n5=L®/2」=
6、_24/2_
7、=12,c4=0“6=L®/2」=L12/2」=6,C5=0ni=L«/2」=⑹2」=3,c6=0心
8、=E/2」=L3/2」=1,c?=1®=L心/2」=
9、_i/2」=i,q=1389=28+27+22+1=(110000101)2第六次课截止于此3.1.2数的因数分解素数只能菠1和其自身除尽的正整数称为素数(1，2,3,5异，11，13，17，・・・丿。合数不是1且非素数的正蔓数称为合数(2,4血8,9，10，12，14，15，16,…人a除尽方表示yfjabo以后不特别说明英丈学母a,b、c…等都裹示正整数。公因子若«b,且aIc,则称a是方和c的衣因子。最大公因子若a昊ib和c的公因子*且方和c的每•一个公因子都能除尽则称4处方和C的最夬公因子,表示为：a=gcd{Z
10、?,c}或a=(Z?,c)o僖数若ale则称c是a的儈数，若ale且方lc则称c長a知b的公信数。最小公俵数若a和方的公信数c能除尽a和方的任一公信教，则称c是a和“的最小公得数，表示为：c=lcm{a,Z?}或c=[a,b]o例12=gcd{12,60}=(12,60)60=lcm{15,20,30}=[15,20,30]定理*若d=/?q+厂，则gcd{a,Z?}=±gcd{/?,r}o定理每一对不全为零的整数，必有一个正的最大公因数。证明不失一般性地，设。和b是正整教'且a>b。令a=bq+r,011、,那么(a,b)=(b,r)=(r,rl)依此类推直到出现余数为零对终止。这样，存在荼一整数4使得J二m,rkH°Z；-1=/7^+1故该序列为f]>r2>.…〉q>0且(tz,/?)=(/?,r)=(r,r,)==z;.所以rk是gcd{%}o上述证明过程提供求gcd{a,b}的具体步骤。求gcd{a,b}的过程可用柢转相除的形天直观的表示如下：aa=qb+r（ci,b）=（b,0b=r、厂=/斤+石（r,斤）=（斤，石）■■■（4一2'rk-）=（4一1，rk）'h严办+4（几工°所以（d,Z?）=（b,厂）=（厂,斤）=（斤，q）=…=（q‘_],*）=«r>r}>r2
12、>•…>几一>hrk=gcd{^,/?}o例求gcd{726,393}o解辗转相除726393133339333356033330013360331393273327462724236610726=1x393+333333=726-393393=1x333+6060二393-333333=5x60+3333=333-5x6060=1x33+2727=60—1x3333=1x27+66=33-1x2727=4x6+33=27—4x66=2x3+0所以gcd{726,393}=gcd{393,
