1.2.2 充要条件优质课教案设计

第五节：同余

一、基本性质

整除的性质非常重要，但是并不能解释所有的问题，为此我们进行了推广——同余。同余最早是由数学家Gauss引入的概念，我们可以将其理解为“余同”（余数相同）。首先来看一下同余的表达方式和定义。

定义1：如果a、b除以m(m>1)得到的余数相同，那么称a、b对于模m同余，记作ab(modm)。否则称a、b对模m不同余。

性质1：ab(modm)也就是说m | a-b 性质1非常重要，由性质1可证得其余性质。

性质2：可加性：若ab(modm),cd(modm)，那acbd(modm),

acad(modm)；

性质3：可乘性：若ab(modm),cd(modm)则acbd(modm)

性质4：可乘方性：若ab(modm)，那么anbn(modm)

性质5：若ab(modm),ab(modn),那么ab(mod[m,n])

性质6：如果(a,m)1，那么存在一个整数b，使得ab1(modm)

性质7：如果abac(modm)bc(modm)(a,m)

特别的，若（a,m）=1则

1

第六节：同余应用及常见的题型

一、求余数问题

常见的问题如求星期几之类的题型，其实也就求被7整除的余数。通过同余的运算，可以很快地求得结果。

例1：如果今天是周六，求242009天以后是星期几？

例2：某数除680,970和1521余数相同，这个数最大是几？

例3:126

547+324

除以13的余数是多少？

二、整除特征判别法：

注意：一个数能否被2、3、4、5、6、7、8、9、11、13等数整除，都有其特别的判别方法。

如何选取合适的方法，并对此作为推广是我们必须要学会的内容。

（1）可以被2整除的数：最末一位数是2的倍数。可以被5整除的数：最末一位数是5的倍数。

（2）可以被4整除的数：最末两位数是4的倍数。可以被25整除的数：最末一位数是25的倍数。

（3）可以被8整除的数：最末三位数是8的倍数。可以被125整除的数：最末一位数是125的倍数。

（4）可以被3和9整除的数，其各位数字之和是3和9的倍数。

（5）可以被6整除的数，必须同时满足可以被2、3整除的特性。

（6）可以被7，11或13整除的数。三位三位依次相减是7或13的倍数。

（7）可以被11整除的数，奇数位数字之和减去偶数位数字之和是11的倍数。

试证明上述方法，并作出自己的推广：

三、奇偶性问题

奇数±奇数=偶数

奇数±偶数=奇数

偶数±奇数=奇数

偶数±偶数=偶数

奇数个奇数的和为偶数，偶数个奇数的和为偶数

奇数的约数都是奇数

奇偶性问题经常结合反证法来进行考虑，常常可以给复杂的问题带来明显的简化。

例1：可不可以在下列数间添加+、-，使得等式成立，为什么？

（1）2008 2007 2006 2005 ……

3 2 1 = 0 （2）2009 2008 2007 2006 ……

3 2 1 = 0

例2：现有2009枚硬币，都是正面朝上，有一个班的学生，每个学生对这些硬币做操作，选取其中100枚硬币将其反过来一次。问，一个班级的学生操作完毕后，是否可能使得所有的硬币都正面朝上？如果是2010

2

枚硬币呢？

例3：现有两个17位数，互为反序数：a1a2...a17,a17a16...a1，试证明，他们的和的所有数码中必有一个偶数

例4：把1,2,3,…….99这99个数任意排列成

,则判断（1-

）（2-

）……（99-

）的奇偶性。

四、完全平方数

完全平方数是常考的一类问题。尤其是其奇偶性的特性，更是重中之重。

（1）

或 或 （2）

或

或 或

试证明以上性质，利用这两个性质，可以给很多题目带来简化。

例1：设质数从小到大排列为

,

,

……证明：对于任意大于1的整数n，

……

都不是完全平方数。

*例2：求最小的整数n，使得存在整数x1,x2,......,xn，满足x1x2......xn1599

例3：如果正整数a，b满足21|ab，那么441|ab

例4：已知n是正整数，且2n+1和3n+1都是完全平方数，证明：40|n

3 2222444

五、尾数问题

所谓尾数其实也就是除以10的余数。当然，绝大多数的题目，不需要用到这个同余，因为尾数是明显有比较简单的规律的。

n1 n2 n3 n4 n5 n6 n7 n8 ……

1 1 1 1 1 1 1 1 1 ……

2 2 4 8 6 2 4 8 6 ……

3 3 9 7 1 3 9 7 1 ……

4 4 6 4 6 4 6 4 6 ……

5 5 5 5 5 5 5 5 5 ……

6 6 6 6 6 6 6 6 6 ……

7 7 9 3 1 7 9 3 1 ……

8 8 4 2 6 8 4 2 6 ……

9 9 1 9 1 9 1 9 1 ……

我们可以看到总是以4作为一个周期的。这样就可以很快地判断出尾数了。

当然有一些题目中会问末两位的值，此时就通过mod 100来处理，或者通过后面提到的同余方程组的方法来处理即可。

例2：试求3

2009的末两位数的大小。

第七节：简单的同余方程

一、同余方程：

简单的同余方程有点像一次方程。形如axb(modp)形式的方程被称为同余方程。

其实解这样的问题就是一个辗转相除法：

我们注意到axb(modp)其实就是找到一个数k，使得a|bkp，也就是说寻找kpb(moda)的解，如此不断重复，注意到模的数越来越小，最终反过来处理就可以得到结果了。

例9：试解下面的同余方程：

34x10(mod23)

73x10(mod101)

63x15(mod153)

4

同余方程有很多的应用，我们可以看以下的这个例子

例10：（五猴分桃问题）5只猴子得到了一堆桃子，他们发现那堆桃子不能被均匀分5份，于是猴子们决定先去睡觉，明天再讨论如何分配。夜深人静的时候，猴子A偷偷起来，吃掉了一个桃子后，它发现余下的桃子正好可以平均分成5份，于是它拿走了一份；接着猴子B也起来先偷吃了一个，结果它也发现余下的桃子恰好可以被平均分成5份，于是它也拿走了一份；后面的猴子C、D、E一次如法炮制，先偷吃一个，然后将余下的桃子平均分成5份并拿走了自己的一份，问：这一堆桃子至少有几个？

二、中国剩余定理

当我们遇到多个同余方程组时，可以通过分别解每个方程得到如下的形式：

xa1(modp1)xa(modp)22

.......xan(modpn)对于如上的方程组而言，有以下性质：在连续的[p1,p2,...,pn]个数当中，至多只有一个数满足条件。

换句话说，就是要找到在1、2、……、[p1,p2,...,pn]中的满足条件的一个数，这样，我们就能求出所有的满足方程组得解了。

此处使用的方法就是中国剩余定理的方法：

步骤：

（1）先考虑a1，寻找一个常数k1，使得k1[p2,p3,...,pn]1(modp1)，并且记k1[p2,p3,...,pn]C1

（2）接着，通过类似地步骤，求得向对于不同a时候的C值

那么最后，构造一个简单的数即可满足同余方程了

xa1C1a2C2......anCn就是我们想要求得的一组解了。

试了解其含义。

另：中国剩余定理（即孙子定理）

设n2,m1,m2,,mn是两两互质的正整数，记M=mi,Mii1nM(i1,2,,n)则同余方程组

mixci(modmi)(i1,2,,n)

5

有且只有解

xMc(modM).

（△）

iiii1n其中Mii1(modmi),i1,2,,n.

（△△）

【证明】由(mi,mj)1(ij)知，(Mi,mj)1，因此每一个同余方程Miy1(modmi)

（i=1，2，…n）都有解，于是必存在i,使得Mii1(modm).又因MmiMi,mi|Mi(ij),

所以对模mi(i1,2,,n)有M11c1MiiciMnncnMiicici(modmi).故（△△）是（△）的解. 若x1,x2是适合（△）的任意两个解，则x1x2(modmi),i1,2,,n,因(mi,mj)1(ij).

故x1x2(modm1m2mn),即x1x2(modM),因此，（△△）是（△）的惟一解.

例1：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？——《孙子算经》

事实上，在孙子算经中，还有一首简单的打油诗来帮助记忆这样的一个思考方式

三人同行七十稀，五树梅花廿一枝，七子团圆整半月，除百零五便得知。

这首诗就隐藏了解决这类题目的主要过程和手段。

第八节：Fermat小定理与Wilson定理

6 首先分别介绍Fermat小定理和Wilson定理的内容：

Fermat小定理：对于质数p，如果存在正整数a，（a,p）=1，那么必有p|aWilson定理：对于质数p，p|(p1)!1。反之亦然。

p11。

例1：试分别证明Fermat小定理和Wilson定理

例2：设x是一个正整数，p是x2+1的一个奇质数因子，证明p1(mod4)

同余问题虽然在学校的教学中出现得很少，但是，其在数学竞赛的应用性就非常强了。同余的内容虽然是一个新知识，但是我们可以注意到启示它的运算并不算。一般都有比较通用的办法来加以解决。

其实数论的问题和各个不同数学分支的结合都非常紧密，是一个非常综合性的学科。

希望同学们在课余时间按可以多多思考同余的问题，更深入地掌握的解决这类问题的手段。

【模拟试题】

1. 今天是星期日，再过2. 求天又是星期几？

除以3所得的余数。

3. 某数除680，970和1521，余数相同，这个数最大是几？

4. 有一列数排成一行，其中第一个数是3，第二个数是7，从第三个数开始，每个数恰好是前两个数的和，那么，第1997个数被3除，余数是几？

5. 若将一批货物共千克装入纸箱，每箱装10千克，最后余多少千克？若每箱装17千克，最后还余多少千克？

7

6、1309被一个质数相除，余数是21，求这个质数。

7、1796被一个质数相除，余数是24，求这个质数。

8、求2001×2000除以7的余数。

9、求123×345+234×456除以11的余数。

10、有一个大于1的整数，它除1000、1975、2001都得到相同的余数，那么这个整数是多少？

11、有三个数1989、901和306被同一个自然数除，得到相同的余数，求这个自然数。

12、两个自然数相除，商15，余3，被除数、除数、商、余数的和是853，求被除数。

8、两数相除商40余7，被除数、除数、余数和商的和是710，求被除数。

13、有一个数除以3余1，除以4余2，问这个数除以12，余数是几？

14、一个数除以5余1，除以6余3，除以7余4，这个数最小是几？

15、3867×4253＝1644□351，求□里的数。

4937×6845＝3379□765，求□里的数。

16、两个自然数相除，商8余16，被除数、除数、商与余数的和为265，求除数是多少？

8

17、写出除以8所得的商和余数（不为0）相同的所有的数。

18、2002×2002-2001除以9的余数是多少？

19、当2002和1781除以某一个自然数，余数分别是2和1，那么这个数最大是多少？

20、一个数除以17的余数是5，被除数扩大2倍，余数是多少？

21、有一个数，除以3余数是1，除以4余数是3 。这个数除以12，余数是多少。

22、570被一个两位数除，余数是15，这个两位数是多少？

23、有一个数加上22的和被9除余3，这个数加上35的和被9被余几？

B组

24、有一个整数，用它去除45，53，143得到的3个伤痕的和是20，这个数是多少？

25、有一个数用它去除100，余数是1，用它去除50，余数是6，求这个数。

26、把几十个苹果平均分成若干份，每份9个余8个，每份8个余7个每份4个余3个。这堆苹果共有多少个？

27、有一个数被5和11整除均余4，被3正好整除，这个数最小是几？

28、求被4除余2，被6除余2，被9除余5的两位数。

9

29、一个数能被3、5、7整除，若用11去除则余7，这个数最小是几？

30、小红收数学学习小组买奥数练习本的钱，她只记下四组各交的钱，第一组6.3元，第二组7.7元，第三组6.3元，第四组9.1元，又知道每本练习本价格都超过1角，求数学学习小组共有多少人？（提示：练习本单价是总价的公约数。）

31、五年级两个班的学生一起排队出操，如果8人排一行，多出一个人；如果11人排一行，同样多出一个人。这两个班最小共有多少人？（提示：如果减去一人那么人数就能被8和11整除了。）

32、一个数被4除余3，被5除余4，被6除余5，这样的数中最小的是几？（提示：余数与除数有什么关系？）

33、一筐苹果，如果按5个一堆放，最后多出3个；如果按6个一堆放，最后多出4个；如果按7个一堆放，还多出1个；这筐苹果至少有多少个？（提示：先满足被7除余1，再从中找出被6除余4……）

竞赛题精选

1、若2836，4582，5164，6522四个自然数都被同一个自然数相除，所得余数相同且为两位数，除数和余数的和为（

）。（2001小学数学奥林匹克试题决赛B卷）

2、一个自然数除以3余2，除以5余2，除以7余5，除以9余5，除以11余4，则满足这些条件的最小自然数是（

）。（1996年我爱数学少年冬令营试题）

3、某数除以11余8，除以13余10，除以17余12，那么这个数的最小可能值是（

）。（1998年小学数学奥林匹克试题预赛A卷）

10

4、一个小于200的数，它除以11余8，除以13余10，那么这个数是（

）。（1998年小学数学奥林匹克试题预赛B卷）

5、在一道有余数的除法算式中，被除数、除数，商和余数的和是599，已知商是15，余数是12，请问，题目中的除数是多少？（厦门实小

2000-2001学年第二学期数学科竞赛卷B组）

11