奥数讲义数论专题：余数及同余.docx

华杯赛数论专题： 余数及同余一、带余除法的定义：一般地，如果a是整数，b是整数(bHO),若有aFb=q・・・r，也就是a=bXq+r, OWrVb ；我们称上面的除法算式为一个带余除法算式.这里：(1) 当f二°时：我们称a可以被b整除，记作b|a，q称为a除以b的商或完全商(2) 当时：我们称a不可以被b整除，记作」"，q称为a除以b的商或不完 全商二、 同余的概念两个整数被同一个大于1的整数m除，所得的余数相同，就说这两个整数对于除数m 来说是同余的•也可以换句话来说这个概念，如果两个整数的差能被大于1的整数m整除， 那么这两个整数对于除数m来说是同余的.同余的概念和符号都是德国伟大数学家高斯引进的•一般地，两个整数a和b，除以大 于1的正整数m,如果所得的余数相同，就说a、b对于模m同余，记作a三b (mod m).由于一个整数被m除的余数只能是0、1、2、3、…、m-1这m个数，所以全体整数可 按被m除的余数分类，凡是余数相同的归为一类，全体整数就被划分成了m类，同一类中 的任何两数被m除的余数都相等，即同一类中任何两数的差都能被m整除，不同类的任何 两数被m除的余数都不相等.三、 同余的性质1. 如果a三b (mod m)，那么m| (a-b)；如果整数a和b对于模m是同余的，那么a 与b的差能被m整除.2. a三a (mod m)，即任何整数都与自身同余.3. 若 a三b (mod m),贝y b三a (mod m).4. 若 a三b (mod m)，b三c (mod m),贝y a三c(mod m).5. 若 a三b (mod m)，c三d (mod m),贝y a+c三b+d (mod m)，a—c三b — d (mod m)，aXc三bXd (mod m).6. 若a三b (mod m),则an三bn (mod m)。

其中n为正整数).例1.用一个两位数除708,余数为43，求这个两位数.【答案】95【解答】根据被除数-余数=商乂除数，可知，所求两位数一定是707-43=665的大于 43 的约数，所以所求的两位数是95.例2.数713、 1103、 830、 947被一个数除所得余数相同(余数不为0) ，求这个除数.【答案】39，13或 3.【解答】1103 — 713=390=3X 13X2X5, 947 — 830=117=3X 13X3, 1103 — 947=156=2X 13X3X2,除数为 39, 13 或 3.例3•从1、2.-100中最多能选出多少个数，使选出的数中每两个的和都不能被3整 除？【答案】35【解答】1、2.-100中，除以3余1的数共34个，即1、4、7、10、…、100.除以 3余2的数共33个,选出的数中,如果有除以3余1的,就一定不能有除以3余2的；如 果有除以3余2的,也就不能有除以3余1的所有这两种数只能选出一种,我们选个数 较多的一种，即1、4、7、10、…、100.此外，被3整除的数只能选出一个，所以最多可 以选出 34+1=35 个数.例 4.求财除以7的余数.【答案】5143 = 3fmad7]【解答】方法一：由于 （143被7除余3），14郸三勢（mod/）甘桦 禅所以 （ 被7除所得余数与 被7除所得余数相等）而爭=729, 7241（11!眄（729除以7的余数为1）,样三书三亨三5（mod7）所以 •故14带'除以7的余数为5方法二： 计算 被 7 除所得的余数可以用找规律的方法，规律如下表：例5.53 n -xiggi的末三位数是多少？【答案】625【解答】首先，仅考虑后三位数字，所求的数目相当于^汇九…弟门的平方再乘以阳典四以997冨孙的末三位.而993x^5x997刈99 =型 刈99 网 加(993000-9站)x (995000 - 995 x3) (993000-953)x(995000-2985)其末三位为叭然后来看前者•它是一个奇数的平方，设其为 （k为奇数），由于（沐）"防乜+唧-1），而奇数的平方除以8余1,所以L-1是8的倍 ,, 25k3-11 上，,, 25（k3-l） = 200m数，则 是200的倍数，设 ，则（S^j3 = 25+25（Ar: -1） = 25 + 200^所以它与105的乘积(5汀 ^105=(25+200^)x105= 21000^+2625，所以所求的末三位都是 625.例 6.有 2 个三位数相乘的积是一个五位数，积的后四位是1031，第一个数各个位的数 字之和是10，第二个数的各个位数字之和是8，求两个三位数的和.【答案】360【解答】观察条件仅给出了两个乘数的数字之和，同时发现乘积的一部分已经给出， 即乘积的一部分数字之和已经给出，我们可以采用弃九法原理的倒推来构造出原三位数。

因为这是一个一定正确的算式，所以一定可以满足弃九法的条件，两个三位数除以9的余 数分别为1和8,所以等式一边除以9的余数为8,那么口1031除以9的余数也必须为8, □只能是3将31031分解质因数发现仅有一种情况可以满足是两个三位数的乘积，即31031 = 31x1001 = 143x217.所以两个三位数是143和 217，那么两个三位数的和是360例7.三个连续的两位数除以5 的余数之和是7，除以 7的余数之和是9，除以 9 的余 数之和是15.则这三个数除以11的余数之和■—.【答案】12【解答】三个连续的两位数除以5 的余数之和是7，那么只可能是3+4+0=7，所以第一 个数被5 除余3；同样方法可以得出第一个两位数除以7余 2，除以 9余 4或者 7.如果第一个两位数除以9余4,那么由于它除以7余2,所以它只能是7X9-5=58，满 足除以 5 余 3 的要求.这时三个数除以11 的余数依次是3、4和 5，和是12.如果第一个两位数除以9余7,那么由于它除以5余3,所以它只能是5X9-2=43或者 5X9X2-2=88，但是它们都不满足除以7余2的要求.因此题目所求的余数之和是12.例8•定义表示a、b中较大的数除以较小的数所得的余数，例如14Q6 = 6Q14 = 2，那么在小于100的数中，使得^29 = 5的自然数x有 个.【解答】如果X大于29，那么X应该是29的倍数加上5,这样的数有29X 1+5=34, 29X2+5=63,29X3+5=92.如果x小于29,那么x应该是29-5=24的约数，并且大于5,这样的数有6、8、12、 24.所以满足条件的数一共有7个.例9.一个自然数的7倍除以231所得的余数是28,它的11倍除以231所得的余数是 143,那么它的15倍除以231所得的余数是—.【答案】27【解答】方法一：由已知,这个数除以33的余数是4,除以21的余数是13, 因此它除以231的余数是202,那么它的15倍除以231的余数是202X 15三231=13……27.方法二：注意到11X2-7=15，所以所求余数为143X2-28三258三27(mod 231). 例10.有一个自然数,用它分别去除63,90,130都有余数,3个余数的和是25.这3 个余数中最大的一个是多少？【答案】20【解答】因为63+90+130-25=258，所以除数一定是258的约数.而258=2X3X43因为25三3〉8,说明至少有一个余数大于8,因此除数大于9.但又显然小于63 (否则 它去除63的余数就是63),所以满足要求的除数只可能是43,经检验,它除63,90, 130的余数分别是20,4,1,满足要求.所求最大余数是20.例11.在小于1000的正整数中,分别除以18及33所得余数相同的数有多少个？【答案】99 【解答】余数只能是0至17,用18及33的公倍数分别加上0~17均可,小于1000的 自然数中18与33的公倍数有198、396、594、792、990,前四个数分别加上0至17各得 18个数,990只能加上0到9这十个数,此外1到17这17个数也符合题目的要求.综上所述共18X4+10+17=99个.例12.甲、乙、丙三数分别为603, 939, 393.某数A除甲数所得余数是A除乙数所得 余数的2倍，A除乙数所得余数是A除丙数所得余数的2倍•求A等于多少？【答案】17【解答】某数A除甲数所得余数是A除乙数所得余数的2倍，A除乙数所得余数是A 除丙数所得余数的2倍，也即某数A除甲数与除乙数的2倍及丙数的4倍余数相同， 939X2=1878,393X4=1572；1878-1572=306=2X3X3X17,1572-603=969=3X17X19,306 与 969 的公约数有：3、17 和 51，3 可以整除甲、乙、丙三个数，51经检验不符合 17符合，所以，A=17.。