高中数学讲义：初等数论 同余

高中数学讲义：初等数论同余

目录

1.本讲概述....................................................................1

1.1.同余的定义：............................................................1

1.2.剩余类与完全剩余系(简称完系).........................................1

2.例题精讲....................................................................2

3.大显身手....................................................................3

1.本讲概述

同余是大数学家高斯的一个天才发明，这个符号使得原来难以表述的很多数

论问题表述起来简单清晰.利用同余符号，可以方便地处理各种复杂的数字相对

于另一数的余数这一类问题.本讲将着重讲述同余的基本性质，并利用这些性质

来解决各类同余的典型问题.此外，基于同余，还给出了剩余系与完系的概念.

尽管联赛大纲没有明确对这两个概念作要求，但是有了对剩余系的基本认识后

对很多问题处理起来会更为方便.

1.1.同余的定义：

设m是一个给定的正整数，如果两个整数a与b用m除所得的余数相同，

则称a与b对模同余，记作。三。(modm),否则，就说a与b对模m不同余.

(用三符号上面加一个斜线来表示，类似不等符号).

显然，a=£>(modin)a=km+b,CkZ)m\(a-b)；

1.2.剩余类与完全剩余系(简称完系)

我们可以将所有的整数按模m分类.例如：按模2分类，可将所有整数分

成两类，模2余1的分成一类，即奇数；模2余0的一类，即偶数.按模3分

类，可分成3k,3k+l,3k-l三种类型;等等.

剩余类的定义:设m为一给定的正整数,则全体整数可以分为m个集合Ko,

K1,…，Km-1,这里K产{x|xKZ,x-r(modm)},r=0,1,…，m-1.我们称Ko,Ki,…,

Km-1为模m的剩余类.

在模m的m个剩余类中分别取一个数，共取出m个，我们把这m个数成

第1页共4页

为模m的一组完全剩余系，简称完系.例如：0,1,2,就是一组完系，显然，

它们两两对模m不同余.

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

性质2.若ao,ai,…，am-i是模m的一个完系,而(a,m)=l,bez,则aao+b,

aai+b,…,aam-i+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),贝Ua土c三b土d(modm)

(5)可乘性：若a三b(modm),c三d(modm),贝Uac=bd(modm)

(6)可乘方性:若a三b(modm),n£N+,则an=bn(modm)

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

(7)如果：ac三bc(modm)且(c,m)=l,则a三b(modm)

如果ac=bc(modm),(c,m)=d,贝ija=b(mod—)

d

(8)如果a三b(modm),a三b(modn)且[m,n]=k,贝Ia三b(modk)([m,n]表

示m,n的最小公倍数)

(9)设pdN+,p22,则任何一个p进制自然数与其数码和(p进制下各数

码之和)对模p-1同余；特别地，p=10时，是我们熟知的“弃九法”的理论依据：

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

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

另外，利用同余与各种乘法公式以及二项式定理展开式相结合往往威力更大,

但我们这里暂时不涉及.

2.例题精讲

【例1】证明上述理论部分中的部分性质：

i.同余的可除性:如果:ac=bc(modm)K(c,m)=l,则a三b(modm)

第2页共4页

ii.证明若ao,ai,…，am-i是模m的一个完系，而(a,m)=l,b6Z,则aao+b,

aai+b,…,aam-i+b也是模m的一个完系.(提示：只需证明任意两

个模m不同余即可)

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

余

【例2】(1)用同余的写法证明：平方数除以4余数为0或1；

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

(3)试证明1155网+34网不是平方数.

【例3】求证：对任意正整数n,8?"+217"

【例4】(1)设m为正整数，证明：必有一个正整数是m的倍数，且它的各位

数字均为0或1.

(2)从任意m个整数中，必可找到若干个数，它们的和(只

有一个加数也行)被m整除.

【例5】199r的各位数字之和为a,a的各位数字之和为b,b的各位数字之和

为c,求c.

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

【例7】求出所有小于10的正整数m,使得511989"'+加989.

【例8】已知数列｛p,J定义如下：z=l"+2"+3"+4",求出所有的正整数n,使

得5Ip”.

【例9】已知数列｛4｝递归定义如下：4=0,4=1,an+2=8an+l-an(n>0),求证：

数列｛%｝中没有形如3a5〃(％夕为正整数)的项.

【例10】设正整数X,y,Z满足f+y2=Z?,证明：60|孙z.

3.大显身手

1.证明：数列11,ill,1111,…中没有平方数

2.若质数且2p+l也是质数，证明：4p+l是合数

3.3000的各位数字之和为a,a的各位数字之和为b,b的各位数字之和为

第3页共4页

C,求c.

1990

4.对，=1,2,3,…,1990,不可以取值1或者・1,证明Z乜工。・

2=1

5.设x,y,z为整数，且满足(x-y)(y-z)(z-x)=A：+y+z,证明：

271x+y+z

6.(1)十进制数88...8妁9...9可被7整除，那么数字x等于多少?(其中

有50个