高中数学第14讲数论+同余（上）.doc

PAGE8

高一·联赛班·第5讲·学生版

第五讲初等数论2同余

本讲概述

同余是大数学家高斯的一个天才发明，这个符号使得原来难以表述的很多数论问题表述起来简单清晰.利用同余符号，可以方便地处理各种复杂的数字相对于另一数的余数这一类问题.本讲将着重讲述同余的基本性质，并利用这些性质来解决各类同余的典型问题.此外，基于同余，还给出了剩余系与完系的概念.尽管联赛大纲没有明确对这两个概念作要求，但是有了对剩余系的基本认识后对很多问题处理起来会更为方便.

同余的定义：

设m是一个给定的正整数，如果两个整数a与b用m除所得的余数相同，则称a与b对模同余，记作，否则，就说a与b对模m不同余.（用符号上面加一个斜线来表示，类似不等符号）.

显然，；

剩余类与完全剩余系（简称完系）

我们可以将所有的整数按模m分类．例如：按模2分类，可将所有整数分成两类，模2余1的分成一类，即奇数；模2余0的一类，即偶数．按模3分类，可分成3k,3k+1,3k-1三种类型；等等.

剩余类的定义：设m为一给定的正整数，则全体整数可以分为m个集合K0，K1，…，Km-1，这里Kr={x|x∈Z,x≡r(modm)},r=0,1,…,m-1．我们称K0，K1，…，Km-1为模m的剩余类．

在模m的m个剩余类中分别取一个数，共取出m个，我们把这m个数成为模m的一组完全剩余系,简称完系.例如：0,1,2，…,m-1就是一组完系，显然，它们两两对模m不同余.

性质1．每个整数在且仅在模m的一个剩余类中．

性质2．若a0,a1,…，am-1是模m的一个完系，而(a,m)=1,b∈Z，则aa0+b,aa1+b,…,aam-1+b也是模m的一个完系．（此性质可自行证明，联赛范围内一般不需要掌握）

同余的性质非常之多，以下仅列举最常用的一些，

（1）自反性：a≡a(modm)(a为任意自然数)

（2）对称性：若a≡b(modm)，则b≡a(modm)

（3）传递性：若a≡b(modm),b≡c(modm)，则a≡c(modm)

（4）可加减性：若a≡b(modm),c≡d(modm)，则a±c≡b±d(modm)

（5）可乘性：若a≡b(modm),c≡d(modm)，则ac=bd(modm)

（6）可乘方性：若a≡b(modm),n∈N+，则an=bn(modm)

注意：一般地同余没有“可除性”，但是

（7）如果：ac≡bc(modm)且(c,m)=1，则a≡b(modm)

如果ac≡bc(modm),(c,m)=d，则a≡b(mod)

（8）如果a≡b(modm),a≡b(modn)且[m,n]=k，则a≡b(modk)（[m,n]表示m,n的最小公倍数）

（9）设p∈N+,p≥2，则任何一个p进制自然数与其数码和(p进制下各数码之和)对模p-1同余；特别地，p=10时，是我们熟知的“弃九法”的理论依据：

任一正整数与其十进制表示中各位数字之和对模9同余.

利用“弃九法”可以方便地解决很多与数字和相关的问题.

另外，利用同余与各种乘法公式以及二项式定理展开式相结合往往威力更大，但我们这里暂时不涉及.

例题精讲

证明上述理论部分中的部分性质：

同余的可除性：如果：ac≡bc(modm)且(c,m)=1，则a≡b(modm)

证明若a0,a1,…，am-1是模m的一个完系，而(a,m)=1,b∈Z，则aa0+b,aa1+b,…,aam-1+b也是模m的一个完系．（提示：只需证明任意两个模m不同余即可）

弃九法原理：任一正整数与其十进制表示中各位数字之和对模9同余

（1）用同余的写法证明：平方数除以4余数为0或1；

（2）用同余的写法证明：奇数的平方除以8余1；

（3）试证明不是平方数.

求证：对任意正整数n，

（1）设m为正整数，证明：必有一个正整数是m的倍数，且它的各位数字均为0或1.

（2）从任意m个整数中，必可找到若干个数，它们的和（只有一个加数也行）被m整除.

的各位数字之和为a，a的各位数字之和为b，b的各位数字之和为c，求c.

求证：三个连续整数的平方和不是立方数.

求出所有小于10的正整数m，使得.

已知数列定义如下：，求出所有的正整数n，使得.

已知数列递归定义如下：，求证：数列中没有形如（为正整数）的项.

设正整数x,y,z满足，证明：.

大显身手

证明：数列11,111,1111，…中没有平方数

若质数，且也是质数，证明：是合数

的各位数字之和为a，a的各位数字之和为b，b的各位数字之和为c，求c.

对可以取值1或者-1，证明.

设x,y,z为整数，且满足，证明：

（1）十进制数可被7整除，那么数字x等于多少？（其中有50个连续的8,50个连续的