初中数学竞赛专题培训
数论有它自己的代数，称为同余理论．最先引进同余的概念与记号的是数学王子高斯．先看一个游戏：有
＋1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移1，2或3格，以先到最后一格者为胜．问是先走者胜还是后走者胜？应该怎样走才能取胜？取胜之道是：你只要设法使余下的空格数是4的倍数，以后你的对手若走i格i1，2，3，你走4i格，即每一次交替，共走了4格．最后只剩4个空格时，你的对手就必输无疑了．因此，若
除以4的余数是1，2或3时，那么先走者甲胜；若
除以4的余数是0的话，那么后走者乙胜．在这个游戏里，我们可以看出，有时我们不必去关心一个数是多少，而要关心这个数用m除后的余数是什么．又例如，1999年元旦是星期五，1999年有365天，3657×52＋1，所以2000年的元旦是星期六．这里我们关心的也是余数．这一讲中，我们将介绍同余的概念、性质及一些简单的应用．同余，顾名思义，就是余数相同．定义1给定一个正整数m，如果用m去除a，b所得的余数相同，则称a与b对模m同余，记作a≡bmodm，并读作a同余b，模m．若a与b对模m同余，由定义1，有amq1＋r，bmq2r．所以abmq1q2，即m｜ab．反之，若m｜ab，设amq1＋r1，bmq2＋r2，0≤r1，r2≤m1，则有m｜r1r2．因｜r1r2｜≤m1，故r1r20，即r1＝r2．于是，我们得到同余的另一个等价定义：定义2若a与b是两个整数，并且它们的差ab能被一正整数m整除，那么，就称a与b对模m同余．同余式的写法，使我们联想起等式．其实同余式和代数等式有一些相同的性质，最简单的就是下面的定理1．定理11a≡amodm．2若a≡bmodm，则b≡amodm．
第二十五讲同余式
3若a≡bmodm，b≡cmodm，则a≡cmodm．在代数中，等式可以相加、相减和相乘，同样的规则对同余式也成立．定理2若a≡bmodm，c≡dmodm，则a±c≡b±dmodm，ac≡bdmodm．证由假设得m｜ab，m｜cd，所以m｜a±cb±d，m｜cab＋bcd，即a±c≡b±dmodm，ac≡bdmodm．由此我们还可以得到：若a≡bmodm，k是整数，
是自然数，则a±k≡b±kmodm，ak≡bkmodm，a≡bmodm．对于同余式ac≡bcmodm，我们是否能约去公约数c，得到一个正确的同余式a≡bmodm？在这个问题上，同余式与等式是不同的．例如25≡5mod10，约去5得5≡1mod10．这显然是不正确的．但下面这种情形，相约是可以的．定理3若ac≡bcmodm，且c，m1，则a≡bmodm．证由题设知acbcabcmk．由于m，c1，故m｜r