网络自招之同余--鲁力老师

13903及14589时能剩下相同余数的最大整数是
因为13903 13511 392,14589 13903 686,
由于13511,13903,14589要被同一个数除时,
余数相同，那么，它们两两之差必能被同一个数整 除.（392,686） 98，所以所求的最大整数是98.
（2003年南京市少年数学智力冬令营试题）22003与
定理，我们可以得到：这个数一定能整除这三个数
【解析】我们知道18,33的最小公倍数为[18,33]=198,
所以每198个数一次.
1〜198之间只有1,2,3，…，17,198（余0）
这18个数除以18及33所得的余数相同，
而999±198=5…•…9,所以共有5X18+9=99个
这样的数.
【巩固】（2008年仁华考题）一个三位数除以17和19都有余 数，并且除以17后所得的商与余数的和等于它除 以19后所得到的商与余数的和.那么这样的三位 数中最大数是多少，最小数是多少？
1998,2000,2003
2000,2003,2001,1995,1998,2000,2003,2001,1995.
［例4】（2005年全国小学数学奥林匹克试题）有一个整
数，用它去除70，110，160所得到的3个余数之
和是50,那么这个整数是.
【解析】（70 110 160） 50 290,50 316……2,除数应当是290的大于
【解析】设这个三位数为s'它除以17和19的商分别为a和b，余数分别为m和n,则s 17a m 19b n.
根据题意可知a m b n,所以s am s b n，即16a 18b,得8a 9..所以a是9的倍数，b是8的倍数.此时,
由于s为三位数，最小为100,最大为999，所以

下面我们定义同余类的加法以及乘法，并揭示出其可能
的带式结构。
定义2.1.4 设a，b为模m的同余类，定义加法（“⊕”）为
a b a1 b1，其中 a1 a, b1 b ；
定义乘法（“”）为
d 1 2 4 5 10 20
a : ( a ,20)=d 1 ，3 ，7 ，9 ，11 ，13，17，19 2 ，6 ，14，18 4 ，8 ，12，16 5 ，15 10 20
定义2.1.3 n个整数 a1 , a2 , , an 叫作模n 的完全剩余系（简称 完系），是指 a1 , a2 , , an 彼此模 n 不同余。
1 1 10 10 1(mod11) × ≡×≡ ，
这意味着 1, 1 0 模11 的逆元均为本身；而 26× ≡ 34× ≡ 59× ≡ 78 1 × ≡ (mod11) ， 即 2, 3, 4, 5, 6, 7,8, 9 分成 11 3 4 2
−
= 对：2 和6 ，3 和4 ，5 和9 ，7 和8 ，
我们把形如ax =xa ≡ 1(mod m)的整数称为a模m的逆元 （简称a的逆）。
推广的Euclid算法
定理2.1.4` 设 m N ，若(a, m)=1，则a在模m的意义下 存在唯一的逆元； 若(a, m) ≠ 1，则a没有模m的逆元。
前述的性质并不十分困难，但却是重要的。我们可以 举出如下的例证： 整系数多项式同余方程 an xn a1x a0 0 mod m 是 同余理论中的一个核心课题，从前述的基本性质中，我们 至少可以推知以下的认识： (1)若 x0 为 f x 0 mod m 的解，则 y x0 mod m ，都 有 f y 0 mod m ，也就是整系数多项式同余方程的解数 是模的意义下的； (2) 一 次 同 余 方 程 ax ≡ b(mod m) ， 在 (a, m)=1 时 的 解 1 a 为 b mod m ，此时解数在模m的意义下为1； n (3)若 m, an 1，则an x a1x a0 0 mod m xn an1an1xn1 an1a1x an1a0 0 mod m 与 是同解方程； f x 0 mod ml 的解必为 f x 0 mod m 的解， (4)若 l N ， 这就为探讨解的结构提供了一种可能性。

第三章第十一节同余问题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）第⼆讲同余式（1）教师：李艳俊联系⽅式：138********本讲内容同余的定义⼀同余的定义中国剩余定理⼆中国剩余定理剩余类环三剩余类环例：解同余式组≡≡≡≡)11(mod 6)7(mod 5)5(mod 4)3(mod 2x x x x 11,7,5,34321====m m m m 753,1153,1173,11754321??=??=??=??=M M M M 13mod )212(3mod 1111=??==′??M M 15mod )123(5mod 1122=??==′??M M 27mod 47mod )453(7mod 11133==??==′M M 211mod 611mod )753(11mod 11144==??==′M M )1155(mod 62)753(52)1153(41)1173(21)1175(+++≡x )1155(mod 113912601650924770≡+++≡x定义1 每⼀个这样的集合称为模m 的同余类或剩余类，⼀个剩余类中的任意⼀个元素叫做该类中的代表元或剩余。

⼀组数称为是模m 的完全剩余系，记为Z m 。

如果对于任意的整数a 有且仅有⼀个整数与a 在同⼀个剩余类中。

12,,,m a a a ?a C 对于模m 的⼀个完全剩余系，就是模m 的m 个两两不同的剩余类，且有12,,,m a a a ?m a a a C C C ,,,21?∪mi a iC 1==Ζ根据同余的概念，可以将集合Z 分成m 个两两互不相交的集合，且同⼀个集合中的任意两个整数对模m ⼀定同余，⽽属于不同集合中的两个整数对模m ⼀定不同余。

对任意⼀个整数a ，令{:}[]a C a km k a =+∈Ζ=三、剩余系1,2, 1,2,……，m 为模m 的最⼩正完全剩余系；定义2 ⼀般地，0,1,2,0,1,2,……，m -1称为模m 的最⼩⾮负完全剩余系；当m 为偶数时 ,-m /2,/2,……,-1,0,1,-1,0,1…… ,(m -2)/2或 ,(-m -2)/2,-2)/2,……,-1, 0,10,1…… ,m /2为模的绝对值最⼩完全剩余系。