初一寒假第1讲整除带余除法

1、第一讲整除带余除法板块1数论中的根本概念和常识质数 合数 整除 约数 倍数 互质 进位制定义略。质数是数论中第一重要的概念。算数根本定理：整数分解的唯一性。1不是质数，因为破坏了这个唯一性。定理表达如下:彳土可大于1的整数a能唯一地写成4 =pf.p：(1)的形式，其中pa p2 <pv都是质数,式1被称为a的标准分解式。【例】证明：假设 >。"产，那么珅.【例】1求2021的标准分解式2x5x3x67(2)求2021的标准分解式质数(3)求2021的标准分解式22x503【例】如果自然数使得2 + 1和3 + 1都恰好是平方数，试问5+ 3能否是一个素数.【解析】如果2

2、 + l = y , 3n + m2 ,那么5 + 3 = 4(2 + 1) (3 + 1) = 4公- nr = (2k +m)(2k ni).因为1 ,否那么，将有5 + 3 = 25+ 1 ,并且(?-炉=>-(痴+ 1) + 2 = (3 + 1)-(5 + 3) + 2 = -2/?<0 .而这是不可能的.故5 + 3不是素数. 判定质数很困难，判定合数的方法是分解。假设bc且cla ,那么ha (传递性)；假设ba且bc,那么3(。土。)。假设反复运用这一性质,易知对于任意的整数，口有 b(au+cv)。有时候要想知道ab是否成立,只需考察adb+ca是否成立。这里的c

3、.d是 适中选取的。(较高级技巧)【例】我们想知道一个数是不是7的倍数34675676，可以用34675截掉末三位减 去676末三位，看看差是不是7的倍数，这是为什么？更彻底的，我们想知道 5740376987465是不是7的倍数，可以去计算465-987+376-740+5是不是7的倍数。【例】一个七位自然数百历是99的倍数（其中八y是阿拉伯数字），试求95。-24），+ 1之 值，简写出求解过程.【解析】由99k2.9427知9k2小、427且11k2冲4279阿而7 ,所以6 + 2 + x + y + 4 + 2 + 7是9的倍数，所以x+y + 3 =是自然数）由0W9 , 0WyW

4、9 ,可得3Wx +，+ 3W21 ,从而x +y = 6或x+y = 15 ;1”62今427 ,所以ll|（6 + x + 4 + 7）-（2 + y + 2）,所以 13 + x-y = l M （A 是整数）又一9Wx-，W9 ,即4W13 + x-，W22 ,所以x-y = -2 或x-y =9 ,因为x+F与V同奇同偶性，所以二;二2或二;二即二或忆；1舍去），95O.v + 24y +1 = 1997（3）假设ba ,那么或者a=0 ,或者lalKhl ,因此假设ab且ba ,那么。=±匕；1整除任 何整数，任何非。整数整除0。这里相当于提供了证明两数相等的一个方法。b

5、 互质，假设 ac,bc ,那么 abc ；这个性质的意义是，满足整除条件的除数变大了，被除数不变，整除条件变得更强。【例】某公园门票价格对到达一定人数的团队按团队票优惠.现有人民C三个旅游团 共72人，如果各团单独购票，门票费依次为360元、384元、480元；如果三个团合起 来购票，总共可少花72元.这三个旅游团各有多少人？在下面填写一种票价方案，使其与上述购票情况相符.售 票 处普通票团体票（须满人）每人每人【解 析】360+384+480 - 72=1152（元），1152-72= 16（元/人）,即团体票是每人16元.因为16不能整除360 ,所以A团未到达优惠人数.假设三个团都未到

6、达优惠人数，那么三个团的人数比为360 : 384 : 480=15 ： 16 ： 20 , 即三个团的人数分别为*72, ? x 72榔X 72 ,这都不是整数（只要指出其中某一个不是 整数即可），不可能.所以C团本来就已到达优惠人数.这有两种可能：只有C团到达；尻C两团都到达.对于,可得c团人数为480-16=30，48两团共有42人，A团人数为15/31x42 , 不是整数，不可能.刘于，可得8团人数为384-16=24 , C团人数为480-16=30 4团18人售 票 处普通票团体票（须满20人）每人20元每人16元（或/或8折优惠）【例】是否存在3个大于1的自然数，使得其中每个自然

7、数的平方减1 ,能分别被其余的每个自然数 所整除？【解析】设a>b>c是满足题设条件的三个自然数.因为/ - 1被b整除，所以d 与互素.又H - 1能分别被a、b整除,因而被ab整除，于是c2 - >ab .另一 方面由值及b>c得ab>c2 ,矛盾.所以满足题设的数不存在.【例】八夕都是大于1的自然数，并且上和汩都是整数，问P +，/的值是多少？【解析】运用排序思想,不妨设，/大于等于,那么女二为大于。小于2的整数，为1 , q那么2p-l = q ,上I化为4-上，那么 =33=5，结果为8 . pPabc, a,b互质,那么ac这个性质的意义是：需要讨论的

8、被除数变小了，整除条件变得更强。【例】可将 3。这3。个整数写成一行，使得由第二个数开始的每个数都是它前面所排列 的所有数之和的约数,那么排在第3。个位置上的数最大应是 .【解析】130的和为s = gll = 3x5x31，设排在第30位的数为x ,由题意、被sr整除, 即x被，整除显然不能为31或31的倍数，因此工最大为3x5 = 15 ,而这也是可以到达的， 将1 30排列为16, 1, 17, 2, 18, 3, 19, 4, 20, 5, 21, 6,22,7,23,8,24,9,25,10,26, 11,27,12,28,13,29, 14,30, 15即可.【例】7ax yz6

9、= 41808 ,其中x , y , z代表非。数字.那么N + V+z' .【解析】根据个位数字分析可知工=3或8，代入表x章= 41808试验可得x = 8 , 止匕日寸有78x536 = 41808 ,即可彳导/ +、尸+z? =98 .是质数，假设2a3q-4，那么能整除中的某一个；特别地，假设是质数，那么1。互质数乘积是平方数，那么互质数都是平方数。【例】在正整数范围解方程=Kv+p）是奇质数【解析】假设），是的k倍，代入得到（攵+1*是平方数，无解。G，,p）= 1那么），,），+都是平方数,产9至4（6）pl，那么n在p进制之下尾数是0。正约数个数，正约数和公式。会用,会

10、证明常识：正整数中，平方数且只有平方数有奇数个正约数。【例】是满足以下条件的最小正整数:（1 是75的倍数；（2 恰为75个正整数因子包括1及本身.试求/75 .【解析】为保证是75的倍数而又尽可能地小，可设=2a.瞑5"其中定0,色1 ,之2, 并且«+!）夕+1尸 1二75由75二5二3 ,易知当a二小二4 ,尸2时，符合条件、 .此时 =2+3+52 , “75 = 432 .质数性质：”是合数，P是它的最小质因数,那么/不超过优所以判断的质合性的时候，只需检查123,4.,标+ 1中的质数质数有无限个。质数之间的缝隙可以超过任意正数。【例】2+3+4+5+.+几是质

11、数,求。【解析】原式二（、+ 2；（”1）。>3时,分子是两个大于2的数乘积一奇一偶，所以原 式是合数。只要计算=2,3的情形。【例】是否存在2021个连续正整数,其中恰有20个质数?【解析】我们知道存在2021个连续合数,不妨设他们是北+1,“+2. , +2021。我们还知道前2021个正整数中的质数多于20个。前2021个正整数都加1 ,算作一次操 作。一直进行这个操作，每次操作后得到的数列中的质数只能增加1 ,减小1或不变。h-1 次操作后，质数个数变成0。那么必有某次操作后质数个数等于20。构造任意长的连续合数列有多种方法，比方2000 ! +2,2000 ! +3,2000

12、! +4,2000 ! +2000是1999个连续的合数。后面学到剩余定理会给出其他构造方法。(10)整数的正约数可以凑对，一个整数的所有正约数的乘积的平方,是这个整数的嘉。如果一个正整数的所有正约数的乘积不是这个整数的幕，那么这个整数是平方数。逆命 题不真。板块2最小公倍数最大公约数两个整数除以他们的最大公约数，得到的商互质。两个整数分别除他们的最小公倍数, 得到的商互质。两个整数的乘积等于最小公倍数与最大公约数的乘积。这里又提供了一种处理两个数的方法：我们有时利用这个代换a=(a,b)x b=(a,b)y其中g，)=1(2)(a,b)=(a9a ± b)b) I (am+bn,

13、ap+bq)【例】正整数，和有大于1的最大公约数,且满足加+ = 371 ,那么HUI = 【解析】设攵是7、的最大公约数，那么也可表示为?=履，n = kb(k>l , a、b均 为正整数)故加 +n = (ka)x +kb = k(k2a3 +b) = 371 = 7x53 ,因为攵>1且7与53者B是质数，又公女，所以攵=7且公a，+/? = 53 , 即49xa'+ = 53 ,由“、方均为正整数，得 = 1 , = 4 ；所以/ = 7 , = 28 ,故而 = 196【例】50+ 2与50+12的最大公约数最大值.【解析】d=50+ *50+12=(50 + /

14、?2 , 50+ (it + 1) 2 - (50 + n2)二50 + 2,2+1=(2 (n2 + 50) , In + 1)因 2 + 1 是奇数=2 (n2 + 50) -n(2/7+1) , 2+ 1二(100-/7 f 2/7+1)=(100- f 2n +1+2 (100- fl)=100-，201) <201在二 100 时，d = 201 .故所求值为201 .(3)假设干个整数的最大公约数d ,最小公倍数ko那么对于任意质数，在"中的次数 是p在这些整数中的次数的最小值”在k中的次数是p在这些整数中的次数的最大值。【例】证明：对于自然数攵、?和.不等式k /

15、 m m , / 碓伙,m ,川2 成立.【解析】将攵、叭分解.设k = P，P,P；.p：'=以其中口i=l , 2 , D为不同的素数,即 瓜力为非负整数.对任一个素因数 pt ,不妨设0%呼曰一在所要证明的不等式左边, pi的指数为4fy-； 而右边，的指数为2讨.因而所要证明的不等式成立.要证明一个数大于另一个数，方法之一是只要证明任1可质数,在两个数中的质数都满足 同一方向的不等关系。【例】找到正整数a,b满足a , b + a , b+a + h = ab【解析】设"二心 b=ky (x,y)=l彳导至 lj k+xyk+kx+ky=kx x ky*1 +x+y+

16、xy=vyxl>'+1 jlx+1假设工二)1 ,那么x=y=l。a=b=4假设x>y ,那么x=y+1代入*得到州+2)= 1,2所以a-2,3 从而=6力=3,4所有的解是(。力)=(4,4)(6,3)(3,6)(6,4)(4,6)板块3带余除法一般地，如果a , b是正整数#)，那么一定有另外两个整数g和r , 0寸< % ,使得a=bxq+rQ当=。时，我们称d能被b整除。当;¥0时，我们称。不能被b整除，为a除以b的余数，g为除以的不完全商亦简称为商.用带余除式又可以表示为a-b=q.rf 0<r <bo这里q.r的选取是唯一 的。带余

17、除法提供了一种处理两个整数的方法，这种方法以后会经常用到。【例】在大于2005的自然数中，被56除后，商与余数相等的数共有多少个？这些数的 总和是多少？【解析】由于余数小于除数，商和余数相等，故商小于56。另一方面，由于被除数大于2005 ,故商数大于2005除以56带余除法中的商35 ,所以56>商数 >35。所以，在大于2005的自然数中，被56除后，商与余数相等的数有30个。由于被除数=56x商数十余数=57x商数,其中，商数等于36至55。所以，30 个整数的和二57x(36+37+55) = 57x15x91 = 77805。【例】最简分数；它能分解成不超过个正整数的倒数

18、和，这些整数互不等。 b解析：也就是写成单位分数的和。我们先看能写出的最大单位分数是多少。为此要利用一下带余除法。设/X明+厂，那么不超过/的最大单位分数是。 bq + 1:-白=户?所以我们还需要把 户一分解成单位分数的和。b q + 1 b(q + )b(q +1)通过观察，这个分数的分子严格减小了。这说明至多次这样的操作之后，我们的任务就完成了。显然这些单位分数的大小不同，个数不超过仇 课后练习1 .能将123,7,8,9填在3x3的方格表中，使横向和一竖向相邻两数之和都是质数吗?如果能，请给出一一一一种解法。如果不能，请说明理由。解析：横向和竖向相邻两教之和都是质数，那么奇偶相同的两数

19、不能相邻。所以正中间是奇数，它与2,4 , 6 , 8相邻。容易看出无论中间添的是几,+2簿+4,+6,+8中有合数。2 . 173%是一个四位数，数学老师说：“先后用三个数代替X , A 1所得到的3个四位数，依次可以被9、11、6整除。")问这3个数的和是多少？'/解析：911737 1111738611734三个数的和是19。.3 .两个圆只有一个公共点A ,大圆直径48厘米，小圆直径30厘米。两只甲虫同时从A 点出发，按所指的方向以相同的速度分别沿两个圆爬行。问：当小圆上的甲虫最少爬了 几圈时，两只甲虫相距最远？解析：小圆上的甲虫爬整数圈，大圆上的甲虫爬整数圈多半圈,距离最远。设小圆上的爬了。圈，大圆上的爬了 b圈。由于速度相同，30=48/2