数论教案§1整数的整除 带余除法1 整数的整除设a,b 是整数,且b ≠0,如果有整数q,使得a=bq,则称b 整除a,记为b|a,也称b 是a 的因数,a 是b 的倍数. 如果没有整数q,使得a=bq,则称b 不能整除a,记为b?a.例如 2|4, 4|-12, -5|15; 2?3， -3?22. 在中小学数学里,整除概念中的整数是正整数,今天讲的整除中的整数可正可负. 判断是否b|a 当a,b 的数值较大时,可借助计算器判别.如果b 除a 的商数是整数,说明b|a;如果b 除a 的商不是整数,说明b?a. 例1判断下列各题是否b|a(1) 7|127 (2) 11|129 (3) 46|9529 (4) 29|5939 整除的简单性质(1)如果c|b,b|a,那么c|a;(2)如果d|a,d|b,那么对任意整数m,n,都有d|ma+nb.(3)如果12,,,n a a a L 都是m 的倍数,12,,,n q q q L 是任意整数,那么1122n n q a q a q a +++L 是m 的倍数.(4)如果c|a,d|b,那么cd|ab 。
例如： 2|4,2|(-6),那么2|4+(-6),2|4-(-6). 2|4,3|(-6),那么2×3|4×(-6). 例2证明任意2个连续整数的乘积,一定可被2整除. 练习 证明任意3个连续整数的乘积,一定可被3整除. 2.带余除法设a,b 是整数,且b>0,那么有唯一一对整数q,r 使得 a=bq+r,0≤r ＜ b . (1) 这里q 称为b 除a 的商,r 称为b 除a 的余数.例如-5=3×(-2)+1 5=3×1+2 -5=(-3)×2+1 5=(-3)×(-1)+2 15=(-5)×(-3), -24=(-2)×12. 事实上,以b 除a 的余数也可以是负的.例如 -5=3×(-1)-2=3×(-2)+1.求b 除a 的余数,也称为模运算(取余):mod.可用计算器进行.具体操作:输入a-按mod(取余)键-输入b-按=键得出余数.如果b 除a 的余数=0,则b|a;如果b 除a 的余数≠0,则b?a.例3 利用计算器求余数:(1) 7除127;(2)11除-129 ;(3)46除-9529;(4)-29除5939 奇数、偶数及性质能被2整除的整数称为偶数.如,0,4,10,-6,-8都是偶数. 不能被2整除的整数称为奇数.如,-5,-3,1,7,11都是奇数. 偶数的形式为2n(n 是整数);奇数的形式为2n-1(n 是整数).奇数、偶数的性质: 偶数±偶数=偶数,奇数±奇数=偶数,奇数±偶数=奇数,偶数×偶数=偶数,偶数×奇数=偶数,奇数×奇数=奇数.例如 2+4,2-4,3+1,3-1,3+4,6+5设a,b 是任意两个整数,则a+b 与a-b 同奇同偶. 例如3+5,3-5,6+3,6-3,例4设a,b,n 是任意3个整数,而且222a b n -=,证明n 是偶数.例5设a 是任一奇数,试证明8|21a -.例6设n 是正整数,证明形如3n-1整数不是完全平方数.证明 对任意整a,设a=3q 或a=3q ±1,于是2a =92q 或 2a =92q ±6q+1=3(32q ±2q)+1.即2a≠3n-1,故3n-1不是完全平方数.练习 设n 是正整数,证明形如4n-1、4n+2的整数都不是完全平方数. 习题:P3-4:1t,2t.§2公因数、最大公因数1.最大公因数、辗转相除法中小学里的公因数、最大公因数的概念：几个数的公有因数叫做这几个数的公因数.公因数中最大的整数称为这几个数的最大公因数. (1)几个数:不能确定;(2)因数、公因数:都是正整数; 最大公因数:没有专门的符号. 定义设12,,,n a a a L ,d 都是整数,d ≠0,如果i d a ,i=1,2,…,n,称d 是12,,,n a a a L 的公因数,12,,,n a a a L 的公因数中最大的整数称为最大公因数.记为12(,,,)n a a a L .如果12(,,,)n a a a L =1,则称12,,,n a a a L互质。
例1 (-6,8)=2,(-3,6,-9,15)=3,(1,2,3,-4)=1.在中小学数学里,求正整数a,b 的最大公因数主要有这个样几种方法：(1)观察法；(2)将a,b 的所有公因数都求出来,再从中挑最大的； (3)用短除法.辗转相除法:设a,b 是正整数,而且有111,0;a bq r r b =+<<12221,0;b rq r r r =+<< 123332,0;r r q r r r =+<<…………… （*）211,0;n n n n n n r r q r r r ---=+<<11.n n n r r q -+=(,)n a b r =。
例2用辗转相除法求(123,78),练习:用辗转相除法求(66,54).下面说明辗转相除法的正确性.先证明性质1设整数a,b,c 不全为0,而且有整数q 使得a=bq+c 则(a,b)=(b,c). 证明 由a,b,c 不全为0知,(a,b)、(b,c)都存在.因(a,b)|a,(a,b)|b,c=a-bq,得(a,b)|c,又得(a,b)≤(b,c); 反之,由(b,c)|b,(b,c)|c,a=bq+c,得(b,c)|a,(b,c)≤(a,b). 所以(a,b)=(b,c). 由(*)式知1210,n n b r r r r ->>>>>>L 而n 是有限正整数,再由性质1得112(,)(,)(,)a b b r r r ===…=211(,)(,)(,0)n n n n n n r r r r r r ---===.2.最大公因数的性质 最大公因数的几个性质：性质2 (am,bm)=(a,b)m,m>0.(短除法的根据) 例3求(84,90),(120,36).(84,90)=3(28,30)=6(14,15)=6.(120,36)=12(10,3)=12. 性质3 (a,b)=(|a|,|b|). 性质4 (a,b,c)=((a,b),c).例4求(-84,120),(-120,-72),(24,-60,-96).例5设n 是任意整数,证明3152n n ++是既约分数.证明 设d=(3n+1,5n+2),则d|3(5n+2)-5(3n+1),即d|1,d=1，所以3n+1与5n+2互质.作业 1.利用辗转相除法求(84,90). 2.求(120,36).3.设n 是整数，证明3172n n ++是既约分数。
§3整除的进一步性质及最小公倍数1.整除的进一步性质推论1设a,b 不全为零,那么有s,t ∈Z 使得as+bt=(a,b). 证明 将(*)中每式中的余数解出得21n n n nr r r q --=-,1321n n n n r r r q ----=-,…,212r b rq =-,11r a bq =-,再将1221,,,,n n r r r r --L 的表达式依次代入到21n n n n r r r q --=-中就得au+bv=n r =(a,b)=d,u,v ∈Z.例1用辗转相除法求(120,54),并求整数u,v 使得120u+54v=(120,54).解∵120=2×54+12,54=12×4+6,12=6×2,∴(120,54)=6. 12=120-2×54,6=54-12×4=54-(120-2×54)×4 =120×(-4)+54×9. ∴ u=-4,v=9.练习用辗转相除法求(84,45),并求整数u,v 使得84u+45v=(84,45).设a,b 都是正整数,问a,b 的公因数与最大公因数有什么关系 例2 ①求(12,18)及12与18的所有正的公因数；通过这个例子,请同学们观察最大公因数与公因数有何关系能否提出自己的猜想能否证明自己的猜想性质1 设d 是a,b 的最大公因数,那么,a,b 的任一公因数都是d 的因数.证明 如果d=(a,b),由性质2有u,v ∈Z 使得au+bv=d.设s 是a,b 的任一公因数,则s|au,s|bv,且s|au+bv,即s|d.性质2如果d=(a,b),则(,a b d d)=1.性质3如果(a,c)=1,且c|ab,则c|b. 性质4如果(a,c)=1,则(ab,c)=(b,c). 性质5如果(a,b)=1,且a|c,b|c,则ab|c. 例3证明 三个连续整数的积一定可被6整除. 2最小公倍数定义 如果m 是12,,,n a a a L 中每一个数的倍数,则称m 是整数12,,,na a a L 的一个公倍数.12,,,na a a L 的公倍中最小正整数称为12,,,na a a L 的最小公倍数.用[12,,,n a a a L ]来表示.例如 [2,4,-3]=12,[15,12,20]=60,[6,10,15]=30.定理3 [12,,,n a a a L ]=[|1a |,|2a |,…,|n a |].定理4 设a,b 是两个正整数,则 (i)a,b 的任一公倍数是[a,b]的倍数；(ii)[a,b]=(,)aba b .而且若(a,b)=1,则[a,b]=ab.证明(i)设m 是a,b 的任一公倍数,而且m=t[a,b]+r,0≤r<[a,b],因m,[a,b]都是a,b 的公倍数,由r=m-t[a,b]知r 也是a,b 的公倍数,若0<r<[a,b],则这与[a,b]的最小性矛盾.故r=0,m=t[a,b].(ii)记d=[,]aba b ,则d 是整数,由a|[a,b],a|[a,b]及[,]a a b d b =,[,]b a b d a =知d|a,d|b,即d 是a,b 的公因数.设h 是a,b 的任一公因数,由ab b aa b h h h ==是a,b 的公倍数及TH16知[a,b]|ab h ,即[,]ab d Z a b h h=∈,所以h|d,(a,b)=d,从而(a,b)=[,]aba b .定理5 设12,,,n a a a L 都是正整数,令122[,]a a m =,233[,]m a m =,…,1[,]n n n m a m -=,则12[,,,]n n a a a m =L .定理19设12,,,n a a a L 是n(≥2)个正整数,且两两互素,则12[,,,]n a a a =L 12n a a a L例2 求[123,456,-789]例3 求正整数a,b,满足:a+b=120,(a,b)=24,[a,b]=144.例14设a,b,c 是正整数,则[a,b,c]=(,,)abcab bc ca作业:P14:1.2.求(84,45),并求整数u,v 使得84u+45v=(84,45) .§4质数 算术基本定理1.质数定义设整数a>1,如果a 除了1和a 外再无其它正因数,则称a 为质数,也称为素数.否则,称a 为合数. 2,3,5,7,11都是质数，4,6,8,9,10都是合数.1-100内有素数25个,1-1000内有素数168个,1-10000内有素数1229,10万内有素数9592个,100万之内78498个.定理1设整数a>1,则a 除1外的最小正因数q 是素数,而且当a 是合数时,q ≤.证明 假定q 是合数,设q=bc,1<b,c<q.因b|q,q|a,得b|a,但1<b<q,这与q 是a 的最小正因数矛盾.故q 是素数.若a 是合数,设a=qm,由q 的最小性知a=qm ≥qq,即q ≤.素数判定定理 设整数a>1,不超过所有素数为12,,,k p p p L ,如果i p ?a,i=1,…,k,则a 为素数.例1 以下正整数哪个是素数哪个是合数 231,89,103,169.素数判别威尔逊定理:设整数p>1,那么p 是素数的充分必要条件是 p|(p-1)!+1. 例2 利用威尔逊定理判别3,5,7,11都是素数.当p 较大时,(p-1)!+1的数值非常大,在实际运用时不可行。