1、第十六讲一、质数、合数和分解质因数数 论整除【基本概念和知识】1质数和合数一个数除了 1 和它本身，不再有别的约数，这个数叫做质数（也叫做素数）。一个数除了 1 和它本身，还有别的约数，这个数叫做合数。要特别记住：1 不是质数，也不是合数。2质因数与分解质因数如果一个质数是某个数的约数，那么就说这个质数是这个数的质因数。【例题】例 1：三个连续自然数的乘积是 210，求这三个数。 210=2357 可知这三个数是 5、6、7。例 2：两个质数的和是 40，求这两个质数的乘积的最大值是多少？ 解：把 40 表示为两个质数的和，共有三种形式：40=1723=1129=3371723=3911129
2、=319337=111，所求的最大值是 391。例 3：自然数 123456789 是质数，还是合数？为什么？ 解：123456789 是合数。因为它除了约数 1 和它本身，至少还有约数 3，所以它是一个合数。例 4：连续 9 个自然数中至多有几个质数？为什么？解：如果这连续九个自然数在 1 与 20 之间，那么显然其中最多有 4 个质数（如：19 中有 4 个质数 2、3、5、7）。如果这连续的九个自然数中最小的不小于 13，那么其中的偶数显然为合数，而其中奇数的个数最多有 5 个。这 5 个奇数中必只有一个个位数是 5，因而 5 是这个奇数的一个因数，即这个奇数是合数。这样，至多另 4 个
3、奇数都是质数。综上所述，连续九个自然数中至多有 4 个质数。例 5：把 5、6、7、14、15 这五个数分成两组，使每组数的乘积相等。解： 5=5，7=7，6=23，14=27，15=35。这些数中质因数 2、3、5、7 各共有 2 个，所以如把 14（=27）放在第一组，那么 7 和 6（=2 3）只能放在第二组，继而 15（=35）只能放在第一组，则 5 必须放在第二组。这样，1415=210=567。 这五个数可以分为 14 和 15，5、6 和 7 两组。例 6：有三个自然数，最大的比最小的大 6，另一个是它们的平均数，且三数的乘积是 42560。求这三个自然数。分析先大概估计一下，3
4、03030=27000，远小于 42560，404040=64000，远大于 42560。1因此，要求的三个自然数在 3040 之间。解：42560=265719=25（57）（192）=323538（合题意） 要求的三个自然数分别是 32、35 和 38。例 7：有三个自然数 a、b、c，已知 ab=6，bc=15，ac=10。求 abc 是多少？ 解： 6=23，15=35，10=25。 (ab)(bc)(ac)=(23)(35)(25) a2b2c2=223252 (abc)2=(235)2 abc=235=30在例 7 中有 a2=22,b2=32,c2=52，其中 22=4，32=9
5、，52=25，像 4、9、25 这样的数，推及一般情况，我们把一个自然数平方所得到的数叫做完全平方数或叫做平方数。如：12=1，22=4，32=9，42=16，112=121，122=144，其中 1，4，9，16，121，144，都叫做完全平方数。下面让我们观察一下，把一个完全平方数分解质因数后，各质因数的指数有什么特征。 例：把下列各完全平方数分解质因数。9，36，144，1600，275625。解：9=3236=2232144=32241600=2652275625=325472可见，一个完全平方数分解质因数后，各质因数的指数均是偶数。反之，如果把一个自然数分解质因数之后 ，各个质因数的
6、指数都是偶数，那么这个自然数一定是完全平方数。如上例中，36=62，144=122，1600=402，275625=5252。例 8：一个整数 a 与 1080 的乘积是一个完全平方数，求 a 的最小值与这个完全平方数。分析 a 与 1080 的乘积是一个完全平方数。 乘积分解质因数后，各质因的指数一定全是偶数。解： 1080a=23335a，又 1080=23335 的质因数分解中各质因数的指数都是奇数。 a 必含质因数 2、3、5，因此，a 最小为 235。 1080a=1080235=108030=32400。答：a 的最小值为 30，这个完全平方数是 32400。例 9：360 共有多
7、少个约数？ 分析360=23325为了求 360 有多少个约数，我们先来看 325 有多少个约数，然后再把所有这些约数分别剩以 1、 2、22、23，即得到 23325（=360）的所有约数。为了求 325 有多少个约数，可以先求出 5 有多少个约数，然后再把这些约数分别乘以 1、3、32，即得到 325 的所有约数。2解：记 5 的约数个数为 Y1，3 5 的约数个数为 Y2。360（=23325）的约数个数为 Y 。3由上面的分析可知： Y3=4Y2，Y2=3Y1，显然 Y1=2（5 只有 1 和 5 两个约数）。因此 Y3=4Y2=43Y1=432=24。2所以，360 共有 24 个约
8、数。233Y3=4Y2 中的“4”即为“1、2、2 、2 ”中数的个数，也就是其中 2 的最大指数加 1，也就是 360=2325 中质因数 2 的个数加 1；Y =3Y 中的“3”即为“1、3、32”中数的个数，也就是 23325 中2132质因数 3 的个数加 1；而 Y1=2 中的“2”即为“1、5”中数的个数，即 2 3 5 中质因数 5 的个数加 1。因此Y3=（31）（21）（11）=24。对于任何一个合数，用类似于 23325（=360）的约数个数的讨论方式，我们可以得到一个关于求一个合数的约数个数的重要结论：一个合数的约数个数，等于它的质因数分解式中每个质因数的个数（即指数）加
9、 1 的连乘积。例 10：求 240 的约数的个数。解： 240=243151， 240 的约数的个数是：（41）（11）（11）=20 个， 240 有 20 个约数。请你列举一下 240 的所有约数，再数一数，看一看是否是 20 个？二、最大公约数和最小公倍数【基本概念和知识】 1公约数和最大公约数几个数公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。2公倍数和最小公倍数几个数公有的倍数，叫做这几个数的公倍数；其中最小的一个，叫做这几个数的最小公倍数。 3互质数如果两个数的最大公约数是 1，那么这两个数叫做互质数。【例题】例 1：用一个数去除 30、60、75，
10、都能整除，这个数最大是多少？分析 又要求的数去除 30、60、75 都能整除， 要求的数是 30、60、75 的公约数。要求符合条件的最大的数，就是求 30、60、75 的最大公约数。解：（30，60，75）=15所以，这个数最大是 15。例 2：一个数用 3、4、5 除都能整除，这个数最小是多少？分析由题意可知，要求求的数是 3、4、5 的公倍数，且是最小公倍数。解： 3，4，5=60， 用 3、4、5 除都能整除的最小的数是 60。例 3：有三根铁丝，长度分别是 120 厘米、180 厘米和 300 厘米。现在要把它们截成相等的小段，每根都不能有剩余，每小段最长多少厘米？一共可以截成多少段
11、？分析要截成相等的小段，且无剩八，每段长度必是 120、180、300 的公约数；3又每段要尽可能长，要求的每段长度就是 120、180、300 的最大公约数。解：（120，180，300）=60，每小段最长 60 厘米。120601806030060=235=10（段）答：每段最长 60 厘米，一共可以截成 10 段。例 4：加工某种机器零件，要经过三道工序。第一道工序每个工人每小时可完成 3 个零件，第二道工序每个工人每小时可完成 10 个，第三道工序每个工人每小时可完成 5 个。要使加工生产均衡，三道工序至少各分配几个工人？分析要使加工生产均衡，各道工序生产的零件总数应是 3、10 和
12、5 的公倍数。要求三道工序“至少”要多少工人，要先求 3、10 和 5 的最小公倍数。解：3，10，5=30各道工序均应加工 30 个零件。303=10（人）3010=3（人）305=6（人）答：第一道工序至少要分配 10 人，第二道工序至少要分配 3 人，第三道工序至少要分配 6 人。例 5：一次会餐供有三种饮料。餐后统计，三种饮料共用了 65 瓶：平均每 2 个人饮用一瓶 A 饮料，每3 个人饮用一瓶 B 饮料，每 4 个人饮用一瓶 C 饮料。问参加会餐的人数是多少人？ 分析由题意可知，参加会餐人数应是 2、3、4 的公倍数。解：2，3，4=12参加会餐人数应是 12 的倍数。又12212
13、3124=13（瓶）可见 12 个人要用 6 瓶 A 饮料，4 瓶 B 饮料，3 瓶 C 饮料，共用 13 瓶饮料。又6513=5参加会餐的总人数应是 12 的 5 倍。125=60（人）答：参加会餐的总人数是 60 人。例 6：一张长方形纸，长 2703 厘米，宽 1113 厘。要把它截成若干个同样大小的正方形，纸张不能有剩余且正方形的边长要尽可能大。问：这样的正方形的边长是多少厘米？分析由题意可知，正方形的边长即是 2703 和 1113 的最大公约数。在学校，我们已经学过用短除法求两个数的最大公约数，但有时会遇到类似此题情况，两个数除了 1 以外的公约数一下子不好找到， 但又不能轻易断定
14、它们是互质数。怎么办？在此，我们以例 6 为例介绍另一种求最大公约数的方法。对于例 6，可做如下图解：4从图中可知：在长 2703 厘米、宽 1113 厘米的长方形纸的一端，依次裁去以宽（1113 厘米）为边长的正方形 2 个，在裁后剩下的长 1113 厘米、宽 477 厘米的长方形中，再裁去以宽（477 厘米）为边长的正方形 2 个，然后又在裁剩下的长方形（长 477 厘米，宽 159 厘米）中，以 159 厘米为边长裁正方形，恰好裁成 3 个，且无剩余。因此可知，159 厘米是 477 厘米、1113 厘米和 2703 厘米的约数，所以裁成同样大的，且边长尽可能长的正方形的边长应是 159
15、 厘米。所以，159 厘米是 2703 和 1113 的最大公约数。让我们把图解过程转化为计算过程，即：27031113，商 2 余 477；1113477，商 2 余 159；477159，商 3 余 0。或者写为：2703=21113477，1113=2477159，477=3159。当除数为 0 时，最后一个算式中的除数 159 就是原来两个数 2703 和 1113 的最大公约数。可见，477=1593，1113=15932159=1597，2703=15972477=159721593=15917。又因为 7 和 17 是互质数，所以 159 是 2703 和 1113 的最大公约数
16、。我们把这种求最大公约数的方法叫做辗转相除法。辗转相除法的优点在于它能在较短的时间内求 出任意两个数的最大公约数。例 7：用辗转相除法求 4811 和 1981 的最大公约数。解：因为 4811=21981849，1981=2849283，849=3283。所以，（4811，1981）=283。补充说明：如果要求三个或更多的数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个公约数与另外一个数的最大公约数，这样求下去，直至求得最后结果。也可以直接观察，依次试 公有的质因数。例 8：求 1008、1260、882 和 1134 四个数的最大公约数是多少？ 解：因为（1260，1008）
17、=252，（882，1134）=126，又（252，126）=126，所以，（1008，1260，882，1134）=126。求两个数的最小公倍数，除了用短除法外，是否也有其他方法呢？请看例 9。例 9：两个数的最大公约数是 4，最小公倍数是 252，其中一个数是 28，另一个数是多少？ 解：设要求的数为 x，则有：所以，x=4y28=47所以，28x=4y47又因为 4 是 x 和 28 的最大公约数，（y，7）=1，5所以 4y7 是 x 和 28 的最小公倍数。所以，x28=4252所以，x=425228=36所以，要求的数是 36。通过例 9 的解答过程，不难发现：如果用 a 和 b
18、表示两个自然数，那么这两个自然数的最大公约数与最小公倍数关系是：(a，b)a，b=ab.这样，求两个数的最小公倍数的问题，即可转化成先求两个数的最大公约数，再用最大公约数除 两个数的积，其结果就是这两个数的最小公倍数。例 10：求 21672 和 11352 的最小公倍数。解：因为（21672，11352）=1032（1032 可用辗转相除法求得）所以，21672，11352=21672113521032=238392。答：21672 和 11352 的最小公倍数是 238392。三、带余数的除法前面我们讲到除法中被除数和除数的整除问题。除此之外，例如：163=51，即 16=531， 此时，
19、被除数除以除数出现了余数，我们称之为带余数的除法。一般地，如果 a 是整数，b 是整数（b0），那么一定有另外两个整数 q 和 r，0rb，使得 a=bqr.当 r=0 时，我们称 a 能被 b 整除。当 r0 时，我们称 a 不能被 b 整除，r 为 a 除以 b 的余数，q 为 a 除以 b 的不完全商（亦简称为商）。 用带余除式又可以表示为 ab=qr，0rb.【例题】例 1：一个两位数去除 251，得到的余数是 41，求这个两位数。分析这是一道带余数的除法题，且要求的数是大于 41 的两位数，解题可从带余除式入手分析。解： 被除数除数=商余数，即被除数=除数商余数， 251=除数商41
20、，25141=除数商，210=除数商。210=2357，210 的两位数的约数有 10、14、15、21、30、35、42、70，其中 42 和 70 大于 41。所以除数是 42 或 70，即要求的两位数是 42 或 70。例 2：用一个自然去除另一个整数，商 40，余数是 16。被除数、除数、商与余数的和是 933，求被除数和除数各是多少。解：被除数=除数商余数， 即被除数=除数4016。由题意可知：被除数除数=9334016=877，（除数4016）除数=877，除数41=87716=861， 除数=86141=21。6被除数=214016=856。答：被除数是 856，除数是 21。例
21、 3：某年的十月里有 5 个星期六，4 个星期日，问这年的 10 月 1 日是星期几？解：十月份共有 31 天，每周共有 7 天。31=743，根据题意可知：有 5 天的星期数必然是星期四、星期五和星期六。这年的 10 月 1 日是星期四。例 4：3 月 18 日是星期日，从 3 月 17 日作为第一天开始往回数（即 3 月 16 日第二天，3 月 15 日第三天）的第 1993 天是星期几？解：每周有 7 天，19937=284（周）5（天）从星期日往回数 5 天是星期二，所以第 1993 天必是星期二。例 5：一个数除以 3 余 2，除以 5 余 3，除以 7 余 2，求适合此条件的最小数
22、。这是一道古算题，它早在孙子算经中有记载：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何”关于这道题的解法，在明朝就流传一首解题之歌：“三人同行七十稀，五树梅共廿一枝，七子团圆正半月，除百零五便得知。”意思是，用除以 3 的余数乘以 70，用除以 5 的余数乘以 21，用除以 7 的余数乘以 15，再把三个乘积相加。如果这三个数的和大于 105，那么就减去 105，直至小于 105 为止。这样就可以得到满足条件的解。其解法如下：方法一：270321215=2332331052=23符合条件的最小自然数是 23。方法二：3，72=2323 除以 5 恰好余 3。所以，符合条
23、件的最小自然数是 23。方法 2 的思路是什么呢？让我们再来看下面两道例题。例 6：一个数除以 5 余 3，除以 6 余 4，除以 7 余 1，求适合条件的最小自然数。分析“除以 5 余 3”即“加 2 后被 5 整除”，同样“除以 6 余 4”即“加 2 后被 6 整除”。解：5，62=28，即 28 适合前两个条件。想：285，6？之后能满足“被 7 除余 1”的条件？ 285，64=148，148=2171，又 148210=5，6，7所以，适合条件的最小自然数是 148。例 7：一个数除以 3 余 2，除以 5 余 3，除以 7 余 4，求符合条件的最小自然数。解：想23？之后能满足“
24、被 5 除余 3”的条件？232=8。再想：83，5？之后能满足“被 7 除余 4”的条件？ 83，53=53。所以，符合条件的最小的自然数是 53。归纳以上两例题的解法为：逐步满足条件法。当找到满足某个条件的数后，为了再满足另一个条 件，需做数的调整，调整时注意要加上已满足条件中除数的倍数。解这类题目还有其他方法，将会在有关“同余”部分讲到。7例 8：一个布袋中装有小球若干个。如果每次取 3 个，最后剩 1 个；如果每次取 5 个或 7 个，最后都剩2 个。布袋中至少有小球多少个？ 解：25，71=37（个）37 除以 3 余 1，除以 5 余 2，除以 7 余 2，布袋中至少有小球 37
25、个。例 9：69、90 和 125 被某个自然数 N 除时，余数相同，试求 N 的最大值。分析在解答此题之前，我们先来看下面的例子： 15 除以 2 余 1，19 除以 2 余 1，即15 和 19 被 2 除余数相同（余数都是 1）。但是，1915 能被 2 整除。由此我们可以得到这样的结论：如果两个整数 a 和 b，被自然数 m 除的余数相同，那么这两个数之差（大小）一定能被 m 整除。反之，如果两个整数之差恰被 m 整除，那么这两个整数被 m 除的余数一定相同。例 9 可做如下解答：三个整数被 N 除余数相同，N（9069），即 N21；N（ 12590），即 N35；N 是 21 和
26、35 的公约数。要求 N 的最大值，N 是 21 和 35 的最大公约数。21 和 35 的最大公约数是 7，N 最大是 7。四、最大公约数和最小公倍数本讲重点解决与最大公约数和最小公倍数有关的另一类问题有关两个自然数，它们的最大公 约数、最小公倍数之间的相互关系的问题。定理 1两个自然数分别除以它们的最大公约数，所得的商互质。即如果(a , b)=d，那么(ad , bd )=1.证明：设 ad=a1 , bd=b1 , 那么 a=a1d , b=b1d .假设(a1 , b1)1，可设(a1 , b1)=m(m1)，于是有 a1=a2m , b1=b2m.(a2 , b2 是整数)所以，a
27、= a1d= a2md , b= b1d= b2md .那么 md 是 a、b 的公约数。又m1，mdd.这就与 d 是 a、b 的最大公约数相矛盾。因此，(a1 , b1)1 的假设是不正确的。所以只能是(a1 ,b1)=1，也就是(ad , bd )=1.定理 2两个数的最小公倍数与最大公约数的乘积等于这两个数的乘积。（证明略）定理 3两个数的公约数一定是这两个数的最大公约数的约数。（证明略）下面我们就应用这些知识来解决一些具体的问题。例 1甲数是 36，甲、乙两数的最大公约数是 4，最小公倍数是 288，求乙数。解法 1：由甲数乙数=甲、乙两数的最大公约数两数的最小公倍数，可得36乙数=
28、4288乙数=428836解出乙数=32解法 2：因为甲、乙两数的最大公约数为 4，则甲数=49，设乙数=4b1，且（b1，9）=1。8因为甲、乙两数的最小公倍数是 288， 则288=49b1，b1=28836解出 b1=8所以，乙数=48=32 答：乙数是 32。例 2已知两数的最大公约数是 21，最小公倍数是 126，求这两个数的和是多少？解：要求这两个数的和，我们可以先求出这两个数各是多少。设这两个数为 a、b，ab。因为这两个数的最大公约数是 21，故设 a=21a1 ,b=21b1，且（a1，b1）=1。因为这两个数的最小公倍数是 126，所以解出126=21a1b1 a1=1b1
29、=6 a=211=21b=216=126于是a1b1=6 a1=2b1=3a=212=42 b=213=63则因此，这两个数的和为 21126=147，或 4263=105。答：这两个数的和为 147 或 105。例 3已知两个自然数的和是 50，它们的最大公约数是 5，求这两个自然数。解：设这两个自然数分别为 a 与 b，ab。因为这两个自然数的最大公约数是 5，故设 a=5a1，b=5b1，且（a1，b1）=1，a1b1。因为 ab=50，所以有 5a15b1=50，a1b1=10。满足（a1，b1）=1，a1b1 的解有：a1=1b1=9a1=3b1=7所以，a=51=5b=59=45或
30、a=53=15b=57=35答：这两个数为 5 与 45 或 15 与 35。例 4已知两个自然数的积为 240，最小公倍数为 60，求这两个数。解：设这两个数为 a 与 b，ab，且设（a，b）=d , a=da1 , b=db1 ,其中（a1，b1）=1 。因为两个自然数的积=两数的最大公约数两数的最小公倍数，所以240=d60解出d=4所以a=4a1 , b=4b1.因为 a 与 b 的最小公倍数为 60， 所以4a1b1=60,于是有解出a1b1=15。 a1=1b1=15 a=41=4b=415=60a1=3 b1=5或所以a=43=12b=45=20答：这两个数为 4 与 60 或
31、 12 与 20。9已知两个自然数的和为 54，它们的最小公倍数与最大公约数的差为 114，求这两个自然数。解：设这两个自然数分别为 a 与 b，ab，( a , b )=d,a= da1 ,b=db1,其中(a1 , b1)=1.因为 ab=54，所以 da1db1=54。于是有 d(a1b1)=54，因此，d 是 54 的约数。又因为这两个数的最小公倍数与最大公约数的差为 114， 所以 da1b1d=114,于是有 d(a1b11)=114,因此，d 是 114 的约数。故 d 为 54 与 114 的公约数。由于（54，114）=6，6 的约数有：1、2、3、6，根据定理 3，d 可能
32、取 1、2、3、6 这四个值。如果 d=1，由 d(a1b1)=54，有 a1b1=54；又由 d(a1b11)=114，有 a1b1=115。115=1115=523，但是 1115=11654，523=2854，所以 d1.如果 d=2，由 d(a1b1)=54，有 a1b1=27；又由 d(a1b11)=114，有 a1b1=58。58=158=229，但是 158=5927，229=3127，所以 d2.如果 d=3，由 d(a1b1)=54，有 a1b1=18；又由 d(a1b11)=114，有 a1b1=39。39=139=313，但是 139=4018，313=1618，所以 d
33、3.如果 d=6 ，由 d(a1b1)=54，有 a1b1=9；又由 d(a1b11)=114，有 a1b1=20。20 表示成两个互质数的乘积有两种形式：20=120=45，虽然 120=219，但是有 45=9，例 5所以取 d=6 是合适的，并有 a1=4,b1=5. a=64=24 , b=65=30.答：这两个数为 24 和 30。例 6已知两个自然数的差为 4，它们的最大公约数与最小公倍数的积为 252，求这两个自然数。解：设这两个自然数分别为 a 与 b，且 ab，a = da1 , b = db1 , (a1 , b1)=1.因为 ab=4，所以 da1 db1=4，于是有 d
34、(a1 b1)=4，因此 d 为 4 的约数。2因为这两个自然数的最大公约数与最小公倍数的积为 252，所以 dda1b1=252，于是有 d a1b1=(23)27,因此 d 为 23 的约数。故 d 为 4 与 23 的公约数。由于（4，23）=2，2 的约数有 1 和 2，所以 d 可能取 1、2 这两个值。2如果 d=1，由 d(a1 b1)=4，有 a1 b1=4；又由 d a1b1=252，有 a1b1=252。252 表示成两个互质数的乘积有 4 种形式：252=1252=463=736=928，但是 2521=2514，634=594，367=294，289=194，所以 d1
35、.2如果 d=2，由由 d(a1 b1)=4，有 a1 b1=2；又由 d a1b1=252，有 a1b1=63。63 表示为两个互质数的乘积有两种形式：63=163=79，但 631=622，而 97=2，且（9，7）=1，所以 d=2，并且 a1=9，b1=7.因此 a=29=18，b=27=14.答：这两个数为 18 和 14。在例 2例 5 的解答中之所以可以在假设中排除 a=b 这种情形在各例中都只假设了 ab, 分别是由于：例 2 和例 5，若 a=b，则（a , b）=a , b=a，与条件（a , b）a , b矛盾；例 3，若 a=b， 则 a=b=（a , b）=5，因此
36、ab=1050，与条件矛盾；例 4，ab=240 不是平方数。从例题的解答中可以看出，在处理涉及两数的最大公约数或者最小公倍数的很多问题中，经常用到的基本关系是：若两数为 a、b，那么 a=a1d , b=b1d，其中 d=(a , b) , (a1 , b1)=1，因此a , b=da1b1，有时为了确定起见，可设 ab。对于很多情形，可以排除 a=b 的情形（如上述所示），而只假设 ab。10五、同余的概念和性质你会解答下面的问题吗？问题 1：今天是星期日，再过 15 天就是“六一”儿童节了，问“六一”儿童节是星期几？ 这个问题并不难答，因为，一个星期有 7 天，而 157=21，即 15
37、=721，所以“六一”儿童节是星期一。问题 2：1993 年的元旦是星期五，1994 年的元旦是星期几？这个问题也难不倒我们。因为，1993 年有 365 天，而 365=7521，所以，1994 年的元旦应该是星期六。问题 1、2 的实质是求用 7 去除一总的天数后所得的余数。在日常生活中，时常要注意两个整数用某一固定的自然数去除，所得的余数问题。这样就产生了“同余”的概念。如问题 1、2 中的 15 与365 除以 7 后，余数都是 1，那么我们就说 15 与 365 对于模 7 同余。余同定义：若两个整数 a、b 被自然数 m 除有相同的余数，那么称 a、b 对于模 m 同余，用式子表示
38、为：ab ( modm ) 上式可读作：a 同余于 b，模 m。( * )同余式( * )意味着（我们假设 ab）:ab=mk，k 是整数，即 m(ab).例如：15365（mod7），因为 36515=350=750。5620（mod9），因为 5620=36=94。900（mod10），因为 900=90=109。由例我们得到启发，a 可被 m 整除，可用同余式表示为： a0( modm ).例如，表示 a 是一个偶数，可以写a0(mod2) 表示 b 是一个奇数，可以写b1( mod2 )补充定义：若 m 不能整除（ab），就说 a、b 对模 m 不同余，用式子表示是：ab(mod m)
39、我们书写同余式的方式，使我们想起等式，而事实上，同余式与等式在其性质上相似。同余式有 如下一些性质（其中 a、b、c、d 是整数，而 m 是自然数）。性质 1：aa(mod m)，（反身性）这个性质很显然，因为 aa=0=m0.性质 2：若 ab(mod 性质 3：若 ab(mod 性质 4：若 ab(mod 性质 5：若 ab(mod性质 6：若 ab(modm)，那么 ba(mod m)，（对称性）。m)，bc(modm)，cd(mod m)，cd(modm)，那么 ac(mod m)，（传递性）。m)，那么 acbd(mod m)，（可加减性）。 m)，那么 acbd(mod m)，（可
40、乘性）。m)，那么 anbn(mod m)，（其中 n 为非 0 自然数）。性质 7：若 acbc(mod m)，(c，m)=1，那么 ab(mod m)。注意：同余式性质 7 的条件(c，m)=1，否则像普通等式一样，两边约去，就是错的。例如 610(mod 4)，而 35(mod 4)，因为（2，4）1。请你自己举些例子验证上面的性质。同余是研究自然数的性质的基本概念，是可除性的符号语言。11例 1判定 288 和 214 对于模 37 是否同余，74 与 20 呢？解： 288-214=74=372， 288214（mod 37）. 74-20=54，而 3754， 7420(mod 3
41、7).例 2求乘积 4188141616 除以 13 所得的余数。若先求乘积，再求余数，计算量太大。利用同余的性质可以使“大数化小”，减少计算量。解： 4182（mod 13），8148(mod 13)，16164(mod 13), 根 据 同 余 的 性 质 5 可 得 ： 41881416162846412(mod 13).答：乘积 4188141616 除以 13 余数是 12。例 3求 14389 除以 7 的余数。分析同余的性质能使“大数化小”，凡求大数的余数问题首先考虑用同余的性质化大为小。这道题先把底数在同余意义下变小，然后从低次幂入手，重复平方，找找有什么规律。解法 1： 14
42、33(mod 7)， 14389389(mod 7). 89=641681， 而 322(mod 7)344(mod 7)38162(mod 7)3164(mod 7),332162(mod 7),3644(mod 7).389364 31638 344235(mod 7), 143895(mod 7).答：14389 除以 7 的余数是 5。解法 2：证得 14389389(mod 7)后， 3632 34241(mod 7), 384(36)141(mod 7),38938434 31435(mod 7). 143895(mod 7).例 4四盏灯如图所示组成舞台彩灯，且每 30 秒钟灯的
43、颜色改变一次，第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，这样一直进行下去。请问开灯 1 小时四盏灯的颜色如何排列？分析与解答经观察试验我们可以发现，每经过 4 次互换，四盏灯的颜色排列重复一次。而 1 小时=60 分钟=12030 秒，所以这道题实质是求 120 除以 4 的余数。因为 1200（mod 4），所以开灯 1小时四盏灯的颜色排列刚好同一开始一样。12例 5设自然数 N = an an-1.a1a0 ，其中 a0 、 a1 、 a2 、 an 分别是个位、十位、上的数码，再设M = a0 + a1 + . + an ，求证：NM(mod 9).证明： N = an an-1.a1a0= an 100 0(n个0) + an-1 100 0(n -1个0) + + a1 10(1个0) + a0= a 10n + a10n-1 + + a 10 + ann-110又 11(mod 9),101(mod 9),1021(mod 9),10n1(mod 9).上面这些同余式两边分别同乘以 a0 、 a1 、 a2 、 an ，再相加得：a + a 10 + a 102 + + a 10n012n a0 + a1 + . + an (mod 9)，即 NM(mod 9).这道例题证明了十进制数的一个特有的性质：任何一个整数模 9 同余于它的各数
