福建省厦门第一中学人教版高一全国数学联赛班秋季讲义：第五讲 初等数论2 同余

第五讲 初等数论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）如果：