第一讲整数的整除 第一拼 /编 日里BB 由整除的概念,你能否推出下列整除的基本性质? (1)若a|b,b|a,则a=b,或a=-b. (2)若a|b,bc,则alc. (3)若a|b,alc,则对任意整数x,y,恒有albx+cy. 如何判断一个非零整数整除给定的正整数?对某些特殊的非零整数,我们可以通过观 察发现一些简单的判别方法 给定两组正整数: 第一组6,18, 第二组5,17, 2 54,81,96,108,243 80,85, ,121,212 第一组数有什么规律?它们能被什么整数整除?第二组数呢?计算每组数的各位 数字之和,你能发现什么特征? 观察发现,第一组数能被3整除,并且其中每一个数的各位数字之和都能被3整除; 第二组数不能被3整除,并且其中每一个数的各位数字之和也不能被3整除 由此,我们猜想: (1)一个正整数的各位数字之和能被3整除,那么这个正整数能被3整除 这个命题是否正确?我们证明一下 下面仅对4位正整数情形给出证明,同学们可以类比证明一般的情形. 证明:设N为4位正整数,且它的个、十、百和千位数字依次为a,b,c,d,则 N=d×103+c×102+b×10+a =d×(999+1)+cX(99+1)+b×(9+1)+a =999d+99c+9b+d+c+b+a. 因为3|9994+99+9,所以,当3|d+c+b+a时,3|N 请用类似的方法证明能被9,11,7整除的正整数的下列特征; (2)一个正整数的各位数字之和能被9整除,那么这个正整数能被9整除; (3)一个正整数的奇数位数字之和与偶数位数字之和的差能被11整除,那么这 个正整数能被11整除; (4)一个正整数的末三位数字组成的数与末三位数字之前的数字组成的数之差能 被7(或11)整除,那么这个正整数能被7(或11)整除 aaenaneene.aaaa.a.a果多 ■■3
CHAPTER 逝高中课程标准实验教科书数学(选修46)初等数论沦初步 例1判断710316能否被9,11整除 解:因为7+1+0+3+1+6=18能被9整除,所以710316能被9整除 又因为710316的奇数位数字之和为6+3+1=10,偶数位数字之和为1+0+7=8,而 1ω一8=2不能被11整除,所以710316不能被11整除 2.带余除法 我们知道,14÷3的商为4,余数为2,即14= 3×↓+2,这种表示法在整数集中仍然成立,我们把 它叫做带余除法(或欧氏除法算式) 一般地,设a,b为整数,且b≠0,则存在惟 一的一对整数q和r,使得 a=+r,0≤r<|b|. 事实上,对任意整数a和非零整数b,如果a是b 欧几里得( Euclid,生卒 年不详,约活动于公无前300 的倍数,那么存在整数使得a=例,此时r=0.年前后),古希腊数学家 如果a不是b的倍数,如图1-1所示(b>0的情形), 古希腊的数论成就集中 由于b的倍数在数轴上是等距分布的,而且相邻两个 反映在欧几里得的几何《原 本》一书中,全书共13卷, 倍数之间的距离为b,而a是数轴上的一点,那 其中5卷讲数论,主要包括 么它一定落在b的两个相邻倍数之间.此时,将紧邻欧氏除法算式,算术基本定 a的左侧b的倍数记作加,选取r为a与的距离, 理、素数有无限多个等 此时a=例+r(从数轴上可以直观地看出).这就说 明了满足上述等式的整数q和r是存在的 gb a(g+IM 图1-1 下面说明q和r是惟一的,如果整数对q和r也满足 a=q+r,0≤r<|b|, 那么a=b+r=b(+r,即r-r=b(q- 于是b|(x-r),而一1b<r-r<1b 因此,r-P=0,即r=r,从而q=q 所以,q和r是惟一的 我们把带余除法中惟一的q和r分别叫做a除以b的商和余数.显然,a能被b整除当 且仅当余数r=0 例22004除以某个整数,其商为74,求除数和余数 解:设除数为b,余数为r,则 2004=74b+r,0≤r<b
第一讲整数的除 第一 由此可得 74≤2004<746+b=75b, 从而有 74≤2004 75 所以 2004 2004 75 74 即 2625<b≤27 因此,b=27,r=2004-27×74=6. 我们用符号[x0表示不超过实数x的最大整数,试用a,b表示a除以正整数b 的商q和余数r 的“,的日首日日量目日是 素数及其判别法 考察正整数的正因数,我们发现,有的正整数仅有一个正因数(如1),有的正整数仅 有两个正因数(如3,13,31),而有的正整数至少有三个正因数(如12,14,81) 我们把仅有两个正因数的正整数叫做素数,不是素数又不是1的正整数叫做合数 由定义知,3,13,31是素数,12,14,81是合数,1既不是素数,也不是合数 显然,2是惟一的偶素数,也是最小的素数,每个合数总可以表示成两个大于1的正 整数的乘积,而素数则不能 找出下列每个正整数的正因数: 6,7,9,21,65,77,121 观察每个正整数除1外的最小的一个正因数,从中你能发现什么规律? 我们发现,每个正整数n除1外的最小正因数p是一个素数,事实上,假设p不是素 数,因为p>1,所以p为合数,那么p必然有1,p以外的正因数q,使得q1p.因为 0[x]通常叫做取整函数(或高斯函数),它是数论中一个常见的函数,具有许多有趣的性质 5
CHAPTER 菩通高中课程标准实验教科书数学(选修46)初等数论初步 p|n,所以q|n,于是q是n的除1,p以外且小于p的正因数,这与已知矛盾,故最小 正因数p是一个素数.一般地,任何大于1的整数,总存在一个素数因数.通常,把一个 正整数的素数因数叫做它的素因数 是否总可将任何大于1的整数n分解为一些素数的乘积? 对大于1的整数n,如果n不是素数,我们可以将n分解为一个素数和某个大于1的整 数a的乘积,如果a是一个素数,则过程停止.否则,又可将a分解为一个素数和某个大于 1的整数b的乘积对b又分两种情形:若b为素数,则过程停止;若b不是素数,则将b继 续分解为一个素数和某个大于1的整数c的乘积如此进行下去,直到过程停止,最后总可 将n分解为一些素数的乘积.例如,12=2×2×3,78=2×3×13. 既然任何大于1的整数n总可分解为一些素数的乘积,那么素数有多少个?有限还是 无限?为什么? 我们不妨假设素数有有限个,即m,m2,m,…,m,记这 k个素数的乘积为N,即 欧几里得证 N=mm2m… 明素数有无穷多 个这个命题时使 由此可知,任意一个素数m(i=1,2,…k)都整除N,但不能整m了反证法,这 除N+1.又由于N+1为大于1的正整数,所以它一定能被某个素是数学上第一批 数整除,这就产生了矛盾.因此,假设素数有有限个是错误的,素 使用反证法的命 题 数有无穷多个 对给定的大于1的正整数,如何判断它是不是素数呢?例如,要判断61 是不是素数,是否需要用2~60之间的数一一试除61呢? s,.·.·,,,,,···,·····.········.···.,·······,,·,··· 没有必要.因为2不是61的因数,那么2的倍数也不是61的因数.同样地,若3不 是6的因数,那么3的倍数也不是6的因数.这就是说只需用2~60之间的素数试除61 即可 另一方面,如果61是合数,那么它一定可以表示成两个大于1的正因数的乘积,其 中较小的一个正因数一定不超过√61,并且它的素因数也是61的素因数.这就是说,如果 61是合数,那么它一定存在不超过√61的素因数 因此只需用2~60之间不超过√61的素数试除6即可 不超过√61的素数为2,3,5,7,由于它们都不整除61,所以6是素数
第一讲整数的整除 算一拼 般地,我们有下面的判别法: 如果大于1的整数a不能被所有不超过a的素数整除,那么a一定是素数 这个判别法实际上给出了一种寻找素数的有效方法 例3找出1-100中的全部素数 解:只需把1与1~100之间的合数去掉即可.而对于1~100之间的每个合数a,它 定能被某个不超过a的素数整除,从而能被不超过√100=10的素数整除。我们知道, 不超过10的素数为2,3,5,7.在1-100中首先去掉1,然后分别去掉2.3.5,7除自 身以外的倍数,最后剩下的数就是不超过100的全部素数.具体做法如下表: 2 9 T0 tR 19 点26 3132333437389 43本 4526 47 5525354555585960 61 46 676867Q 7177K7双787980 83 5868788900 9头 97 Q 因此不超过100的素数为2,3,5,7,11,13,17,19,23,29,31,37.41.43, 47,3,59,61,67,7,73,79,83,89.97,共25个.这种寻找素数的方法叫做埃 拉托斯特尼( Eratosthenes)筛法 1.判断下列整数中哪些能分别被3,7,9,11整除 45,98,120,189,1001,1331,56382. 2.探究并证明能被11整除的5住正整数的特征 3.已知1626除以某个整数,其商为81,求除数与余数 4.判断343,2027是素数还是合数