数论基础

第二讲同余初步（1）
本讲概述
同余是大数学家高斯的一个天才发明，这个符号使得原来难以表述的很多数论问题表述起来简单清晰.利用同余符号，可以方便地处理各种复杂的数字相对于另一数的余数这一类问题.本讲将着重讲述同余的基本性质，并利用这些性质来解决各类同余的典型问题.此外，基于同余，还给出了剩余系与完系的概念.尽管联赛大纲没有明确对这两个概念作要求，但是有了对剩余系的基本认识后对很多问题处理起来会更为方便.
同余的定义：
设m 是一个给定的正整数，如果两个整数a 与b 用m 除所得的余数相同，则称a 与b 对模同余，记作)(mod m b a ≡，否则，就说a 与b 对模m 不同余.（用≡符号上面加一个斜线来表示，类似不等符号）.
显然，(mod ),)|()a b m a km b k Z m a b ≡⇔=+∈⇔-（
；同余的性质非常之多，以下仅列举最常用的一些，
（1）自反性：a≡a(mod m)(a 为任意自然数)
（2）对称性：若a≡b(mod m)，则b≡a(mod m)
（3）传递性：若a≡b(mod m),b≡c(mod m)，则a≡c(mod m)
（4）可加减性：若a≡b(mod m),c≡d(mod m)，则a±c≡b±d(mod m)
（5）可乘性：若a≡b(mod m),c≡d(mod m)，则ac=bd(mod m)
（6）可乘方性：若a≡b(mod m),n∈N+，则an=bn(mod m)
注意：一般地同余没有“可除性”，但是
（7）如果：ac≡bc(mod m)且(c,m)=1，则a≡b(mod m)
如果ac≡bc(mod m),(c,m)=d，则a≡b(mod d m
)
（8）如果a≡b(mod m),a≡b(mod n)且[m,n]=k，则a≡b(mod k)（[m,n]表示m,n 的最小公倍数）
（9）设p∈N+,p≥2，则任何一个p 进制自然数与其数码和(p 进制下各数码之和)对模p-1同余；特别地，p=10时，是我们熟知的“弃九法”的理论依据：
任一正整数与其十进制表示中各位数字之和对模9同余.
利用“弃九法”可以方便地解决很多与数字和相关的问题.
另外，利用同余与各种乘法公式以及二项式定理展开式相结合往往威力更大，但我们这里暂时不涉及.剩余类，完全剩余系（简称完系）和缩系
我们可以将所有的整数按模m 分类．例如：按模2分类，可将所有整数分成两类，模2余1的分成一类，即奇数；模2余0的一类，即偶数．按模3分类，可分成3k,3k+1,3k-1三种类型；等等.
剩余类的定义：设m 为一给定的正整数，则全体整数可以分为m 个集合K0，K1，…，Km-1，这里Kr={x |x∈Z,x≡r(mod m)},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 的一个完系．
欧拉函数的定义：对每个整数m，以
表示0,1,,m-1当中与m 互素的整数个数，即为欧拉函数。

缩同余类的定义：如前定义，若，则是m 的一个缩同余类。

模m 的缩同余类共有个。

在每个缩同余类取一个代表，这个代表组成的集合称为m 的缩代表系，简称缩系。

模素数的完全剩余系和缩系是等价的。

类似的，有以下性质：
性质1．每个与m 互素的整数在且仅在模m 的一个剩余类中．
性质2．若aa1,…，是模m 的一个缩系，而(a,m)=1,则aa1,…,a 也是模m 的一个缩系．例题精讲
【例1】证明：
（1）同余的可除性：如果：ac ≡bc (mod m)且(c,m)=1，则a ≡b(mod m)
（2）弃九法原理：任一正整数与其十进制表示中各位数字之和对模9同余
【例2】用同余的写法证明：（1）平方数除以4余数为0或1；
（2）用同余的写法证明：奇数的平方除以8余1；
（3）试证明19911991115534 不是平方数.
【例3】（1）证：若a 1,…，
是模m 的一个缩系，而(a,m)=1，则aa 1,…,a 也是模m 的一个缩系．
（2）(a,m)=1，若
，称b 是a 关于模m 的逆，记作，是模m 的一个同余类。

证：存在且唯一。

（3）若p 是素数，证明：。

（威尔逊定理）
【例4】设n>3是奇数，证明：将n 元集合任意去掉一个元素后，总可以将剩下的元素分成两组，每组个数，使两组的和模n 同余。

【例5】设n 是偶数，以及是模n 的两个完全剩余系。

证明：
不是模n 的完全剩余系。

【例6】求证：对任意正整数n，8不整除.
【例7】求不能表示成的最小素数p,这里a,b 是非负整数。

【例8】设整数x,y,z 满足
，
证明：x+y+z 被27整除。

【例9】设正整数x,y,z 满足222x y z +=，证明：60|xyz .
【例10】(1)设m 为正整数，证明：必有一个正整数是m 的倍数，且它的各位数字均为0或1.
（2）从任意m 个整数12,,...,m a a a 中，必可找到若干个数，它们的和（只有一个加数也行）被m 整除.
（3）从任意17个整数中，必可找到这样的9个数，他们的和是9的倍数。

一般的，可以证明，从任意2n-1个整数中，可以取出n 个数之和是n 的倍数。

大显身手
练习1：设，(a,m)=1，，求和其中{x}为x 的小数部分。

练习2：设p 是一个奇素数，证明：
（1）
(2)
练习3：例4.连结正n 边形的顶点，得到一个闭的n-折线。

证明，若n 是偶数，则在连线中有两条平行线。

若n 为奇数，则连线中不可能恰有一对平行线。

练习4：19911991的各位数字之和为a ，a 的各位数字之和为b ，b 的各位数字之和为c ，求c.
练习5：（1）n 是整数，则：
(2)考虑质数若.证明：可以在这31个数中找到3个连续的质数。

练习6：求证：三个连续整数的平方和不是立方数.
练习7：已知数列{}n p 定义如下：1234n n n n n p =+++，求出所有的正整数n ，使得5|n p .
练习8：已知数列{}n a 递归定义如下：01210,1,8n n n a a a a a ++===-(0)n ≥，求证：数列{}n a 中没有形如35αβ（,αβ为正整数）的项.
练习9：设整数a,b,c 满足a+b+c=0,记d=.证明：
练习10：100个不大于100的自然数之和等于200，证明可以从中挑出若干数来，他们的和恰为100。

练习11：数1978n 与1978m 的最后三位数相等，试求出正整数n 和m ，使得m ＋n 取最小值，这里n ＞m ≥1．
练习12：若整数a,b,满足“从任意2n-1个整数中，可以取出n 个数之和是n 的倍数”.证明：m=ab 也满足这个命题。

练习13：从任意2n-1个整数中，可以取出n 个数之和是n 的倍数。

练习14：35.对于所有素数p 和所有正整数()n n p ≥，证明：p n n C p ⎡⎤-⎢⎥⎣⎦
能被p 整除.。