带余除法
设a和b是两个整数，b?0，则存在惟一的一对整数q和r，满足：
a?qb?r， （Ⅰ）
这里r称为a除以b所得的余数，并且
0?r?b （Ⅱ）
当r?0时，N和a是整除关系，当r?0时，(I)是带余数除法，简称为带余除法，N是被除数，a是除数，q称为不完全商，或简称为商. 例如：23?4?5?3中，23是被除数，5是除数，商是4，余数是3.
带余除法给出了4个整数a,b,q,r，或者讲给出了被除数、除数、商和余数的两个关系：一个是等式（Ⅰ），另一个是不等式（Ⅱ）. 对于带余数除法，只要知道了除数、除数、商和余数四个量中的三个，就可以求出第四个.
在带余除法中，当特别关注余数时，如果除数是2，余数就有2种情况：余数是0和余数是1，整数就可以分为两类：奇数和偶数. 如果除数是一个整数m，用m除一个整数，余数是0，1，2，?，m?1中的某个，整数就可以依照余数分为m类，余数是0的整数是第0类，余数是1的整数是第一类，?，余数是m－1的整数是第m－1类，这时，除数称为模数，余数相同的类称为同余类. 例如：当模数m＝3时，可以将整数分为3k、3k+1和3k+2（k是整数）3个同余类.
当除数m固定之后，在同一类中的整数称为关于模数m的同余数，或者直接称为同余数. 如果a和b是同余数，模数是m，我们用符号
a?b?modm?
表达它们同余的性质，并且将这个表达式称为同余式. 例如：当m＝3时，7、 13、22等是同余类，3是模数，可以表达为：
7?13?22?mod3?.
当模数m不变时，同余数可以做加减和乘法运算，并且有一些简单和重要
的性质，例如：
① 若ma?b，则a?b?modm?，若a?bmodm，则ma?b； ② 若a1?b1?modm?,③ 若a1?b1?modm?,a2?b2?modm?，则 a1?b1?a2?b2?modm?； a2?b2?modm?，则 a1b1?a2b2?modm?.
解方程有个重要的概念，就是在什么范围内求方程的解，范围越大，存在解的可能性就越大，但求解也越困难，如同找人一样，在一间教室找某个人很容易，但在“茫茫大千世界”中找某个人就非常困难.
如果我们是在整数中求方程的解，这类方程称为整数方程. 如果整数方程比较简单，可以用“枚举法”求解，一般一点的方法就是利用同余的性质，逐步简化方程，最后求出方程的解. 例如：求方程7x?3y?100得整数解，利用同余式来求解：对整数方程
7x?3y?100 （*）
计算等号两端关于3的余数，左端因为3y能被3整除，余数为0，7被3除的余数是1，所以左端的余数是1?x?0?x；右端100被3除的余数是1，所以，我们就有：
x?1?mod3?，
或者x?1?3k，并且将x?1?3k代入整数方程7x?3y?100，得到
7?1?7?3k?3y?100，解出y?31?7k.
分类和将问题简单化是数学的基本的思想，同余类可以使许多数学问题简化，使解答过程比较简单，是数学竞赛中常见到的题目类型. 理解同余数既不复杂，又很实用，作为课外知识，学一点有益无害.
m个自然数除以m恰有m个不同的余数，这m个自然数称为模m的完全剩余系。
例1. 一个正方体，每条棱上可以标记上1个1到12的整数，要求每条棱上的整数都不同. 在每个顶点处，相邻有3个整数，这3个整数可以依大到小
A 2 7 1 图3-4 排列出一个新的整数. 例如：图3-4点顶点A处，排列出的整数是721. 问能否有一种标记的方式，使得到的8个整数都能被3整除.
分析和解答：可以. 将1到12按模数3分为三个同余类，分别记为0、1、2. 此时在正方体的12条棱上标记4个0、4个1和4个2，如图3-4a标记这些同余数. 因为在每个顶点都相邻有0、1和2，他们所代表的整数的数字和一定能被3整除. 所以，按图4-9，用同余于零的数替换0、用同余于1的整数替换1、用同余于2的整数替换2，这样所得到的8个整数都能被3整除.
例2. 求72007的个位和十位数字？
分析和解答：求72007的十位和个位就是计算被100除的余数，
2 2 1 图3-4a 0 0 1 2 1 0 72007?73?(74)501?343?[(50?1)2]501?43?1?43(mod100).
例3.小明的妈妈买了若干袋果脯，有葡萄、苹果、雪梨和芒果4种，每种都至少买了1袋，一共化了34元. 已知葡萄、苹果、雪梨和芒果果脯每袋的单价分别是1.4元、2.2元、2.8元和4.2元，小明的妈妈至少买了多少袋果脯，其中苹果果脯有多少袋？
列出算式：
14x?22y?28z?42w?340，①
x,y,z,w分别是小明的妈妈买葡萄、苹果、雪梨和芒果4种水果的袋数. 上式两
边除7，
y?4?Mod7?.
小明的妈妈买了4袋苹果. 将y?4代入①式，得到：
14x?28z?42w?252,x?2z?3w?8.
上面第2个方程，试解的方法可以得到解是：x?1,z?2,w?1,或x?3,z?1,w?1.
所以，小明的妈妈买了4袋苹果果脯，至少买了8袋果脯.
答：小明的妈妈买了4袋苹果果脯，至少买了8袋果脯. 例4. 数.
分析和解答：因为
P?25?Q??2?1???2?2???2?3?????2?17?555555555555设Q?15?25?35???175，问：17除Q的余
??2?4?6???14?16???18?20???34其中，17除?185?205???345?和17除?15?35???155??17?的余数相同.
5，
进而，17除Q和17除P的余数相同. 所以17整除P?Q??25?1?Q?31Q. 既然17和31互质，17就整除Q.
例5． 21能整除22006?17吗？
分析和解答：如果3和7能整除22006?17，21就能整除22006?17.因为
22006?41003??3?1?1003，
22006被3除的余数是1，17被3除的余数是2，所以，3整除22006?17. 因
为
22006?8668?22??7?1?668?4，
22006被7除的余数是4，17被7除的余数是3，所以，7整除22006?17.
例6． 已知
2008个2007?????????a?20072007?2007
问：除以13所得的余数是几？
分析和解答：直接计算，13不能整除2007贺20072007，但是13能整除200720072007.
2008个2007?????????a?20072007?2007?200720072007?102004?4?200720072007?102001?4???200720072007?1000?2007,
