【摘要】 具有悠久历史的数学竞赛已逐渐形成一门特殊的数学学科——竞赛数学． 本文从数学竞赛这个大范围入手，着眼于数论在数学竞赛中的地位和作用，选择中国剩余定理作为切入点，介绍了同余理论的系统知识及同余性质的一些简单应用，并对数学竞赛中有关同余理论的应用作了系统的划分． 每一部分都有２ — ４个例题加以举例说明．
【关键词】 同余 同余理论 数学竞赛
一、数学竞赛·数论·同余
数学竞赛是一种有组织的，在规定时间之内进行的解数学题的竞赛，是人类智慧的灵活、力量与完美的较量．
数学竞赛历史悠久，而且在最近１０年有很大的发展和变化． 并且随着数学竞赛的发展，已逐渐形成一门特殊的数学学科——竞赛数学，也可称为奥林匹克数学． 将高等数学下放到初等数学中去，用初等数学的语言来表述高等数学的问题，并用初等数学方法来解决这些问题，这就是竞赛数学的任务． 数论这门学科最初是从研究整数开始的，所以叫做整数论． 后来整数论又进一步发展，就叫做数论了．
近几十年来，初等数论在计算机科学、组合数学、代数编码、信号的数字处理等领域内得到了广泛的应用． 而且初等数论在各类数学竞赛中占有重要的地位． 国际数学奥林匹克（ＩＭＯ）从１９５９年到２００５年中，已经举行了４６届竞赛，在总共的２７８道题目中，约有四分之一的题目是主要用初等数论知识来解的，如果加上涉及用初等数论知识来解的题目，那所占的比例可达到一半左右．
初等数论的主要内容大致可分为四部分：①整除理论，②不定方程，③同余，④原根与指标．
二、同余理论在数学竞赛中的应用
（一） 同余的性质以及几个重要的定理
１． 同余的定义、性质
定义 给定正整数ｍ，如果整数ａ与ｂ 之差能被ｍ整除，则称ａ与ｂ 对于模ｍ同余，或称ａ与ｂ同余，模 为ｍ，记为ａ ≡ ｂ（ｍｏｄ ｍ），
此时也称ｂ是ａ 对模ｍ的同余．
性质
２． 剩余类和完全剩余系
全体整数集合可按模m来分类：当且仅当ａ≡ｂ（ｍｏｄ ｍ）时，ａ和ｂ属于同一类．于是全体整数按模ｍ被分为ｍ类，每一个这样的类被称为模ｍ的剩余类．在 ｍ个剩余类中各取一个数作为代表，这样的ｍ个数被称为模m的完全剩余系．例如０，１，２，…，ｍ － １是模ｍ的一个完全剩余系，称为最小非负完全剩余系．
完全剩余系有下列性质：
定理３、定理４也是同余理论中重要的定理，在求解同余方程的问题中有非常重要的作用，这里虽不做详细的应用介绍，但对于广大参加数学竞赛的学生还是希望能对其加以重视．
（二） 同余理论用于处理有关整除的问题
整除与同余是密切相关的，有些整除问题在解答过程中常常是同余理论的灵活运用．
例１ （第六届奥赛试题）（１）证明：求出所有正数n 使2n-1能被７整除； （２）没有正整数n能让2n + 1 被７整除．
（三） 同余理论用于求解不定方程
对于一次不定方程的存在性的解法已有一套完整的理论来解决，但若将这些方程转化成线性同余式则解题更简捷．
例２ （第23届ＩＭＯ试题） 试证：（１）如果正整数n及方程x3 - 3xy2 + y2 = n有一组整数解（x,y），那么这个方程至少有三组整数解．
综上所述，方程ｘ３ － ３ｘｙ２ ＋ ｙ３ ＝ ２８９１无整数解．
（四）同余理论用于分配问题
例３ 一位魔方制造商把他的产品装在大方盒子（正方体）里运给批发商． 一位批发商从大方盒中取出一行魔方，试验看是否有毛病，但在试验中，这些魔方毁坏了，其余的魔方用小盒包装，每盒装６个，那么装到最后会剩下几个魔方？
分析 此题看似复杂，其实用同余的观点处理却非常简单．设一行有n个魔方，则大方盒中总共装有n3个，做完试验后，大方盒中还有n3 - n个魔方，于是问题转化为求n3 - n ≡ ?(mod 6)．
解 因为n3 - n = n(n - 1)(n + 1)为三个连续自然数之积，所以n3 ≡ 0(mod 6)．
故不论大方盒的大小如何，试验后按６个一小盒装总可以全部装完．
（五）构造剩余系解题
利用完全剩余系常常可以帮助我们巧妙地解答某些试题．
例４ 设自然数n ≤ 2006，试求其中使3n除７的余数为１的所有n的和．
解 由题意，即求满足3n ≡ 1(mod 7)（８）
的所有n的和． 而
例５ （第２３届全俄中学奥林匹克竞赛试题，１１年级）巫士委员会以如下方式接受考核：国王把所有巫士排成一队，然后给每个巫士戴上从白色、蓝色、红色帽子中任意选取的一顶帽子，每个巫士都能够看到站在其前面所有人的帽子颜色，但看不见自己所戴帽子的颜色，也看不到站在他后面的人的帽子颜色．要求每分钟都有巫士报出三种颜色中的一种（允许同时报）．报完之后国王就处死那些将自己所戴帽子颜色判断错了的巫士．在议事举行前，这１００个巫士达成一致：尽量将叛死刑的人数降到最低．问：有多少个巫士一定可以免受惩罚？
解 第一个猜的巫士因为没有任何信息帮助他确定其所戴帽子的颜色，所以不管猜什么颜色，都只是一个随机的猜测，那么就不能担保１００个巫士全部免受惩罚．
但采用如下的办法，可保证９９个巫士免受惩罚．
首先由站在队伍末尾的巫士报出一种颜色，接着由站在他前面的人报，如此继续，最后直到站在首位的巫士报出一种颜色．
分别用三个数字来代表三中颜色：白色为０，蓝色为１，红色为２．最后一个巫士将站在前面的所有巫士的帽子颜色数目相加，再去３去除这个和，并报出余数相应的帽子颜色，记该余数为S1．倒数第二个巫士也将其前方的所有帽子颜色数目相加，用３去除和得一余数，该余数记为r2，那么倒数第二个巫士所戴帽子的颜色数目为 S2 = S1 - r2(mod 3)，从而也能都准确报出自己所戴帽子的颜色，使自己免受惩罚．
令Sn为倒数第n个巫士所报的帽子的颜色数目， rn为倒数第n个巫士将他前方所有的帽子颜色数目相加所得的和用３除之后所得的余数．因而，只要有了递归数列{Sn}，即Ｓｎ ≡ Ｓ１－ Ｓｋ － ｒｎ（ｍｏｄ ３），０ ≤ Ｓｎ ≤ ２，倒数第n（n ＞ 1 ）个巫士就能准确地报出自己所戴帽子的颜色．
以上是同余理论在一些数学竞赛中的有关应用，而鉴于同余理论在数论中的特殊地位，若要灵活地掌握和应用它，还需加强对数论知识的系统、有效的学习． 同余理论在数学竞赛中的应用是相当广泛的，而且不论是《初中数学竞赛大纲》还是《高中数学竞赛大纲》都规定有相应的同余理论的内容，所以广大竞赛学生应该对同余理论加以足够的重视．
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”