第五讲初等数论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同余.利用“弃九法”可以方便地解决很多与...
