浅谈余数问题中的同余特性

华杯赛数论专题：余数及同余一、带余除法的定义：一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q…r，也就是a＝b×q＋r, 0≤r＜b；我们称上面的除法算式为一个带余除法算式.这里：（1）当时：我们称a可以被b整除，记作b|a，q称为a除以b的商或完全商（2）当时：我们称a不可以被b整除，记作，q称为a除以b的商或不完全商二、同余的概念两个整数被同一个大于1的整数m除，所得的余数相同，就说这两个整数对于除数m来说是同余的.也可以换句话来说这个概念，如果两个整数的差能被大于1的整数m整除，那么这两个整数对于除数m来说是同余的.同余的概念和符号都是德国伟大数学家高斯引进的.一般地，两个整数a和b，除以大于1的正整数m，如果所得的余数相同，就说a、b对于模m同余，记作a≡b（mod m）.由于一个整数被m除的余数只能是0、1、2、3、…、m-1这m个数，所以全体整数可按被m除的余数分类，凡是余数相同的归为一类，全体整数就被划分成了m类，同一类中的任何两数被m除的余数都相等，即同一类中任何两数的差都能被m整除，不同类的任何两数被m除的余数都不相等.三、同余的性质1.如果a≡b（mod m），那么m|（a-b）；如果整数a和b对于模m是同余的，那么a 与b的差能被m整除.2.a≡a（mod m），即任何整数都与自身同余.3.若a≡b（mod m），则b≡a（mod m）.4.若a≡b（mod m），b≡c（mod m），则a≡c（mod m）.5.若a≡b（mod m），c≡d（mod m），则a+c≡b+d （mod m），a－c≡b－d （mod m），a×c≡b×d （mod m）.6.若a≡b（mod m），则an≡bn（mod m）。

（其中n为正整数）.例1.用一个两位数除708，余数为43，求这个两位数.【答案】95【解答】根据被除数-余数=商×除数，可知，所求两位数一定是707-43=665的大于43的约数，所以所求的两位数是95.例2.数713、1103、830、947被一个数除所得余数相同（余数不为0），求这个除数.【答案】39，13或3.【解答】1103－713=390=3×13×2×5，947－830=117=3×13×3，1103－947=156=2×13×3×2，除数为39，13或3.例3.从1、2、…100中最多能选出多少个数，使选出的数中每两个的和都不能被3整除？【答案】35【解答】1、2、…100中，除以3余1的数共34个，即1、4、7、10、…、100.除以3余2的数共33个，选出的数中，如果有除以3余1的，就一定不能有除以3余2的；如果有除以3余2的，也就不能有除以3余1的。

六余数和同余1.有余数的除法各部分之间的关系：被除数=除数×商＋余数被除数－余数﹦商×除法2.除法算式的特征:余数＜除数3.有关余数问题的性质：性质1：如果两个整数a,b除以同一个数m，而余数相同，那么a和b的差能被m整除。

性质2：对于同一个除数，如果两个整数同余，那么他们的差就一定能被这个数整除。

性质3：对于同一个除数，如果两个整数同余，那么他们的乘方仍然同余。

解答同余类型题目的关键是灵活运用性质，把求一个比较大的数字除以某数的余数问题转化为求一个较小数除以这个数的余数，使复杂的问题变得简单化。

1.把题目转化为算式就是：□÷7﹦□……□余数要比除数7小，商和余数相同，题中商和余数可能是0、1、2、3、4、5、6，带入原式。

根据被除数﹦商×除法＋余数，算得：0×7＋0﹦0；1×7＋1﹦8；2×7＋2﹦16；3×7＋3﹦24；4×7＋4﹦32；5×7＋5﹦40；6×7＋6﹦48。

所求被除数可能是：0、8、16、24、32、40、48。

一个三位数被37除余17，被36除余3，那么这个三位数是多少？有啥好方法吗？这道题可采取经典的余数处理方法------凑。

这个凑，可不是漫无目的的凑。

而是有理有据才行。

1、找一个最小的自然数，满足除以37余17，当然17即可满足。

2、很显然，这个数除以36并不余3，作适当调整。

3、为了不改变37的那个余数，每次可加上一个37.4、每加一次37，除以36的那个余数就增加1（记住，不要计算被除数是多少，而采取的是余数的性质。

被除数扩大一倍，余数也扩大一倍，被除数增加几，余数也会增加几（或者除以除数的余数））5、因为我们要求的数除以36要余3，现在只是余17，即达到36后再多出3，即余39（注意，这里用的是扩展余数），还差39-17=22.所以要增加22个37.6、结果是17+22×37即为答案。

数论之同余问题余数问题是数论知识板块中另一个内容丰富，题目难度较大的知识体系，也是各大杯赛小升初考试必考的奥数知识点，所以学好本讲对于学生来说非常重要。

许多孩子都接触过余数的有关问题，并有不少孩子说“遇到余数的问题就基本晕菜了！”余数问题主要包括了带余除法的定义，三大余数定理（加法余数定理，乘法余数定理，和同余定理），及中国剩余定理和有关弃九法原理的应用。

知识点拨：一、带余除法的定义及性质：一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q……r，也就是a＝b×q＋r,0≤r＜b；我们称上面的除法算式为一个带余除法算式。

这里：r=时：我们称a可以被b整除，q称为a除以b的商或完全商(1)当0r≠时：我们称a不可以被b整除，q称为a除以b的商或不完全商(2)当0一个完美的带余除法讲解模型:如图，这是一堆书，共有a本，这个a就可以理解为被除数，现在要求按照b本一捆打包，那么b就是除数的角色，经过打包后共打包了c捆，那么这个c就是商，最后还剩余d本，这个d就是余数。

这个图能够让学生清晰的明白带余除法算式中4个量的关系。

并且可以看出余数一定要比除数小。

二、三大余数定理：1.【余数的加法定理】a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。

例如：23，16除以5的余数分别是3和1，所以23+16=39除以5的余数等于4，即两个余数的和3+1.当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。

例如：23，19除以5的余数分别是3和4，故23+19=42除以5的余数等于3+4=7除以5的余数，即2.2.【余数的乘法定理】a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。

例如：23，16除以5的余数分别是3和1，所以23×16除以5的余数等于3×1=3。

当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。

六余数和同余 1.有余数的除法各部分之间的关系：被除数=除数×商＋余数被除数－余数＝商×除法 2.除法算式的特征:余数＜除数 3.有关余数问题的性质：性质1：如果两个整数a,b 除以同一个数m，而余数相同，那么a 和b 的差能被m 整除。

性质2：对于同一个除数，如果两个整数同余，那么他们的差就一定能被这个数整除。

性质3：对于同一个除数，如果两个整数同余，那么他们的乘方仍然同余。

解答同余类型题目的关键是灵活运用性质，把求一个比较大的数字除以某数的余数问题转化为求一个较小数除以这个数的余数，使复杂的问题变得简单化。

1.把题目转化为算式就是：□÷7＝□……□ 余数要比除数7 小，商和余数相同，题中商和余数可能是0、1、2、3、4、5、6，带入原式。

根据被除数＝商×除法＋余数，算得：0×7＋0＝0；1×7＋1＝8；2×7＋2＝16；3×7＋3＝24；4×7＋4＝32；5×7＋5＝40；6×7＋6＝48。

所求被除数可能是：0、8、16、24、32、40、48。

一个三位数被37 除余17，被36 除余3，那么这个三位数是多少？有啥好方法吗？这道题可采取经典的余数处理方法------凑。

这个凑，可不是漫无目的的凑。

而是有理有据才行。

1、找一个最小的自然数，满足除以37 余17，当然17 即可满足。

2、很显然，这个数除以36 并不余3，作适当调整。

3、为了不改变37 的那个余数，每次可加上一个37. 4、每加一次37，除以36 的那个余数就增加1（记住，不要计算被除数是多少，而采取的是余数的性质。

被除数扩大一倍，余数也扩大一倍，被除数增加几，余数也会增加几（或者除以除数的余数））5、因为我们要求的数除以36 要余3，现在只是余17，即达到36 后再多出3，即余39 （注意，这里用的是扩展余数），还差39-17=22.所以要增加22 个37. 6、结果是17+22×37 即为答案。

第三章第十一节同余问题093数教黄欢01号在整数除法运算中，被除数与除数可能是整除关系，也可能不是整除关系。

而许多问题，只需要知道余数。

由此形成了专门研究余数的问题，即同余问题。

一、带余除法的定义如果a，b是两个整数，b>0，那么一定有而且只有两个整数q，r使a=bq+r，（0≤r<b）.我们称r为a除以b的余数，q为a除以b的不完全商。

整数集合是可按余数分类。

一个整数被正整数b除时，余数只有0，1，2，…，b-1这b种情况。

我们把被b除同时都余r (0≤r＜b)的一类数，叫做b的剩余类。

因此，数b的剩余类共有b个。

这样整数就被分成b类。

比如，一个整数被2除时的余数只能是0和1，所以整数可分为两类，即余数为0的偶数，记为2k，余数为1的奇数，记为2k+1，其中k为任意整数。

一个整数被3除时的余数只能是0和1，2，所以整数可分为三类，即被3整除的一类，记为3k，被3除余1的一类，记为3k+1，被3除余2的一类，记为3k+2，其中k取任意整数。

二、同余的概念两个整数a与b除以整数m（m>0），如果余数相同，则称a与b关于模m同余。

并用下面的同余式表示a≡b(mod m).a≡b(mod m) ⇔a=b+km,(k∈N) ⇔m|(a-b).同余的概念和记号都是德国数学家高斯在他的名著《算术研究》（1801年）中引进的，是研究数论的重要工具。

三、同余的性质1.（反身性）a≡a(mod m)；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±b≡c±d(mod m)；5.a+b≡c(mod m)当且仅当a≡c-b(mod m)；6.如果a≡b(mod m),c≡d(mod m),那么ac≡bd(mod m),a n≡b n(mod m),(n为正整数)，ak≡bk(mod m) (k为正整数)。

（十八）余数和同余【知识要点】1、例如：37÷5＝7……2，四者之间的数量关系：被除数=除数×商+余数2、同余的概念：两个整数，被同一个大于1的整数m除，所得余数如果相同，那么，这两个整数对于除数m来说是同余的。

例如：14和26这两个数虽然大小不同，但它们分别除以6所得的余数相同，我们把14和26叫做关于模6同余。

3、同余最基本的性质是：几个同余式（模相同）相加、减、乘、乘方仍然同余。

【典型例题】例1、两个整数相除商8，余16；并且被除数、除数、商及余数的和是463.那么被除数是多少？解：因为：被除数=除数×8+16，并且被除数+除数=463―8―16＝439，所以除数=（439－16）÷（8+1）=47，被除数=47×8＋16=392.例2、被3除余2，被5除余3，被7除余4的最小自然数是多少？解：被3除余2的数有2，5，8，11，…其中8又能被5除余3，并且满足条件最小的，而［3，5］=15，所以8+15=23，23+15=38，38+15=53，53满足了被7除余4这个条件，并且最小。

例3、五（3）班同学上体育课，排成3行少1人，排成4行多3人，排成5行少1人，排成6行多5人，问上体育课的同学最少多少名？解：［3,4,5,6］=60, 60－1=59(人).例4、小刚在一次计算除法时，把被除数171错写成117，结果商少了3而余数恰好相同，这题中的除数是几？解：设除数为m,正确的商位q，余数为r，那么错写被除数后，除数仍为m，商为q－3，余数仍为r。

因为：171=m×q+r117= m×（q－3）+r于是171 －117= （m×q+r）－（m×q－3 m+r）得m=18.【精英班】例5、有一个三位数，其中个位上的数是百位上的数的3倍，且这个三位数除以5余4，除以11余3.这个三位数是多少？解：这个三位数除以5余4，所以它的个位数字是4或9，因为个位数字是百位数字的3倍，所以个位数字只能是9，百位数字是3.因为这个数除以11余3，所以它的十位数字=3+（9－3）=9，这个三位数是399.【竞赛班】例6、11+22+33+44+55+66+77+88+99除以3的余数是多少？解：由数的整除性质和同余性质可推知：（1）3的倍数的任何次方（0除外）除以3的余数为0，可知33+66+99 除以3余0.（2）不是3的倍数的偶次方除以3的余数为0，可知22+44+88除以3余1.（3）11除以3余1，55与25对于3同余，它们除以3余2. 77与17对于3同余，它们除以3余1. 所以（1+2+1）÷3=1……1。

同余的性质及应用1 引言数论的一些基础内容的学习，一方面可以加深对数的性质的了解，更深入的理解某些其他邻近学科，另一方面，可以加强数学训练.而整数论知识是学习数论的基础，其中同余理论有时整数论的重要组成部分，所以学好同余理论是非常重要的.在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数，例如我们问现在是几点钟，就是用24去除某一个总的时数所得的余数；问现在是星期几，就是问用7去除某一个总的天数所得的余数，假如某月2号是星期一，用7去除这月的号数，余数是2的都是星期一.我国古代孙子算经里已经提出了同余式11(mod )xb m ,22(mod )xb m ,…,(mod )k k xb m 这种形式的问题，并且很好地解决了它.宋代大数学家秦九韶在他的《数学九章》中提出了同余式1(mod )i i x M m ≡, 1,2,...,i k =, i m 是k 个两两互质的正整数，12...k m m m m =,i i m m M =的一般解法.同余性质在数论中是基础，许多领域中一些著名的问题及难题都是利用同余理论及一些深刻的数学概念，方法，技巧求解.例如，数论不定方程中的费尔马问题，拉格朗日定理的证明堆垒数论中的华林问题，解析数论中，特征函数基本性质的推导等等.在近现代数论研究中，有关质数分布问题，如除数问题，圆内格点问题，等差级数问题中的质数分布问题，2an bn c ++形式的质数个数问题，质数个数问题，质数增大的快慢问题，孪生质数问题都有一定程度的新成果出现，但仍有许多尚未解决的问题.数论的发展以及现代数学发展中提出的一些数论问题，都要求我们对于近代数论的一些方法和基础知识，必须熟练掌握.所以，本文主要介绍了同余理论中同余基本性质的一些简单应用，通过本文的阐述，希望可以为对数论有兴趣的读者，增加学习数论知识的兴趣，并能为他们攻破那些经典的数论难题开展数论课题课题提供一些帮助.2 同余的概念给定一个正整数m ，把它叫做模，如果用m 去除任意两个整数a 与b 所得的余数相同，我们就说对模m 同余，记作(mod )a b m ≡,如果余数不同，就说对模m 不同余. 由定义得出同余三条性质：（1）(mod )a a m ≡；（2）(mod )a b m ≡,则(mod )b a m ≡；（3）(mod )a b m ≡,(mod )b c m ≡,则(mod )a c m ≡.定义也可描述为:整数a ,b 对模m 同余的充分必要条件是m a b -,即a b mt =+,t 是整数.3 同余的八条基本性质由同余的定义和整数的性质得出[1]：（1）若(mod )a b m ≡,(mod )c d m ≡,则(mod )a c b d m +≡+若(mod )a b c m +≡, 则(mod )a c b m ≡-（2）若(mod )a b m ≡,(mod )c d m ≡, 则(mod )ac bd m ≡ 特别地,若(mod )a b m ≡,则(mod )ak bk m ≡（3）若11......(mod )k k A B m ∂∂∂∂≡, (mod )i i x y m ≡, 0,1,...,i n =则1111...1...1......(mod )k k k k k k A x x B y y m ∂∂∂∂∂∂∂∂≡∑∑（4）若1a a d =, 1b b d =, (,)1d m =, (mod )a b m ≡,则11(mod )a b m ≡（5）若(mod )a b m ≡,0k >, 则(mod )ak bk m ≡；若(mod )a b m ≡, d 是a ,b 及m 任一正公因数,则(mod )a b m d d d≡ （6）若(mod )i a b m ≡,1,2,...,i k =,则12(mod[,,...,])k a b m m m ≡其中12[,,...,]k m m m 是12,,...,k m m m , k 个数最小公倍数（7）若(mod )a b m ≡, d m ,0d >,则(mod )a b d ≡（8）(mod )a b m ≡, (,)(,)a m b m =,若d 能整除m 及a ,b 两数之一,则d 必整除a ,b 另一个.4 同余性质在算术里的应用4.1 检查因数的一些方法 例1 一整数能被3(9)整除的充要条件是它的十进位数码的和能被3(9)整除. 证:按照通常方法,把任意整数a 写成十进位数形式,即1101010...n n n n a a a a --=+++, 010i a ≤<.因101(mod3)≡, 所以由同余基本性质,即3a 当且仅当3i a ∑； 同法可得9a 当且仅当9ia ∑，0,1,...,i n =. 例2 设正整数11010001000...n n n n a a a a --=+++，01000i a ≤<，则7（或11或13）整除a 的充要条件是7（或11或13）整除0213(...)(...)(1)i i a a a a a ++-++=-∑，0,1,...,i n =.证：1000与-1对模7（或11或13）同余，根据同余性质知，a 与(1)i i a -∑对模7（或11或13）同余即7（或11或13）整除a 当且仅当7（或11或13）整除(1)i i a -∑，0,1,...,i n =. 例3 a =5874192，则587419236i a =++++++=∑，0,1,...,i n =能被3，9整 除，当且仅当a 能被3，9整除解：由例1证法可知，该结论正确.例4 a =435693，则43569330i a =+++++=∑，0,1,...,i n =能被3整除，但ia ∑不能被9整除当且仅当3是a 的因数，9不是a 的因数.解：由例1的证法可得.例5 a =637693，则6371000693a =⨯+，69363756i a =-=∑，0,1,...,i n =能被7整除而不能被11或13整除当且仅当7是a 的因数但11，13不是a 的因数. 解：由例2的证法可知，该结论正确.例 6 a =75312289，27510003121000289a =⨯+⨯+2893127552ia =-+=∑，0,1,...,i n =能被13整除，而不能被7，11整除当且仅当13是a 的因数，而7与11不是a 的因数.解：由例2的证法可知.例7 应用检查因数的方法求出下列各数标准分解式① 1535625 ②1158066解：①65432115356251105103105106102105=⨯+⨯+⨯+⨯+⨯+⨯+，153562527i a =++++++=∑，927 ∴91535625，21535625110005351000625=⨯+⨯+，021()625153591a a a +-=+-=，由例2得1391，791，∴71535625，131535625，又51535625，951374095⨯⨯⨯=，15356253754095=， 5375，375755=，2575，∴54153562535137=⨯⨯⨯.②6543111580661101105108106106=⨯+⨯+⨯+⨯+⨯+，11586627i a =+++++=∑，927∴91158066，2115806611000158100066=⨯+⨯+，021()66115891a a a +-=+-=-，由例2得791，13∴71158066，131158066，又21158066，971321638⨯⨯⨯=，11580667071638=，7707， ∴2115806629713101=⨯⨯⨯⨯.4.2 弃九法（验证整数计算结果的方法）我们由普通乘法的运算方法求出整数a ，b 的乘积是P ，并令1101010...n n n n a a a a --=+++，010i a ≤<1101010...n n n n b b b b --=+++，010i b ≤<，1101010...n n n n P c c c --=+++，010i c ≤<，如果()()i j a b ∑∑与k c ∑对模9不同余，那么所求得的乘积是错误的. 特别的，在实际验算中，若i a ，j b ，k c 中有9出现，则可去掉（因90(mod9)≡）. 例1 a =28997，b =39495，按普通计算方法算得a ，b 乘积是P =1145236515， 按照上述弃九法8(mod9)a ≡，3(mod9)b ≡，5(mod9)P ≡.但83⨯与5对模9不同余，所以计算有误.例2 若a =28997，b =39495，P =1145235615，那么P a b =⨯？解：按照上述弃九法，8(mod9)a ≡，3(mod9)b ≡，6(mod9)P ≡.虽然83⨯与6对模9同余，但是由通常乘法计算得到1145236515a b ⨯=， 故P a b =⨯不成立.注：当使用弃九法时，得出的结果虽然是()()i j a b ∑∑(mod9)k c ≡∑也还不能完全肯定原计算是正确的.4.3 同余性质的其他应用例1 求7除5047的余数.解：由147(2)2(mod 7)≡-≡-，2247(2)4(mod 7)≡-≡，5547(2)1(mod 7)≡-≡-，∴50516247(47)47144(mod 7)≡⨯≡⨯≡，即5047除以7余数为4.例2 试证：形如87()k k N +∈的整数不能表为三个平方数之和.证：假定22287(,,)N k a b c a b c Z =+=++∈，则2227(mod8)a b c ++≡，但这不可能.因为对模8而论.每一个整数最小非负余数只能是0，1，2，3，4，5，6，7中的一个数.而200(mod8)≡，211(mod8)≡，224(mod8)≡，231(mod8)≡，240(mod8)≡，251(mod8)≡，264(mod8)≡，271(mod8)≡.因此，任一整数平方对模8必与0，1，4三个数之一同余，而从｛0，1，4｝中任取三个数，其和都不可能与7对模8同余，所以对于任何整数a ，b ，c 都有222a b c ++与7对模8不同余.即形如87()k k N +∈的整数不能表为三个平方数之和.例3 试证：53335333-能被10整除.证：由已知条件有533(mod10)≡，225339(mod10)≡≡，555337(mod10)≡≡，445331(mod10)≡≡，∴5341541553(53)53(3)3133(mod10)≡⨯≡⨯≡⨯≡又333(mod10)≡，223339(mod10)≡≡，553337(mod10)≡≡，443331(mod10)≡≡，∴33484833(33)33(3)3133(mod10)≡⨯≡⨯≡⨯≡∴53335333(mod10)≡，即533310(5333)-也就是说，53335333-能被10整除.例4 设,,a b c N ∈且6()a b c ++，求证：3336()a b c ++证：对模6来说每一个整数的最小非负数余数为0，1，2，3，4，5 300(mod 6)≡，311(mod 6)≡，322(mod 6)≡，333(mod 6)≡，344(mod 6)≡，355(mod 6)≡，即对任何整数k ，3(mod 6)k k ≡∴3(mod 6)a a ≡，3(mod 6)b b ≡，3(mod 6)c c ≡∴333()()(mod 6)a b c a b c ++≡++又()0(mod 6)a b c ++≡∴333()0(mod 6)a b c ++≡故3336()a b c ++例5 若(5,)1n =，证明5n n -能被30整除.证：设n N ∈，(mod6)n k ≡则0,1,2,3,4,5k =由500(mod 6)≡，511(mod 6)≡，522(mod 6)≡，533(mod 6)≡，544(mod 6)≡，555(mod 6)≡，∴5(mod 6)k k ≡即55(mod 6)n k k n ≡≡≡，56()n n -同理可知55()n n -又(5,6)1= ∴530()n n -故5n n -能被30整除.5 同余性质在数论中的应用：求简单同余式的解5.1一次同余式、一次同余式解的概念在代数里面，一个主要问题就是解代数方程.而同余性质在数论中的应用主要体现在同余在方程中的应用，也就是求同余式的解.一次同余式的定义：若用()f x 表示多项式110...n n n n a x a x a --+++，其中i a 是整数，又设m 是一个正整数，则()0(mod )f x m ≡ 叫做模m 的同余式.若n a 与0对m 不同余，则n 叫做()0(mod )f x m ≡的次数.定义：若a 是使()0(mod )f a m ≡成立的一个整数，则(mod )x a m ≡叫做同余式()0(mod )f x m ≡ 的一个解.定理 一次同余式(mod )ax b m ≡,a 与0对模m 不同余,它有解充要条件是(,)a m b .[3]5.2 孙子定理解一次同余式组引例 今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何? 解:设x 是所求物数，则依题意有，2(mod3)x ≡,3(mod5)x ≡,2(mod7)x ≡ 孙子算经里介绍用下列方法求解由表格知，所求物数是23.孙子定理：设1m ,2m ,…,k m 是k 个两两互质的正整数，12...k m m m m =，i i m m M =，1,2,...,i k =,则同余式组11(mod )x b m ≡, 22(mod )x b m ≡,... ,(mod )k k x b m ≡的解是111111222...(mod )k k k x M M b M M b M M b m ≡+++,其中11(mod )i i i M M m ≡, 1,2,...,i k = [4]用表格形式概括如下例1 解同余式组1(mod 5)x b ≡, 2(mod 6)x b ≡，3(mod 7)x b ≡，4(mod11)x b ≡. 解：此时567112310m =⨯⨯⨯=,16711462M =⨯⨯=,25711385M =⨯⨯=，35611330M =⨯⨯=, 4567210M =⨯⨯=.解11(mod )i i i M M m ≡, 1,2,3,4i = 得113M =, 121M =, 131M =, 141M =即12341386385330210(mod 2310)x b b b b ≡+++.例2 韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数？ 解:由题意，有1(mod5)x ≡，5(mod6)x ≡，4(mod7)x ≡，10(mod11)x ≡3462385533042101067312111(mod 2310)x ≡⨯+⨯+⨯+⨯≡≡.5.3 简单高次同余式组()0(mod )i f x m ≡, 1,2,...,i k =及()0(mod )f x p ∂≡ ,p 为质数，0∂>的解数及解法的初步讨论定理1 若1m ,2m ,…, k m 是k 个两两互质的正整数, 12...k m m m m =,则同余式()0(mod )f x m ≡与同余式组()0(mod )i f x m ≡,1,2,...,i k =等价.若用i T 表示()0(mod )i f x m ≡,1,2,...,i k =,对模i m 的解数, T 表示()0(mod )f x m ≡对模m 的解数，则12...k T TT T =.[5] 例1 解同余式()0(mod35)f x ≡，43()289f x x x x =+++.解: 由定理1知()0(mod35)f x ≡与同余式()0(mod5)f x ≡ , ()0(mod 7)f x ≡等价.同余式()0(mod5)f x ≡有两个解，即1,4(mod5)x ≡同余式()0(mod 7)f x ≡有三个解，即3,5,6(mod 7)x ≡即()0(mod35)f x ≡有六个解，即1(mod 5)x b ≡,2(mod 7)x b ≡由孙子定理有，122115(mod 35)x b b ≡+即得()0(mod35)f x ≡的解为31,26,6,24,19,34(mod35)x ≡. 定理2 设1(mod )x x p ≡,即11x x pt =+, 10,1,2,...t =±±是()0(mod )f x p ≡的一解，并且p 不整除1()f x ,( 1()f x 是()f x 的导函数),则11x x pt =+刚好给出()0(mod )f x p ∂≡，p 为质数，0∂>的一解x x p t ∂∂∂=+,0,1,2,...t ∂=±±, 即(mod )x x p ∂∂≡, 其中1(mod )x x p ∂≡.[6]例2 解同余式3262717200(mod30)x x x +++≡.解: 由定理1知()0(mod30)f x ≡与()0(mod 2)f x ≡,()0(mod3)f x ≡,()0(mod5)f x ≡等价.显然，()0(mod 2)f x ≡有两解0,1(mod 2)x ≡()0(mod3)f x ≡有一解2(mod3)x ≡()0(mod5)f x ≡有三解0,1,2(mod5)x ≡同余式()0(mod30)f x ≡有六个解即1(mod 2)x b ≡,2(mod 3)x b ≡,3(mod 5)x b ≡,10,1b =；22b =；30,1,2b = 由孙子定理得12315106(mod30)x b b b ≡++,以1b ,2b ,3b 值分别代入，得()0(mod30)f x ≡全部解为20,2,26,5,11,17(mod30)x ≡.例3 解同余式()0(mod 27)f x ≡，4()74f x x x =++.解: ()0(mod3)f x ≡有一解1(mod3)x ≡，并且3不整除1(1)f ，以113x t =+ 代入()0(mod9)f x ≡得11(1)3(1)0(mod 9)f t f +≡ 但(1)3(mod9)f ≡，1(1)2(mod 9)f ≡即13320(mod 9)t +⨯≡即1210(mod 3)t +≡因此1213t t =+而2213(13)49x t t =++=+是()0(mod9)f x ≡的一解；以249x t =+代入()0(mod 27)f x ≡即12(4)9(4)0(mod 27)f t f +≡,2189200(mod 27)t +⨯≡即2220(mod3)t +≡, 2323t t =+即3349(23)2227x t t =++=+为所求的解.5.4 简单二次同余式2(mod )x a p ∂≡,0∂>,(,)1a p =解的判断二次同余式一般形式为20(mod )ax bx c m ++≡,a 与0对模m 不同余，由上面所学知识，经总结，判断一般二次同余式有解与否问题，一定可以转化为判断形如2(mod )x a p ∂≡,0∂>有解与否问题.先讨论单质数模同余式2(mod )x a p ≡,(,)1a p =有解与否问题若它有解，则a 叫做模p 的平方剩余，若它无解，则a 叫做模p 的平方非剩余.定理1 若(,)1a p =,则a 是模p 的平方剩余的充要条件是121(mod )p ap -≡且有两解；而a 是模p 的平方非剩余充要条件是121(mod )p a p -≡-.[7]()a p是勒让得符号，它是一个对于给定单质数p 定义在一切整数a 上的函数，它的值规定如下:当()1a p=时，a 是模p 的平方剩余； 当()1a p=-时，a 是模p 的平方非剩余； 当（pa ）=0时，p a .[8]讨论质数模同余式2(mod )x a p ∂≡,0∂>,(,)1a p =有解与否问题定理2 2(mod )x a p ∂≡,0∂>,(,)1a p =有解的充要条件是()1a p=，并且在有解情况下，解数是2.[9]讨论合数模同余式2(mod 2)x a ∂≡,0∂>,(2,)1a =有解与否问题定理3 设1∂>,当2∂=,1(mod 4)a ≡时，2(mod 2)x a ∂≡,0∂>,(2,)1a =有解，且解数是2；当3∂≥，1(mod8)a ≡时，上式有解，解数是4.[10]例 解257(mod 64)x ≡.解: 因571(mod8)≡故有4个解.把x 写成3(14)x t =±+代入原同余式,得到23(14)57(mod16)t +≡, 由此得 31(mod 2)t ≡, 故44[14(12)](58)x t t =±++=±+是适合257(mod16)x ≡的一切整数，再代入原同余式得到24(58)57(mod 32)t +≡, 由此得40(mod 2)t ≡, 故55(582)(516)x t t =±+⨯=±+是适合257(mod 32)x ≡的一切整数,再代入原同余式得到25(516)57(mod 64)t +≡, 由此得51(mod 2)t ≡, 故66[516(12)](2132)x t t =±++=±+是适合257(mod 64)x ≡的一切整数，因此21,53,21,53(mod64)x ≡--是所求四个解.6 结论本文从同余概念及其基本性质出发，通过实例概括总结出同余性质在算术及数论中的一些简单应用.同余性质在算术中的应用主要是通过检查因数和弃九法验算结果的实例作出阐述;数论中同余性质的应用主要体现在简单一次同余式组及高次同余式的求解,以及二次同余式是否有解的判断.参考文献[1]闵嗣鹤,严士健编. 初等数论(第二版)[M].北京:高等教育出版社,1982.9:37-93.[2]余元希等.初等代数研究(上)[M].北京:高等教育出版社,1988:53-82.[3]赵振成.中学数学教材教法(修订版)[M].上海:华东师范大学出版社,1999.12:53-56.[4]王书琴，刘晓卫.剩余定理及一次同余式组[J].哈尔滨师范大学自然科学学报,2002-1-17.[5][法]C.布尔勒，朱广才译. 代数[M].上海:上海科技出版社,1984.3:72-121.[6]曹才翰，沈伯英. 初等代数教程[M].北京:北京师范大学出版社,1987:76-85.[7]刘合义.谈数论中的同余及其应用[J].衡水学院学报,2007:2-6.[8]H.B.勃罗斯库列亚柯夫，吴品三译. 数与多项式[M].北京:高等教育出版社,1980:42.[9]林国泰,司徒永显. 初等代数研究教程[M].广州:暨南大学出版社,1996:81-96.[10]林六十. 初等代数研究[M].北京:中国地质大学出版社,1989:145-158.致谢在大学的生活和学习中, 一直得到应用数学系领导和老师们的关心和帮助, 是在他们的谆谆教导下, 我在专业知识的学习中打下了坚实的基础, 在个人修养方面我从他们身上看到了“学高为师、身正为范”的教师风范, 吸取了踏实、严谨、刻苦、认真的治学精神, 以及正直、诚实、守信的人格魅力, 并且在日常生活中身体力行, 以他们为榜样, 加强教师道德修养, 努力丰富自己、完善自己.我在大学期间取得的所有成绩都是和系领导以及老师们的帮助和教诲分不开的, 在此向他们致以衷心的感谢和良好的祝愿.在这学期撰写毕业论文的过程中, 得到了孙善辉老师的悉心指导, 熟悉了撰写论文的一般格式和许多注意事项, 这对于我以后的学习和生活都具有很好的示范作用. 感谢孙善辉老师的帮助和指导！在我论文的撰写和校对过程中, 还得到了许多同学的帮助, 是他们帮助我发现论文里的某些小小的错误, 这使我节省了时间去完成其他的工作, 在此向他们表示感谢.最后, 再次感谢孙善辉老师的辛勤指导！。

余数性质及同余定理知识框架一、余除法的定及性1.定：一般地，若是 a 是整数， b 是整数（ b≠0） ,若有 a÷b=q⋯⋯ r ，也就是 a＝b×q＋ r ,0≤r＜ b；我称上面的除法算式一个余除法算式。

里：(1)当 r 0 ：我称 a 可以被 b 整除， q 称 a 除以 b 的商或完好商(2)当 r 0 ：我称 a 不可以被 b 整除， q 称 a 除以 b 的商或不完好商一个圆满的余除法解模型 : 如是一堆，共有 a 本，个 a 就可以理解被除数，在要求依照 b 本一捆打包，那么 b 就是除数的角色，打包后共打包了 c 捆，那么个 c 就是商，最后节余 d 本，个 d 就是余数。

个能学生清楚的理解余除法算式中 4 个量的关系。

并且可以看出余数必然要比除数小。

2.余数的性⑴ 被除数除数商余数；除数（被除数余数）商；商（被除数余数）除数；⑵ 余数小于除数．二、余数定理：1.余数的加法定理a 与b 的和除以c 的余数，等于a,b 分除以 c 的余数之和，或个和除以 c 的余数。

比方： 23，16 除以 5 的余数分是 3 和 1，所以 23+16＝ 39 除以 5 的余数等于4，即两个余数的和3+1.当余数的和比除数大，所求的余数等于余数之和再除以 c 的余数。

比方： 23，19 除以 5 的余数分是 3 和 4，所以 23+19＝ 42 除以 5 的余数等于3+4=7 除以 5 的余数22.余数的加法定理a 与b 的差除以c 的余数，等于a,b 分除以 c 的余数之差。

比方： 23， 16 除以 5 的余数分是 3 和 1，所以 23－ 16＝7 除以 5 的余数等于2，两个余数差3－ 1＝2.当余数的差不减，上除数再减。

比方： 23，14 除以 5 的余数分是 3 和 4， 23－ 14＝ 9 除以 5 的余数等于4，两个余数差3＋ 5－4＝ 43.余数的乘法定理a 与b 的乘除以c 的余数，等于a,b 分除以 c 的余数的，也许个除以 c 所得的余数。

数论---同余问题余数问题是我们数论知识非常重要的一大板块，许多名校小升初考试中，各大杯赛中经常会考到，所以序号本讲内容堆学生来讲是非常重要的。

定理1：几个数相加，如果存在一个加数，不能被数a整除，那么它们的和，就不能被整数a整除。

如：35除以5,7余0，除以3余2；63除以3,7余0，除以5余3；30除以3,5余0，除以7余2。

则35+63+30除以3余2，除以5余3，除以7余2。

定理2：两数不能整除，若除数扩大（或缩小）了几倍，而被除数不变，则其商和余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。

一、带余除法的定义及性质：一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q……r，也就是a＝b×q＋r,0≤r＜b；我们称上面的除法算式为一个带余除法算式。

这里：r=时：我们称a可以被b整除，q称为a除以b的商或完全商(1)当0r≠时：我们称a不可以被b整除，q称为a除以b的商或不完全商(2)当0一个完美的带余除法讲解模型:如图，这是一堆书，共有a本，这个a就可以理解为被除数，现在要求按照b本一捆打包，那么b就是除数的角色，经过打包后共打包了c捆，那么这个c就是商，最后还剩余d本，这个d就是余数。

这个图能够让学生清晰的明白带余除法算式中4个量的关系。

并且可以看出余数一定要比除数小。

二、三大余数定理：1.余数的加法定理a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。

例如：23，16除以5的余数分别是3和1，所以23+16=39除以5的余数等于4，即两个余数的和3+1.当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。

例如：23，19除以5的余数分别是3和4，故23+19=42除以5的余数等于3+4=7除以5的余数，即2.2.余数的乘法定理a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。

例如：23，16除以5的余数分别是3和1，所以23×16除以5的余数等于3×1=3。