《初一寒假第1讲整除带余除法》由会员分享，可在线阅读，更多相关《初一寒假第1讲整除带余除法（8页珍藏版）》请在金锄头文库上搜索。
1、 第一讲 整除 带余除法板块1 数论中的基本概念和常识质数 合数 整除 约数 倍数 互质 进位制定义略。质数是数论中第一重要的概念。算数基本定理：整数分解的唯一性。1不是质数，因为破坏了这个唯一性。定理叙述如下：任何大于1的整数a能唯一地写成（1）的形式，其中都是质数.式（1）被称为a的标准分解式。【例】证明：若，则【例】（1）求2010的标准分解式 25367 （2）求2011的标准分解式 质数 （3）求2012的标准分解式 22503【例】如果自然数使得和都恰好是平方数，试问能否是一个素数【解析】如果，则因为，否则，将有，并且而这是不可能的故不是素数判定质数很困难，判定合数的方法是分解。(
2、1)若b|c且c|a，则b|a (传递性)；(2)若b|a且b|c，则。若反复运用这一性质，易知对于任意的整数u,v有。有时候要想知道a|b是否成立，只需考察a|db+ca是否成立。这里的c,d是适当选取的。(较高级技巧)【例】我们想知道一个数是不是7的倍数（34675676），可以用34675（截掉末三位）减去676（末三位），看看差是不是7的倍数，这是为什么？更彻底的，我们想知道5740376987465是不是7的倍数，可以去计算465-987+376-740+5是不是7的倍数。【例】已知一个七位自然数是的倍数(其中、是阿拉伯数字)，试求之值，简写出求解过程【解析】由知且，所以是的倍数，所
3、以(是自然数)由，可得，从而或；，所以，所以(是整数) 又，即，所以或，因为与同奇同偶性，所以或，即或(舍去)， (3)若b|a，则或者a=0，或者，因此若a|b且b|a，则；1整除任何整数，任何非0整数整除0。这里相当于提供了证明两数相等的一个方法。(4)a,b互质，若a|c,b|c，则ab|c；这个性质的意义是，满足整除条件的除数变大了，被除数不变，整除条件变得更强。【例】某公园门票价格对达到一定人数的团队按团队票优惠现有A、B、C三个旅游团共72人，如果各团单独购票，门票费依次为360元、384元、480元；如果三个团合起来购票，总共可少花72元(1)这三个旅游团各有多少人? (2)在下
4、面填写一种票价方案，使其与上述购票情况相符售 票 处 普通票 团体票(须满 人) 每人 每人 【解析】360+384+48072=1152(元)， 115272=16(元人)，即团体票是每人16元 因为16不能整除360，所以A团未达到优惠人数 若三个团都未达到优惠人数，则三个团的人数比为360：384：480=15：16：20，即三个团的人数分别为，这都不是整数(只要指出其中某一个不是整数即可)，不可能所以C团本来就已达到优惠人数 这有两种可能：只有C团达到；B、C两团都达到 对于，可得C团人数为48016=30，A、B两团共有42人，A团人数为15/3142，不是整数，不可能 刘于，可得B
5、团人数为38416=24， C团人数为48016=30 A团18人售 票 处 普通票 团体票(须满20人) 每人20元 每人16元(或或8折优惠)【例】是否存在3个大于1的自然数，使得其中每个自然数的平方减1，能分别被其余的每个自然数所整除？【解析】设abc是满足题设条件的三个自然数因为a21被b整除，所以a与b互素又c21能分别被a、b整除，因而被ab整除，于是c21ab另一方面由ac及bc得abc2，矛盾所以满足题设的数不存在【例】已知、都是大于的自然数，并且和都是整数，问的值是多少？【解析】运用排序思想，不妨设大于等于，则为大于小于的整数，为，则，化为，则，结果为a|bc, a,b互质，
6、则a|c这个性质的意义是：需要讨论的被除数变小了，整除条件变得更强。【例】可将这个整数写成一行，使得由第二个数开始的每个数都是它前面所排列的所有数之和的约数则排在第个位置上的数最大应是 【解析】的和为，设排在第30位的数为，由题意被整除，即被整除.显然不能为或的倍数，因此最大为，而这也是可以达到的，将排列为即可【例】已知，其中，代表非数字那么 【解析】根据个位数字分析可知或，代入试验可得，此时有，即可得(5) p 是质数，若，则p能整除中的某一个；特别地，若p是质数，则。互质数乘积是平方数，则互质数都是平方数。【例】在正整数范围解方程 x2=y(y+p) p是奇质数【解析】若y是p的k倍，代入
7、得到(k+1)k是平方数，无解。(y,p)=1 则y,y+p都是平方数，y= (6)p|n, 那么n在p进制之下尾数是0。(7)正约数个数，正约数和公式。（会用，会证明）常识：正整数中，平方数且只有平方数有奇数个正约数。【例】n是满足下列条件的最小正整数：（1）n是75的倍数；（2）n恰为 75个正整数因子（包括1及本身）试求n/75【解析】 为保证 n是75的倍数而又尽可能地小，可设n235，其中0，1，2，并且（1）（1）（1）75由75523，易知当4，2时，符合条件（1）、（2）此时n243452，n/75432(8)质数性质：a是合数，p是它的最小质因数，则p2不超过a。所以判断n的
8、质合性的时候，只需检查1,2,3,4,中的质数(9)质数有无限个。质数之间的缝隙可以超过任意正数。【例】2+3+4+5+n是质数，求n。【解析】原式=。n3时，分子是两个大于2的数乘积（一奇一偶），所以原式是合数。只要计算n=2,3的情形。【例】是否存在2011个连续正整数，其中恰有20个质数？【解析】我们知道存在2011个连续合数，不妨设他们是n,n+1,n+2，n+2010。我们还知道前2011个正整数中的质数多于20个。前2011个正整数都加1，算作一次操作。一直进行这个操作，每次操作后得到的数列中的质数只能增加1，减小1或不变。n-1次操作后，质数个数变成0。那么必有某次操作后质数个数
9、等于20。构造任意长的连续合数列有多种方法，比如2000！+2,2000！+3,2000！+4,2000！+2000是1999个连续的合数。后面学到剩余定理会给出其他构造方法。(10)整数的正约数可以凑对，一个整数的所有正约数的乘积的平方，是这个整数的幂。如果一个正整数的所有正约数的乘积不是这个整数的幂，那么这个整数是平方数。逆命题不真。板块2 最小公倍数 最大公约数(1)两个整数除以他们的最大公约数，得到的商互质。两个整数分别除他们的最小公倍数，得到的商互质。两个整数的乘积等于最小公倍数与最大公约数的乘积。这里又提供了一种处理两个数的方法：我们有时利用这个代换 a=(a,b)x b=(a,b
10、)y 其中(x,y)=1(2) (a,b)=(a,ab) (a,b)|(am+bn,ap+bq)【例】正整数m和n有大于1的最大公约数，且满足，则 【解析】设是m、n的最大公约数，则m、n可表示为，(，、均为正整数)故，因为且7与53都是质数，又，所以且，即，由、均为正整数，得，；所以，故【例】50n2与50+（n+1）2的最大公约数最大值【解析】d=（50n2,50+（n+1）2）（50n2，50（n1）2（50n2）（50n2，2n1）（2（n250），2n1）（因 2n1是奇数）（2（n250）n（2n1），2n1）（100n，2n1）（100 n，2n12（100 n）（100n，20
11、1）201在n100时，d201故所求值为201(3)若干个整数的最大公约数d，最小公倍数k。那么对于任意质数p，p在d中的次数是p在这些整数中的次数的最小值；p在k中的次数是p在这些整数中的次数的最大值。【例】证明：对于自然数k、m和n不等式k，mm，nn，kk，m，n2成立【解析】将k、m、n分解设 其中pi（i=1，2，l）为不同的素数，i、i、i为非负整数对任一个素因数pi，不妨设0iii在所要证明的不等式左边，pi的指数为iii=i2i；而右边pi的指数为2i因而所要证明的不等式成立要证明一个数大于另一个数，方法之一是只要证明任何质数，在两个数中的质数都满足同一方向的不等关系。【例】
12、找到正整数a,b满足（a，b）a，babab【解析】设a=kx b=ky (x,y)=1得到k+xyk+kx+ky=kxky *1+x+y+xy=kxy x|y+1,y|x+1若x=y，则x=y=1。a=b=4若xy，则x=y+1 代入*得到y|y+2 y=1,2所以x=2,3 从而a=6,b=3,4所有的解是(a,b)=(4,4) (6,3) (3,6) (6,4) (4,6)板块3 带余除法一般地，如果a，b是正整数（b0），那么一定有另外两个整数q和r，0rb，使得a=bq+r。当r=0时，我们称a能被b整除。当r0时，我们称a不能被b整除，r为a除以b的余数，q为a除以b的不完全商（亦
13、简称为商）.用带余除式又可以表示为ab=qr，0rb。 这里q,r的选取是唯一的。 带余除法提供了一种处理两个整数的方法，这种方法以后会经常用到。【例】在大于2005的自然数中，被56除后，商与余数相等的数共有多少个？这些数的总和是多少？【解析】由于余数小于除数，商和余数相等，故商小于56。另一方面，由于被除数大于2005，故商数大于2005除以56带余除法中的商，所以。所以，在大于2005的自然数中，被56除后，商与余数相等的数有30个。由于，其中，商数等于36至55。所以，30个整数的和 =。【例】最简分数。它能分解成不超过a个正整数的倒数和，这些整数互不等。解析：也就是写成单位分数的和。我们先看能写出的最大单位分数是多少。为此要利用一下带余除法。设b=aq+r，那么不超过的最大单位分数是。所以我们还需要把分解成单位分数的和。通过观察，这个分数的分子严格减小了。这说明至多a-1次这样的操作之后，我们的任务就完成了。显然这些单位分数的大小不同，个数不超过a。课后练习1. 能将1,2,3,7,8,9填在的方格表中，使横向和竖向相邻两数之和都是质数吗？如果能，请给出一种解法。如果不能，请说明理由。解析：横向和竖向相邻两数之和都是质数，那么奇偶相同的两数不能相邻。所以正中间是奇数，它与2，4，6，8相邻。容易看出无论中间添的n是几，n+2,n+4,n+6,n+8中有
