清北学堂 高中数学--数论同余问题选讲导学

华杯赛数论专题：余数及同余一、带余除法的定义：一般地，如果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的。

同余的概念-人教A版选修4-6 初等数论初步教案一、教学目标1.了解同余的概念。

2.掌握同余运算的性质。

3.能够使用同余运算的性质解决初等数论问题。

二、教学重点1.同余的概念。

2.同余运算的性质。

三、教学难点1.应用同余运算的性质解决初等数论问题。

四、教学内容及进度安排课时教学内容学时第一课时同余的概念1学时第二课时同余运算的性质1学时第三课时应用同余运算的性质解决初等数论问题1学时五、教学步骤第一课时-同余的概念1.引入：回顾模运算的概念、性质及应用。

2.学习：同余的概念及其表示法，同余数的概念。

3.总结：总结同余的概念及其表示法。

第二课时-同余运算的性质1.引入：引入同余运算的性质及其证明方法。

2.学习：同余运算的基本性质，同余运算的逆元及其应用。

3.总结：总结同余运算的性质及其应用。

第三课时-应用同余运算的性质解决初等数论问题1.引入：引入应用同余运算的性质解决初等数论问题的方法。

2.学习：应用同余运算的性质解决初等数论问题的例子。

3.总结：总结应用同余运算的性质解决初等数论问题的方法。

六、教学评估1.在课堂上布置练习题，检查学生对同余运算的掌握情况。

2.布置一道探究题，让学生归纳总结同余运算的性质和应用。

3.综合考虑学生的平时表现、作业和考试情况，评估其对同余运算的掌握情况。

七、拓展阅读1.同余式及其应用2.解一元高次同余方程八、参考资料1.《数学（高中必修）》人教版下册2.《初等数论》程开甲著。

兰州成功私立中学高中奥数辅导资料（内部资料）§27 同余1．设m 是一个给定的正整数，如果两个整数a 与b 用m 除所得的余数相同，则称a 与b 对模同余，记作 a ≡b(mod m) ，否则，就说a 与b 对模m 不同余，记作a ≡b(mod m)，显然，a ≡b(mod m) ⇔a =km +b,(k ∈Z ) ⇔m | (a -b) ；每一个整数a 恰与1，2，……，m，这m 个数中的某一个同余；2.同余的性质：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).若a1 ≡b1 (mod m) ，a2 ≡b2 (mod m) ，则 a1 ±a2 ≡b1 ±b2 (mod m)特别是a ≡b(mod m) ⇔a ±k ≡b ±k (mod m) ；5).若a1 ≡b1 (mod m) ，a2 ≡b2 (mod m) ，则 a1a2 ≡b1b2 (mod m) ；特别是 a ≡b(mod m), k ∈Z ⇔则ak ≡bk (mod m)a ≡b(mod m), n ∈N ⇔则a n≡b n(mod m) ；6).a(b +c) ≡ab +ac(mod m) ；7).若ac ≡bc(mod m),则当(c, m) = 1时，a ≡b(mod m)当(c, m) =d时，a ≡8).若a ≡b(mod m1 ) ，a ≡b(mod m2 )a ≡b(mod m3) b(modm)..特别地，ac ≡bc(mod mc) ⇔a ≡b(mod m) ；d………………a ≡b(mod mn ) ，且M = [m1, m2,⋯⋯mn]，则a ≡b(mod M )1 例题讲解1. 证明：完全平方数模 4 同余于 0 或 1；2．证明对于任何整数 k ≥ 0 , 26k +1 + 36k +1 + 56k + 1 能被 7 整除；3．试判断197126 + 197227 + 197328 能被 3 整除吗？4．能否把 1，2，……，1980 这 1980 个数分成四组，令每组数之和为 S 1，S 2，S 3，S 4 ， 且满足 S 2 - S 1，＝10，S 3 - S 2＝10，S 4 - S 3＝105．在已知数列 1，4，8，10，16，19，21，25，30，43 中，相邻若干数之和，能被 11 整除的数组共有多少组。

数学奥赛辅导 第三讲 同余知识、方法、技能同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本讲介绍同余的基本概念，剩余类和完全剩余系，同余方程，整数模的阶和中国剩余定理.Ⅰ.基本概念定义一：设m 是一个给定的正整数.如果两个整数a 、b 用m 除所得的余数相同，则称a 、b 对模m 同余，记为a ≡b （modm ）；否则，记为a ≡b （modm ）.例如，15≡7（mod4），－23≡12（mod7）. 同余有如下两种等价定义法：定义一* 若m|a －b ，则称a 、b 对模m 同余.定义一**若a =b+mt(t ∈Z)，则称a 、b 对模m 同余. 同余的基本性质：（1）.|)(mod 0a m m a ⇔≡ （2）))((mod 反身性m a a ≡))((mod )(mod )(mod ))((mod )(mod 传递性对称性m c a m c b m b a m a b m b a ≡⇔⎭⎬⎫≡≡≡⇔≡（3）若则),(mod ),(mod m d c m b a ≡≡ ①);(mod m d b c a ±≡± ②).(mod m bd ac ≡（4）若).(mod ,.,,2,1,0),(mod 0101m b x b x b a x a x a n i m b a n n n n i i +++=+++=≡ 则特别地，设)(mod ),()(01m b a Z a a x a x a x f i n n ≡∈+++=若 ，则).)(mod ()(m b f a f ≡（5）若).),((mod),(mod c m mb a m bc ac ≡≡则特别地，又若（c,m ）=1，则).(mod m b a ≡ 【证明】因),(|b a c m -这等价于).(),(|),(b a c m cc m m -又因若（a ,b ）=),(d b d a d ⇒=1（d≠0）及b|a c ，且（b,c ）=1,|a b ⇒从而有).(|),(b a c m m- 这个性质说明同余式两边的同一非零因数，不能像等式那样“约去”，只有当这非零因数与模互质时，才可“约去”.（6）),(mod m b a ≡而).(mod ),0(|d b a d m d ≡>则 （7）设),(mod m b a ≡ ①若c>0，则);(mod mc bc ac ≡ ②d 为a 、b 、m 的任一公约数，则).(mod dm d b d a ≡ （8）若).(mod ,1),()(mod ),(mod 212121m m b a m m m b a m b a ≡=≡≡则且 （9）若).,(),(),(mod m b m a m b a =≡则Ⅱ.剩余类和完全剩余系若按对某一模m 的余数进行分类，就可以引入所谓的剩余类和完全剩余系的概念.定义二：设m ∈N*，把全体整数按其对模m 的余数r （0≢r ≢m －1）归于一类，记为k r ，每一类k r （r=0,1,…,m －1）均称模m 的剩余类（又叫同余类）.同一类中任一数称为该类中另一数的剩余.剩余类k r 是数集{}{})(mod |,,,|m r a Z a a k Z q r m r qm k r r ≡∈=∈+=且也即是余数是模,它是一个公差为m 的（双边无穷）等差数列.根据定义，剩余类具有如下性质：（1）);(,1210j i k k k k k k Z j i m ≠=⋂⋃⋃⋃=-φ而 （2）对任一数n ∈Z ，有惟一的00r k n r ∈使； （3）对任意的a ,b ∈Z ，a ,b ).(mod m b a k r ≡⇔∈定义三：设110,,,-m k k k 是模m 的（全部）剩余类.从每个k r 中任取一个数a r ,这m 个数110,,,-m a a a 组成的一个组称为模m 的一个完全剩余系，简称完系.例如，取m=4，则有{}{} ,9,5,1,3,7,,8,4,0,4,8,10--=--=k k ，k 2={…，－6，－2，2，6，10，…}，k 3={…，－5，－1，3，7，11，…}.数组0，1，2，3；－8，5，2，－1等等都是模的4的一个完全剩余系.显然，模m 的完全剩余系有无穷多个.但最常用的是下面两种： （1）非负数最小完全剩余系：0，1，2，…，m －1；（2）绝对值最小完全剩余系：它随m 的奇偶性不同而略有区别.当.),1(,,1,0,1,),1(,,12k k k k k m -----+= 为时（对称式） 当).1(,,1,0,1,),1(,.),1(,1,0,1,),2(),1(,2-----------=k k k k k k k k m 或为时 由定义不难得到如下判别完全剩余系的方法：定理一：m 个整数m a a a ,,,21 是模m 的一个完系i a j i ,时当≠⇔≡)(mod m a j 定理二：设（b,m ）=1，c 为任意整数.若n a a a ,,,21 为一个完系，则c ba c ba c ba m +++,,,21 也是模m 的一个完全剩余系.特别地，任意m 个连续整数构成模m 的一个完全剩余系.【证明】只需证明：当).(mod ,m c ba c ba j i j i +≡+≠时而这可用反证法得证.下略. 设m 为一正整数，由于在0，1，…，m －1中与m 互质的数的个数是由m 惟一确定的一个正整数，因此，可给出如下定义.定义四：m 为一正整数，把0，1，…，m －1与m 互质的数的个数叫做m 的欧拉函数，记为).(m ϕ显然，)(m ϕ的定义域是正整数N*，前n 个值为：,,6)7(,2)6(,4)5(,2)4(,2)3(,1)2(,0)1( =======ϕϕϕϕϕϕϕ当m=p 为质数时，.1)(-=p p ϕ设k 是模的一个剩余类.若a 、b ∈k ，则).(mod m b a ≡于是由性质9知，（a ,m ）=（b,m ）.因此，若（a ,m ）=1，则k 中的任一数均与m 互质.这样，又可给出如下定义.定义五：如果一个模m 的剩余类k r 中任一数与m 互质，则称k r 是与模m 互质的剩余类；在与模m 互质的每个剩余类中任取一个数（共)(m ϕ个）所组成的数组，称为模m 的一个简化剩余系.例如，取m=6，在模6的六个剩余类中，{},,13,7,1,5,11,1 --=k{} ,17,11,5,1,7,5--=k 是与模6互质的剩余类.数组1，5；7，－7；1，－1；等等都是模6的简化剩余类.由此定义，不难得到：定理三:)(21,,,m a a a ϕ 是模m 的简化剩余系)).(,2,1,,)((mod ,1),(m j i j i m a a m a j i i ϕ =≠≡=⇔且 定理四：在模m 的一个完全剩余系中，取出所有与m 互质的数组成的数组，就是一个模m 的简化剩余系.这两个定理，前者是简化剩余系的判别方法，后者是它的构造方法.显然，模m 的简化剩余系有无穷多个，但常用的是“最小简化剩余系”，即由1，2，…，m －1中与m 互质的那些数组成的数组.由定理不难证得简化剩余系的如下性质定理.定理五：设)(21,,,m a a a ϕ 是模m 的简化剩余系.若（k,m ）=1，则)(21,,,m ka ka ka ϕ 也是模m 的简化剩余系.下面介绍两个有关欧拉函数的重要结论.其证明略. 定理六：（欧拉定理）若（a ,m ）=1，则)(mod 1)(m a m ≡ϕ 特别地，（费马小定理）若m=p 为质数，p a ，则).(mod 11p a p ≡- 定理七：（威尔逊定理）设p 素数，则（p －1）！).(mod 1p -≡ 定理八：（欧拉函数值计算公式）令m 的标准分解式为 k k p p p m ααα 2121=， 则 ∏=-=ki i p m m 1).11()(ϕ例如，30=2·3·5，则.8)511)(311)(211(30)30(=---=ϕ读者应认识到：由于任何整数都属于模m 的某一剩余类，所以，在研究某些整数性质时，选取适当的（模）m ，然后在模m 的每个剩余类中取一个“代表数”（即组成一个完全剩余系），当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.Ⅲ.同余方程设x a x a x a x a x f n n n n 为0111)(++++=-- 的整系数多项式.类似于多项式和代数方程式的有关定义，我们有定义六：同余式)(mod 0),(mod 0)(m a m x f n ≡≡叫做一元n 次同余方程.例如，)3(mod 03539257≡-+-x x x 是七次同余方程.定义七：若c 使得)(mod ,)(mod 0)(m c x m c f ≡≡则成立叫做同余方程)(mod 0)(m x f ≡的一个解.显然，同余方程的解是一些剩余类，而不仅是一个或n 个类.例如，),5(mod 1≡x)5(mod 4≡x 都是二次同余方程)5(mod 12≡x 的解.1．一次同余方程)(mod m b ax ≡（其中m a ）称为一次同余方程.关于它的解，有如下共知的结论：定理九：若（a ,m ）=1，则)(mod m b ax ≡有一个解.定理十：若（a ,m ）=d>1，d b ，则)(mod m b ax ≡无解，其中)(mod 0m a ≡. 定理十一：若（a ,m ）=d>1，d|b ，则)(mod m b ax ≡有d 个解.并且，若)(mod 1m x βα=的一个解为),(mod 1m r x ≡则d 个解为：1,,1,0),(mod 1-=+≡d k m km r x ，其中.,,1dm m d b d a ===βα 下面介绍一次同余方程1),(),(mod =≡m a m b ax （*）的解法.【解法1】因（a ,m ）=1，则存在二数s,t ，使得as +mt=1，即)(mod 1m as =，由此有)(mod ),(mod m bs x m bs asx ≡≡于是为（*）的解.【解法2】先把（*）变形成abm a b x )((mod ≡仅只是形式上的记号），然后用与m 互质的数陆续乘右端的分子分母，直至把分母绝对值变成1（通过分子分母各对模m 取余数）而得到解.【解法3】得用欧拉定理.因),(mod )(mod ),(mod 11)()()(m a b x a m b ax m a m m m -⋅≡≡≡ϕϕϕ可得由 从而有解 ).(mod 1)(m a b x m -⋅≡ϕ2．一次同余方程组定义八：若数r 同时满足n 个同余方程：r n k m x f k k 则.,,2,1),(mod 0)( =≡叫做这n 个同余方程组成的同余方程组的解.定理十二：对同余方程组⎩⎨⎧≡≡).(mod ),(mod 2211m c x m c x记.],[,),(2121M m m d m m == ①若d 21c c -，则此同余方程组无解；②若21|c c d -，则此同余方程组有对模M 的一类剩余解.Ⅳ.模m 的阶和中国剩余定理 （1）模m 的阶定义九：设m>1是一个固定的整数，a 是与m 互素的整数，则存在整数k ，1≢k ＜m ，使得)(mod 1m a k ≡.我们将具有这一性质的最小正整数（仍记为k ）称为a 模m 的阶.a 模m 的阶具有如下性质：①设m a k m a 模是,1),(=的阶，ν,u 是任意整数，则)(mod m a a v u ≡的充要条件是)(mod k u ν≡. 特别地，)(mod 1m a u≡的充分必要条件是k|u. 【简证】充分性显然.必要性.设).(mod 11),()(mod ,,m a m a m a a u l u lu易知及则由记=≡-=>ννν用带余除法，k r m a m a a k r r kq l r r kq <≤≡≡⋅<≤+=0).(mod 1),(mod 1,0,由即故这里及k 的定义知，必须r=0，所以).(mod k r u ≡②设a m a ,2),(=模m 的阶为k ，则数列,,,,32 a a a 模m 是周期的，且最小正周期是k ，而k 个数k a a a ,,,2 模m 互不同余.③设a m a 则,1),(=模m 的阶整除欧拉函数).(m ϕ特别地，若m 是素数p ，则a 模p 的阶整除p －1.（2）中国剩余定理（即孙子定理）设n m m m n ,,,,221 ≥是两两互质的正整数，记M=∏===ni ii i n i m MM m 1),,2,1(, 则同余方程组 ),,2,1)((mod n i m c x i i =≡ 有且只有解 ∑=≡ni ii iM c M x 1).(mod α （△）其中.,,2,1),(mod 1n i m M i i i =≡α （△△）【证明】由)(1),(j i m m j i ≠=知，1),(=j i m M ，因此每一个同余方程)(mod 1i iy m M ≡ （i =1，2，…n ）都有解，于是必存在),(|,).(mod 1,j i M m M m M m M i i i i i i i ≠=≡又因使得αα 所以对模).(mod ),,2,1(111i i i i i n n n i i i i m c c M c M c M c M n i m ≡≡++++=αααα 有故（△△）是（△）的解.若21,x x 是适合（△）的任意两个解，则).(1),(,,,2,1),(mod 21j i m m n i m x x j i i ≠===因 故),(mod ),(mod 212121M x x m m m x x n ≡≡即 因此，（△△）是（△）的惟一解.赛题精讲例1：数1978n 与1978m 的最末三位数相等，试求正整数m 和n ，使得n+m 取最小值，这里.1≥>m n （第20届IMO 试题）【解】由已知而),1000(mod 10781978mn≡1000=8×125，所以 )8(m o d 10781978m n≡ ①)125(mod 10781978m n ≡ ②因1≥>m n ，且（1978m ，125）=1，则由②式知1978n －m ≡1（mod125）③又直接验证知，1978的各次方幂的个位数字是以8、4、2、6循环出现的，所以只有n －m 为4的倍数时，③式才能成立，因而可令n －m=4k.由于. n+m=（ n －m ）+2m=4k+2m ，因而只需确定出k 和m 的最小值.先确定k 的最小值：因为19784=（79×25+3）4≡34≡1（mod5），19784≡34≡1（mod25）.故可令19784=5t+1，而5 t ，从而0≡1978n－m－1=19784k －1=（5k+1）k －1≡2)5(2)1(t k k ⋅- +)125(mod5t k ⋅，显然，使上式成立的k 的最小值为25. 再确定m 的最小值：因1978≡2（mod8），则由①式知，)8(mod 22m n ≡ ④ 由于,1≥>m n ④式显然对m=1，2不成立，从而m 的最小值为3.故合于题设条件的n+m 的最小值为106.【评述】比例中我们用了这样一个结论：1978的各次方幂的个位数字是以8，4，2，6循环出现，即，当r=1，2，3，4时，).10(mod 6,2,4,8197819784≡=+rq p 这种现象在数学上称为“模同期现象”.一般地，我们有如下定义：整数列{}n x 各项除以m （m ≣2，m ∈N*）后的余数n a 组成数列{}n a .若{}n a 是一个周期数列，则称{}n x 是关于模m 的周期数列，简称模m 周期数列.满足n T n a a =+（或n T n x a ≡+ （modm ））的最小正整数T 称为它的周期.例如，（1）{}n1978是模10周期数列，周期为4；（2）自然数列{n}是一个模m （m ≣2，m ∈N*）周期数列，周期为m ；（3）任何一个整数等差数列都是一个模m （m ≣2，m ∈N*）周期数列，周期为m.例2：设a 是方程01323=+-x x 的最大正根，求证：17可以整除[a 1788]与[a 1988].其中[x ]表示不超过x 的最大整数. （第29届IMO 预选题）【证明】根据如下符号表可知，若设三根依次为a <<βα， 则,121,211<<-<<-βα.||,,02)12(2)(,223233βαβαααααα<<->-=+-+-=-<于是由于f a另一方面，由韦达定理知，)8(1296292)3(2)(233322222a aa a a a a a a -+=+-+=+-+=+-=-+=+αββαβα.1,8)22(2222<+∴=>βαa为了估计[1788a]、[1988a]，先一般考察[a n ]，为此定义：),2,1,0.( =++=n a u n n n n βα直接计算可知：).0(3,9.32,323222210≥-==++==++==++n n u u a u a u u n n 以及βαβ 又因,12223,0,||(10<-<-=+>+<<+<αβαβαβαβα又即n n n n 当2≥n 时，)].(1[1)(),1||22n n n n n n n n n n n u u a βαβαβαβαβα+---=+-=<+<+≤+则),2,1.(1][ =-=∴n u a n n由此知，命题变为证明：1119881788--u u 和能被17整除. 现考察{}n u 在模17的意义下的情况：,2,6,5,16,9,9,11,1,7,9,3,311109876543210≡≡≡≡≡≡≡≡≡≡≡≡u u u u u u u u u u u u,9,3,3,0,6,14,118171615141312≡≡≡≡≡≡≡u u u u u u u可见，在模17意义下，{}n u 是16为周期的模周期数列，即).17(mod 16n n u u ≡+由于 1788),17(mod 1),17(mod 1),16(mod 41988),16(mod 1241988121788≡≡≡≡≡≡u u u u 故故).17(mod 01,0119881788≡-≡-u u 命题得证.例3：求八个整数821,,,n n n 满足：对每个整数k （－1985<k<1985），有八个整数a 1，a 2，…，a 8∈{－1，0，1}，使得.882211n a n a n a k +++= （第26届IMO 预选题）【解】令数集{}.1,,2,1},1,0,1{,333|12321+=-∈⋅++⋅+⋅+==+n i a a a a a k k G i n n显然 3331m a x 12=++++=+n nG H ，.33312H mixG n -=----=且G 中的元素个数有1231+=+H n 个.又因G 中任意两数之差的绝对值不超过2H ，所以G 中的数对模2H+1不同余.因此，G 的元素恰好是模2H+1的一个绝对值最小的完系，于是，凡满足H k H ≤≤-的任意整数都属于G ，且可惟一地表示为：n n a a a a 33312321⋅++⋅+⋅++ 形式.当n=7时，H=3280>1985，而n=6时，H=1043<1985.故n 1=1，n 2=3，…，n 8=37为所求. 例4：设n 为正整数，整数k 与n 互质，且0<k<n.令M={1，2，…，n －1}，给M 中每个数染上黑、白两种颜色中的一种，染法如下：（i ）对M 中每个i ，i 与n －i 同色；（ii ）对M 中每个i ，i ≠k,i 与|k －i |同色.求证：M 中所有的数必为同色. （第26届IMO 试题）【证明】因,1),(=n k 又0，1，…n －1是模n 的一个完全剩余系，所以0，k ，2k ，…，（n －1）k 也是模n 的一个完全剩余系.若设),1,,2,1,11)((mod -=-≤≤≡n j n r n r jk j j 其中 则M=}.,,,{121-n r r r 下只需证).21(1-≤≤+n j r r j j 与因为，若如此，当r 1的颜色确定后，M 中所有都与r 1同色.由于)(mod ),(mod )1(11n r k r n r k j j j j ++≡+≡+则，因此，（1）若k r r n k r j j j +=<++1,则，于是，由条件（i ）知，jj j j r r n n r n r k =---=-+)(1与同色.又由条件（ii ）知，111||+++=---j j j r k r k r k 与同色，故j j r r 与1+同色.综上所述可知，j j r r 与1+同色.命题得证.例5：设a 和m 都是正整数，a >1.证明：).1(|-ma m ϕ【证明】实上，显然1-ma a 与互素，且1-ma a 模的阶是m ，所以由模阶的性质③导出).1(|-m a m ϕ例6：设p 是奇素数，证明：2p －1的任一素因了具有形式x px ,12+是正整数.【证明】设q 是2p －1的任一素因子，则q ≠2.设2模q 的阶是k ，则由)(mod 12q p≡知k|p ，故k=1或p （因p 是素数，这是能确定阶k 的主要因素）.显然k ≠1，否则),(mod 121q ≡这不可能，因此k=p.现在由费马小定理)(mod 121q q ≡-推出.1|,1|--q p q k 即因p 、q 都是奇数，故q －1=2p x（x 是个正整数），证毕.例7：设m,a ,b 都是正整数，m>1，则.1)1,1),(-=--b a bamm m【证明】记).1,1(--=bam m d 由于（a ,b ）|a 及（a ,b ）|b ，易知1|1),(--a b a m m及1|1),(--b b a m m ，故d m b a |1),(-，另一方面设m 模d 的阶是k ，则由)(mod 1),(mod 1d m d m b a ≡≡推出，k|a 及k|b ，故k|（a ，b ）.因此.1|),(mod 1),(),(-≡b a b a m d d m 即 综合两方面可知，.1),(-=b a md 证毕.例8：设n ，k 是给定的整数，n>0，且k （n －1）是偶数.证明：存在,1),(),(,,==n y n x y x 使得是).(mod n k y x ≡+【证明】我们先证明，当n 为素数幂αp 时结论成立.实际上，我们能证明，存在x ,y ，使 p x y ，且k y x =+.如p=2，则条件表明k 为偶数，可取2,11,1,2;1,1-==-==>-==k y x k y x p k y x 或则如中有一对满足要求.一般情形下，设r r p p n αα11=是n 的标准分解，上面已证明，对每个i p ，均有整数i x ，i y ，使p i x i y i ，且).,,2,1(r k y x i i =+现在孙子定理表明，同余方程组)(mod ,),(mod 111r a r r p x x p x x ≡≡ α有解x ，同样)(mod ,),(mod 111r a r r p y y p y y ≡≡ α也有解y.现在易证x ,y 符合问题中的要求：因p i x i y i ，故p i x y （i =1，…，r ），于是（x y ，n ）=1.又).(mod ),,,1)((mod 1n k y x r i p k y x y x i i i ≡+==+=+故 α例9：设n 为任意的正整数.证明：一定存在n 个连续的正整数解，使其中任何一个都不是质数的整数幂. （第30届IMO 试题）【证明】取2n 个两两不同的质数.,,,,,,2121n n q q q p p p 和同余方程组),(mod i i q p i x -≡n i ,,2,1 =.由于n n q p q p q p ,,,2211 两两互质，根据孙子定理必有解，取为正整数N ，则n 个连续正整数N+1，N+2，…，N+n 都至少含有两个不同的质因数，因而它们中的任一个都不是质数的整数幂.证毕.。

同余
1．同余
0、初等数论基本概念：
①整除：设a，b 是整数，b≠0．如果存在一个整数q 使得等式：a＝bq 成立，则称b 能整除a 或a 能被b 整除，
记作b|a；如果这样的q 不存在，则称b 不能整除a．
②最大公因数：设a1，a2，…，a n 是n 个不全为零的整数，若整数d 是它们之中每一个的因数，那么d 就叫做a1，a2，…，a n 的一个公因数．整数的公因数中最大的一个叫做它们的最大公因数，记作（a1，a2，…，an）．
③互质：设a1，a2，…，a n 是n 个不全为零的整数，若（a1，a2，…，a n）＝1，则称a1，a2，…，an 是互质的．
1、同余：
设m 为正整数，称为模．若用m 去除两个整数a 和b 所得的余数相同，则称a 和b 对模m 同余，记作
a≡b（modm）．
读作a 同余于b 模m．
2、性质：
①a≡a（modm），
②如果a≡b（modm），那么b≡a（modm），
③如果a≡b（modm）且b≡c（modm），那么a≡c（modm），
④若a≡b（modm），c≡d（modm），则ac≡bd（modm），
⑤若a≡b（modm），则a n≡b n（modm）．
1/ 1。

同余同余式性质应用非常广泛，在处理某些整除性、进位制、对整数分类、解不定方程等方面的问题中有着不可替代的功能，与之密切相关的的数论定理有欧拉定理、费尔马定理和中国剩余定理。

基础知识三个数论函数对于任何正整数均有定义的函数，称为数论函数。

在初等数论中，所能用到的无非也就有三个，分别为：高斯(Gauss)取整函数[x ]及其性质，除数函数d (n )和欧拉(Euler)函数)(x ϕ和它的计算公式。

1． 高斯(Gauss)取整函数[x ]设x 是实数，不大于x 的最大整数称为x 的整数部分，记为[x ]；][x x -称为x 的小数部分，记为｛x ｝。

例如：［0.5］＝0，7.0}3.0{,1415.0}{,4][,3]3[,7]50[=-=-=--=-=Λππ等等。

由}{],[x x 的定义可得如下性质：性质1.1}{0};{][<≤=-x x x x ；性质2.1][][1+<≤<-x x x x ；性质3.设Z a ∈，则][][x a x a +=+；性质4.][][][y x y x +≥+;}{}{}{y x y x +≤+;性质5.⎩⎨⎧---=-1][][][x x x Zx Z x ∉∈；性质6.对于任意的正整数n ，都有如下的埃米特恒等式成立：][]1[]2[]1[][nx nn x n x n x x =-+++++++Λ； 为了描述性质7，我们给出如下记号：若a b |α，且1+αb a ，则称为αb 恰好整除a ，记为a b ||α。

例如：我们有2000||5,2000||234等等，其实，由整数唯一分解定理：任何大于1的整数a 能唯一地写成k i p p p a k a k a a ,,,2,1,2121ΛΛ==的形式，其中i p 为质（素）数（)(j i p p j i <<）。

我们还可以得到：k i a p i a i ,,2,1,||Λ=。

同余的概念与应用概念与性质1. 定义：若整数a,b 被整数m(m≥1)除的余数相同,则称a 同余于b 模m,或a,b 对模m 同余.记为a≡b(modm).余数r:0≤r<1.2. 性质：(ⅰ)a≡b(modm)⇔m|a-b,即a=b+mk,k ∈Z.(ⅱ)若a≡b(modm),b≡c(modm),则a≡c(modm).(ⅲ)若a 1≡b 1(modm),a 2≡b 2(modm)，则a 1±a 2≡b 1±b 2(modm),a 1a 2≡b 1b 2(modm);(ⅳ)设f(x)=a n x n +a n-1x n-1+…+a 1x+a 0,g(x)=b n x n +b n-1x n-1+…+b 1x+b 0是两个整系数多项式,满足a i ≡ b i (modm)(0≤i≤n).若a≡b(modm),则f(a)≡f(b)(modm).(ⅴ)ac≡bc(modm)⇔a≡b(mod ),(m c m ), (ⅵ)若m≥1,(a,m)=1,则存在整数c 使得ac≡1(modm).称c 为a 对模m 的逆或倒数,记为c=a -1(modm);(ⅶ)⎩⎨⎧≡≡)(mod )(mod 21m b a m b a 同时成立⇔≡a b (mod[m 1,m 2]);(ⅷ)若a≡b(modm 1),a≡b(modm 2),且(m 1,m 2)= 1,则a≡b(modm 1m 2).3. 剩余类：设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r≤m -1}称为模m 的一个剩余类。

性质：(ⅰ)i m i K Z 10-≤≤= 且K i ∩K j =φ(i≠j).(ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里.(ⅲ)对任意a 、b ∈Z ，则a 、b ∈K r ⇔a≡b(modm).4. 完全剩余系：设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系。

同余的概念-人教A版选修4-6 初等数论初步教案一、教学目标1.了解同余的定义和性质；2.掌握同余的运算规则和推论方法；3.运用同余理论解决实际问题。

二、教学重点1.同余的定义和性质；2.同余的运算规则；3.同余理论的应用。

三、教学难点1.同余的推论方法；2.同余理论在实际问题中的应用。

四、教学过程1. 导入（10分钟）首先引入同余的概念，让学生思考两个数之间应该满足什么条件才能说它们是同余的。

然后与学生一起探讨同余的含义和性质。

2. 定义和性质（20分钟）讲解同余的定义和性质，包括同余关系的传递性、对称性、反身性等，以及同余意义下的等式和不等式的特性。

在讲解的过程中，可以通过一些例子来加强学生的理解。

3. 运算规则（30分钟）讲解同余的运算规则，包括同余的加、减、乘、除、幂次等运算法则，以及同余的推论方法和定理。

在讲解的过程中，可以通过一些练习题来巩固学生的运算能力。

4. 应用实例（30分钟）将同余理论的应用与学生生活中的日常问题联系起来，让学生通过实际例子来理解同余理论的应用。

例如，用同余理论来解决生日问题、购物折扣问题等。

5. 总结归纳（10分钟）对课程内容进行总结归纳，让学生能够理解同余概念的重要性和实际应用的意义。

同时，让学生通过课程总结，确认对同余理论的掌握程度，进一步提高学习兴趣。

五、教学评价通过对学生的课堂表现和作业完成情况的评价，反馈学生对同余概念的掌握和运用能力。

同时，让学生知道如何运用同余理论来解决实际问题的方法和技巧。

六、教学反思在教学中，要注意让学生能够理解同余的含义和性质，并掌握运算规则和应用方法。

在讲解过程中，可以采用一些具体的例子来加深学生的理解，同时也要注意运用不同的教学方式和方法，以便能够满足不同学生的学习需求。

高二数学竞赛班二试讲义同余与剩余类班级姓名一、知识点金1．同余两个整数,a b 除以正整数m ，若余数相同，则称a 与b 关于模m 同余，记作(mod )a b m ≡，这叫做同余式。

2．性质以下性质均在整数范围内讨论，模为正整数。

（1）若(mod )ac bc m ≡，则当(,)1c m =时，(mod )a b m ≡；则当(,)c m d =时，(modm a b d≡。

（2）若1(mod )A a m ≡，2(mod )A a m ≡，且12(,)1m m =，则12(mod )A a m m ≡。

（3）费尔马小定理：p 为素数，对任意正整数a ，都有|()pp a a -。

费尔马小定理的推论：设p 为素数，a 为正整数，且(,)1a p =，11(mod )p a p -≡。

证明：由于,2,,(1)a a p a ⋅⋅⋅-模p 的余数各不相同，否则，若有(mod )ia ja p ≡，其中11i j p ≤<≤-，则|()p j i a -，而p 不整除a ，所以|()p j i -，这是不可能的，因此,2,,(1)a a p a ⋅⋅⋅-模p 的余数必然取遍1,2,,1p ⋅⋅⋅-这1p -个数，仅可能顺序不同。

故2(1)12(1)(mod )a a p a p p ⋅⋅⋅⋅⋅⋅-≡⋅⋅⋅⋅⋅⋅-。

又p 为素数，则((1)!,)1p p -=，所以由性质（1）得11(mod )p ap -≡。

3．剩余类设*m N ∈，把全体整数按对模m 的余数进行分类，余数为r (01)r m ≤<-的所有整数归为一类，记为r k ，r k 称为模m 的一个剩余类(0,1,2,,1)r m =⋅⋅⋅-。

显然，r k 是一个以m 为公差的无穷等差数集。

它有如下性质：（1）011m Z k k k -=⋅⋅⋅ ，且i j k k =∅ ；（2）对任意n Z ∈，有唯一的r ，使得r n k ∈。

数论讲义定义（欧拉(Euler)函数）对于一个正整数 n ，小于 n 且和 n 互质的正整数（包括 1）的个数，记作 φ(n )（1）对于给定的一个素数 p ， φ(p) = p -1。

（2）则对于正整数 n = p k ，φ(n) = p k - pk -1欧拉(Euler)函数公式： kk p p p n n p p p n n k 11()11)(11()(212121---== ϕααα，则的标准分解为：若 例1 与300互素且不超过300的自然数的个数。

解 所求的数即80)511)(311)(211(300)300(=---=ϕ例2 1到1001这1001个数中，是7,11或13的倍数的有多少个？解：由于7,11,13均为质数，所有不是它们的倍数的数都是和它们互素的，而与它们互素就意味着和1001互素，且这些数都是比1001小的数。

所以我们可以直接使用 111(1001)1001(1)(1)(1)71113ϕ=⨯-⨯-⨯-61012=⨯⨯720=定理1：（欧拉（Euler ）定理）设),(m a ＝1，则)(mod 1)(m am ≡ϕ。

分析与解答：要证)(mod 1)(m a m ≡ϕ，我们得设法找出)(m ϕ个n 相乘，由)(m ϕ个数我们想到m ,,2,1 中与m 互质的)(m ϕ的个数：)(21,,,m a a a ϕ ，由于),(m a ＝1，从而)(21,,,m aa aa aa ϕ 也是与m 互质的)(m ϕ个数，且两两余数不一样，故)(21m a a a ϕ⋅⋅⋅ ≡)(21,,,m aa aa aa ϕ ≡)(m a ϕ)(21m a a a ϕ⋅⋅⋅ （m m od ），而（)(21m a a a ϕ⋅⋅⋅ m ）＝1，故)(mod 1)(m a m ≡ϕ。

这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。

例3.设1),91(=ab ，求证：)(|911212b a-。

第 2 章 同余运算（一） 内容●同余概念 ●性质 ●剩余类→整数分类 ●模幂运算（二） 重点● 同余及其计算（三） 应用：● 密码学● 公钥密码学【例】 RSA 公钥算法：准备：选大素数p 、q ，记n ＝pq ，φ(n)＝(p －1)(q －1)，再选正整数e ，满足（e ，φ(n)）≡1（mod n ）并求d ，满足 ed ＝1（mod φ(n)）加密：明文串P 编码为数字M ，则密文C ≡e M （mod n ） 解密： M ≡d C （mod n ），再将数字M 解码得明文串P2.1 同余的概念及基本性质(一) 同余概念【定义2.1.1】给定一个正整数m ，两个整数a 、b 叫做模m 同余，如果a －b 被m 整除，或b a m -|，记作b a ≡ ()m mod ；否则叫做模m 不同余，记作a ≠b （（mod m ））【注】由于b a m -|等价于b a m --|，所以同余式b a ≡ ()m mod等价于 b a ≡()()m -mod ，故以后总假定模1≥m 。

判断同余的方法一：利用定义【例1】 7│28＝29－1，故29≡1（mod 7）；7│21＝27－6，故27≡6（mod 7）；7│28＝23－（－5），故23≡－5（mod 7）；(二) 性质【性质1】（定理1）设m 是一个正整数，a 、b 是两个整数，则a≡b （mod m ）⇔存在整数k ，使得a ＝b ＋km 。

（证）a≡b （mod m ） ⇔ b a m -|⇔ 存在k ，使得 a －b ＝km ，即a ＝b ＋km【性质2】（定理2）同余是一种等价关系。

即（i ） 自反性：a≡a m（ii ） 对称性：a≡b （mod m ） ⇒ b≡a （mod m ） （iii ） 传递性：a≡b mod m 且b≡c （mod m ）⇒ a≡c （mod m ）（证）（i ）m │0＝a －a ⇒ a≡a m（ii ）a≡b （mod m ） ⇒ m │a －b ⇒ m │b －a ＝－(a －b) ⇒ b≡a （mod m ）（iii ）a≡b （mod m ），b≡c （mod m ） ⇒ m │a －b ，m │b －c⇒m│(a－b)＋(b－c)＝a－c ⇒a≡c （mod m）【例3】【性质3】（等价定义）（定理3）整数a、b模m同余⇔a、b被m除的余数相同。

课程类型 数学
“同余”
讲义编号：
本节的重点是同余理论，包括同余性质、同余类与剩余系、欧拉函数、欧拉小定理、Wilson 定理、中国剩余定理。

1. 同余
1) 设1d ≥，|d m ，若()mod a b m ≡，则()mod a b d ≡
2) 0d ≠，则()()mod mod a b m ad bd m d ≡ ⇔ ≡
3) ()()mod mod ,m ac bc m a b m c ⎛⎫≡ ⇔ ≡ ⎪ ⎪⎝
⎭ 4) 若1m ≥，(),1a m =，则存在c 使得()mod ca m ≡1
我们把c 称为a 对模m 的逆，记作()1mod a
m -或1a -。

显然：()1,1a m -=及()()11mod a
a m --≡
例1
【解答】
2. 同余类或剩余系
● 把全体整数分为这样的若干个两两不相交的集合，使得在一个集合中的任意两个数对模m 一定同余，而属
于不同集合中的两个数对模m 一定不同余。

每一个这样的集合称为模m 的同余类或模m 的剩余系。

我们以mod r m 表示r 所属的模m 的同余类
● 完全剩余系：一组数1,...,s y y 称为模m 的完全剩余系，如果对任意的a 有且仅有一个y i 是a 对模m 的剩
余，即a 同余与y i 模m 。

例2。