密码学数学基础第四讲 同余式(3)

1.同余的概念：设m 是一个给定的正整数，把它称为模．如果两个整数,a b 用m 去除所得的余数相同，则称a 与b 对模m 同余，记为()mod a b m ≡．这个符号读作：“a 与b 模m 同余”，如()644mod3≡，()1973mod ≡，()50mod5≡．2.同余这一概念也可用下面两种方式之一来叙述，三种说法是等价的．若|m a b -，则a 与b 对模m 同余； 若a b mt =+（t 为整数），则a 与b 对模m 同余．用符号表示为：()|mod m a b a b mt a b m -⇔=+⇔≡．3.根据同余的定义，容易得到同余的一些性质，最常用的性质有以下几条： 反身性：()mod a a m ≡；对称性：()()mod mod a b m b a m ≡⇒≡； 传递性：()()()mod mod mod a b m a c m b c m ≡⎫⎪⇒≡⎬≡⎪⎭；可加性：()()()mod ()mod mod a b m a c b d m c d m ≡⎫⎪⇒±≡±⎬≡⎪⎭．推论1：()mod a c b c m ±≡±；推论2：()()mod 0mod a b c m a b c m +≡⇒+-≡．可乘性：()()mod mod a b m ac bc m ≡⇒≡（c 为整数）． 推论1：()()()mod mod mod a b m ac bd m c d m ≡⎫⎪⇒≡⎬≡⎪⎭．推论2：()()mod mod n n a b m a b m ≡⇒≡（n 为自然数）．除法性质：若(mod )ac bc m ≡，且(,)c m d =，则(mod )ma b d≡． 证明：由(,)c m d =可设,c de m df ==，且(,)1e f =，则有 (mod )|ac bc m m ac bc ≡⇒-，即|()|()df a b de f a b e -⇒-由(,)1e f =可知，|()(mod )f a b a b f -⇒≡，即mod m a b d ⎛⎫≡ ⎪⎝⎭．推论：若(mod )ac bc m ≡，且(,)1c m =，则(mod )a b m ≡．第4讲数论1. 若正整数m 和1995对于模6同余，则m 的值可能是 （ ）A ．25B ．26C ．27D ．28【解析】 199563323=⨯+，故19953(mod6)≡273(mod6)≡，选C ．一、四则运算与余数规律【例 1】 求3326(25746)+被50除所得的余数．【解析】33332577(mod50)2577(mod50)≡⇒≡ 2432337491(mod50)71(mod50)71(mod50)77(mod50)≡≡-⇒≡⇒≡⇒≡ 故332577(mod50)≡，从而3325746(746)(mod50)3(mod50)+≡+≡ 于是332626(25746)3(mod50)+≡又552507243730(mod50)37(mod50)≡+≡+≡⇒≡-，故102203(7)491(mod50)31(mod50)≡-≡≡-⇒≡，故 26205153333732129(mod50)++≡≡⨯≡-⨯≡-≡即余数为29．【变式】 设,a b 都是正整数，且a 被7除余数是2，b 被7除余数是5，求24a b +和24a b -被7除的余数． 【解析】 根据同余的定义，将题设条件“翻译”成符号形式，然后运用同余的性质来求解． 由题意可知，2(mod7),5(mod7)a b ≡≡由2(mod7)a ≡及(mod )(mod )n n a b m a b m ≡⇒≡这一性质可知 2224(mod 7)a ≡≡由5(mod7)b ≡及(mod )(mod )a b m ac bc m ≡⇒≡这一性质可知 4201(mod7)b ≡≡-故224413(mod7),4415(mod7)a b a b +≡-≡-≡+≡．【变式】 求4444441234.....19901991++++++的个位数． 【解析】 首先考查1,2,3,4,....,1990,1991除以10的余数情况，然后再拓展到4次． 4444102030....19900(mod10)102030....19900(mod10)≡≡≡≡≡⇒≡≡≡≡≡； 44441112131.....1991(mod10)1112131.....1991(mod10)≡≡≡≡≡⇒≡≡≡≡≡； 44442122232.....1982(mod10)21222.....19826(mod10)≡≡≡≡≡⇒≡≡≡≡≡； 44443132333....1983(mod10)31323....19831(mod10)≡≡≡≡≡⇒≡≡≡≡≡； ………44449192939...1989(mod10)91929...19891(mod10)≡≡≡≡≡⇒≡≡≡≡≡ 故4444441234.....1990199112006199119961995199++++++≡⨯+⨯+⨯+⨯+⨯ 6199119961991199049454949488(mod10)+⨯+⨯+⨯+⨯≡++++++++≡≡ 从而可知，个数数字为8．【变式】 ⑴ 求738547被17除的余数；⑵ 23374747a =，其中2337a =，试求233747被7整除的余数．【解析】 ⑴ 24474(mod17)47161(mod17)471(mod17)≡-⇒≡≡-⇒≡7385184641418464747(47)474713(mod17)⨯+≡≡⨯≡≡． ⑵ 36472(mod7)4781(mod7)471(mod7)≡-⇒≡-≡-⇒≡23371(mod6)371(mod6)≡⇒≡故23376164747(47)47475(mod 7)r r +≡≡⋅≡≡，其中r 为正整数即所求的余数为5．【例 2】 求证：1999199911|1023+．【解析】 看到高次项，我们就应该想到要用(mod )(mod )n n a b m a b m ≡⇒≡这一性质，但是 199910太大，可通过(mod )a c b c m ±≡±这一性质将底数变小，然后来证明． 199********(mod11)101(mod11)10(1)1(mod11)≡⇒≡-⇒≡-≡- 199********(mod11)2311(mod11)≡⇒≡≡故199919991023110(mod11)+≡-+≡，即1999199911|1023+．【例 3】 试证明32641|21+．【解析】32323232641|21210(mod641)21(mod641)21641(mod641)+⇔+≡⇔≡-⇒≡-+ 3272525264025(mod641)25(mod641)25641(mod641)⇔≡=⨯⇔≡⇔≡-25223522159(mod641)2159159641225(mod641)⇔≡-⨯⇔≡-≡--≡-⨯ 1831522525641616277(mod641)277(mod641)⇔≡-≡-+≡≡⨯⇔≡152132776415642141(mod641)2141(mod641)⇔≡-≡-≡-⨯⇔≡- 1321121411416415002125(mod641)2125(mod641)⇔≡-≡-+≡≡⨯⇔≡1129921256412129(mod641)21291296412(mod641)⇔≡-≡-⨯⇔≡-≡-+≡ 9922(mod 641)≡显然成立，反推即可得出结论．二、余数的分类讨论【例 4】 1986198719881989n n n n +++的个位不是0，求正整数n 满足的条件．【解析】19866(mod10)19866(mod10)n n ≡⇒≡ 同理，19877(mod10),19888(mod10),19899(mod10)n n n n n n ≡≡≡故1986198719881989(6789)(mod10)n n n n n n n n +++≡+++我们知道，自然数的正整数次方的个位数字周期出现，且最小公倍数为4． 故可分以下情况讨论：若4n k =，则1986198719881989(6161)144(mod10)n n n n +++≡+++≡≡； 若41n k =+，则1986198719881989(6789)300(mod10)n n n n +++≡+++≡≡； 若42n k =+，则1986198719881989(6941)200(mod10)n n n n +++≡+++≡≡； 若43n k =+，则1986198719881989(6329)200(mod10)n n n n +++≡+++≡≡． 又1986198719881989n n n n +++的个位不是0，故4n k =（k 为正整数）【变式】 试证明：当且仅当4|n 不成立时，有5|1234n n n n +++（n 为自然数）【解析】 设4n k r =+（k 为整数，0,1,2,3r =，,k r 不同时为0），则有4422(2)2162n k r k r k r +==⋅=⋅，由161(mod5)161(mod5)k ≡⇒≡，故21622(mod5)n k r r ≡⋅≡．同理，38133(mod5)n k r r ≡⋅≡，425644(mod5)n k r r ≡⋅≡． 于是，12341234(mod5)n n n n r r r r +++≡+++ 当0r =时，12344(mod5)r r r r +++≡；当1r =时，12341234100(mod5)r r r r +++≡+++≡≡； 当2r =时，123414916300(mod5)r r r r +++≡+++≡≡； 当3r =时，12341827641000(mod5)r r r r +++≡+++≡≡ 故当且仅当4|n 不成立时，有5|1234n n n n +++（n 为自然数）．三、同余性质的相关应用【例 5】 261322431503985(mod )m ≡≡≡，且2613被m 除余数不为1，求自然数m 及余数． 【解析】 设261322431503985(mod )r m ≡≡≡≡，则2613,2243,1503,985am r bm r cm r dm r =+=+=+=+（,,,a b c d 为整数） 由此可知，()261322433702537a b m -=-==⨯⨯ ()150********c d m -=-=⨯⨯由m 是2537,2737⨯⨯⨯⨯的公约数，故m 可取2,37,237⨯． 当2m =时，余数为1r =，不合题意，舍去. 当37m =时，余数为23r =； 当74m =时，余数为23r =； 综上所述，37m =或74m =．【变式】 如果m 是大于1的整数，69，90，125对于m 同余，那么m 的值是_____________． 【解析】 由题意可知，6990125(mod )m ≡≡，则有2135560(mod )m ≡≡≡又m 是大于1的整数，()21,35,567=，故7m =．【例 6】 试证明：对任意自然数n ，2903803464261n n n n A =--+都能被1897整除．【解析】(2903464)(803261)n n n n A =--- (2903464)(803261)'M M =---（,'M M 为整数） 92712271'M M =⨯-⨯又(2903803)(464261)n n n n A =---(2903803)(464261)'N N =---（,'N N 为整数） 7210729'N N =⨯-⨯故0(mod271)A ≡，0(mod7)A ≡又(7,271)1=，18977271=⨯，故0(mod1897)A ≡．【例 7】 十进制下，44444444的各位数字之和等于A ，A 的各位数字之和为B ，B 的各位数字之和为C ，求C ．【解析】 44444444是一个很大的数字，但是它的位数我们可以估计出来．设44444444N =，则444454444222204444(10)10<=，这表明N 的位数不多于22220位． 因此，它的各位数字之和A 应小于222209⨯，即222209199980A <⨯=． 由此可知，A 最多为6位数，从而可知6954B <⨯=．在1,2,3,...53中，数字和最大的一个数是49，因此4913C ≤+=． 根据上例能被9整除的数的特点可知： (mod9)N A B C ≡≡≡又3344447(mod9)444473431(mod9)≡⇒≡≡≡，4444314811=⨯+，故14813777(mod9)N ⨯≡⨯≡．又7(mod9)C ≡，13C ≤，故7C =．点评：①101(mod9)n ≡；②一个正整数与其各位数字之和对于整数9同余．【变式】 证明：一个正整数能被9整除的充要条件是它的各位数字之和能被9整除． 【解析】 设能被9整除的任意的正整数均能表示为12....n a a a ，12....n A a a a =+++，则1212121....1010...10n n n n n a a a a a a a ---=⋅+⋅++⋅+我们知道，10199...9n n-=，故101(mod9)n ≡故121212112....1010...10...(mod9)n n n n n n a a a a a a a a a a A ---≡⋅+⋅++⋅+≡+++≡ 又12....9n a a a k =（k 为正整数），故90(mod9)A k ≡≡，即9|A ．反之，若一个数的各位之和能被9整除，则这个数必然能被9整除．【变式】 A 为任意n 位数，将组成A 的各位数字任意重新排列后得到一个新数B ，如果A B >，证明A B-是9的倍数．【解析】 设12...n A a a a =，123..n N a a a a =++++，则有1212121...1010...10(mod9)n n n n n A a a a a a a a N ---≡≡⋅+⋅++⋅+≡同理，(mod9)B N ≡，故0(mod9)A B -≡，得证．【例 8】 求整数x ，使得2(mod 3)3(mod 5)2(mod 7)x x x ≡⎧⎪≡⎨⎪≡⎩【解析】 解法一：将同余式转化成等式的形式，然后不停的作代换． 由2(mod3)x ≡可知，32x m =+（m 为整数），故323(mod5)31(mod5)36(mod5)2(mod5)m m m m +≡⇒≡⇒≡⇒≡ 设52m k =+，（k 为整数），则有3(52)2158x k k =++=+，故 1582(mod7)15615(mod7)1(mod7)k k k +≡⇒≡-≡⇒≡，故 71k n =+（n 为整数），从而15815(71)810523x k n n =+=++=+ 故整数x 是被105除余23的一切整数． 解法二：运用中国剩余定理首先求出一组123,,M M M 满足：()()()1111mod3,0mod5,0mod7M M M ≡≡≡ ()()()2110mod3,1mod5,0mod7M M M ≡≡≡()()()2110mod3,0mod5,1mod7M M M ≡≡≡ 本题当中12370,21,15M M M ===满足上述条件． 容易证明：()123mod3aM bM cM a ++≡()123mod5aM bM cM b ++≡ ()123mod 7aM bM cM c ++≡所以2,3,2a b c ===时123S aM bM cM =++满足题目条件．习题 1. 求所有满足3|21n +的正整数n ．【解析】30(mod3)21(mod3)2(1)21(1)1(mod3)n n n n ≡⇒≡-⇒≡-⇒+≡-+ 若3|21n +，则210(mod3)n +≡，故(1)10n -+=从而可知，当且仅当n 为奇数时，3|21n +．习题 2. a 除以5余1，b 除以5余4，且3a b >，求3a b -除以5的余数． 【解析】 由题意可知，1(mod5),4(mod5)a b ≡≡，则有 33414(mod5)a b -≡-≡-≡ 故余数为4．习题 3. 求10002除以13的余数.【解析】41232163(mod13)23271(mod13)≡≡⇒≡≡≡ 10001283442223(mod13)⨯+≡≡≡故余数为3．习题 4. 求9992的最后两位数字．【解析】()()()91210251212mod1002512840964mod10021mod100≡≡⇒≡⨯≡≡-⇒≡- 99999099909992222(1)121288(mod100)+⇒≡≡⋅≡-⨯≡-≡习题 5. 求证：555522227|(22225555)+【解析】226322223(mod7)222232(mod7)222221(mod7)≡⇒≡≡⇒≡≡ 故5555692522169252222222222(2222)(2222)3125(mod7)⨯+⨯+≡≡⋅⋅≡≡ 226355554(mod7)555542(mod7)555521(mod7)≡⇒≡≡⇒≡≡ 故22226370225555555542(mod7)⨯+≡≡≡从而可知，55552222222255555270(mod7)+≡+≡≡即555522227|(22225555)+．习题 6. 设n 为自然数，若1914103(mod83)n n +≡+，则n 的最小值可能是 （ ）A ．4B ． 8C ． 16D ． 32【解析】 1914103(mod83)91109720(mod83)n n n n +≡+⇒+≡⇒-≡，故选B ．生肖为何取数12？《周礼·春官·冯相氏》载：“掌十有二岁，十有二月，十有二辰，十日，二十八星之位，辨其叙事，以会天位。

第三章 数学基础近代密码学用到数学之多，遍及许多数学分支，如概率统计、信息论、数论、有限域理论、复杂性理论，甚至于代数、几何等都在近代密码学中扮演重要角色。

所以，数学是近代密码学不可或缺的工具。

3.1 数论3.1.1 数的m 进制表示1. 十进制表示十进制是最方便的一种整数表示法。

例： 7108109101198723+∙+∙+∙=110210710310553721234+∙+∙+∙+∙=2. m 进制表示实际上，使用任何进制表示一个数都是可以的。

定理 设m 是大于的正整数，则每一个正整数n 可唯一地表示为0111c m c m c m c n k k k k ++++=--其中),,2,1,0(k j c j =是整数，且0,0≠<≤k j c m c 。

记作：m k k c c c c n )(011 -=。

3. m 进制表示的具体做法将一个正整数n 表示成m 进制时，主要是要确定k k c c c c ，，，，110- 。

若用⎥⎦⎥⎢⎣⎢m n 表示n 除以m 后，取其整数部分（也就是比m n 小的最大整数），确定k k c c c c ，，，，110- 的方法如下：1. 令01c r =，n n =0，则有1221101c m c m c m c m n n k k k k ++++=⎥⎦⎥⎢⎣⎢=---2. 令12c r =，则有2331212c m c m c m c m n n k k k k ++++=⎥⎦⎥⎢⎣⎢=---3. 令23c r =， ……4. 若m n i >，令 ,2,1,0,1==+i c r i i122111++-----+++++=⎥⎦⎥⎢⎣⎢=i i i k k i k k i i c m c m c m c m n n5. 直到110++==⎥⎦⎥⎢⎣⎢=k k k k r c m n n ， 即m n k <为止。

4. 举例例 5389==m n ， 解 令 3890==n n则有34342323121201013 0 5350 3 55152 15577547753895c r n n c r n n c r n n c r n n ===⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢====⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢====⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢====⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢=，，，，故5123)4203(4525053389=+∙+∙+∙=例 2389==m n ， 解 令 3890==n n⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦1 12121 12320 32620 621220 1222420 42 24821 84 29720 97219421 19423892889778667556445334223112001====================================c n n c n n c n n c n n c n n c n n c n n c n n c n n ，，，，，，，，， 故2278)101000011(1222389=+++=第六次课截止于此3.1.2 数的因数分解素数 只能被1和其自身除尽的正整数称为素数（1,2,3,5,7, 11,13,17,…）。

同余定理知识点总结同余定理通常被描述为以下形式：如果整数a和b对于模m同余，即a ≡ b (mod m)，那么a和b除以模m的余数是相等的。

同余定理可以改写为a mod m = b mod m。

同余定理有两个基本的性质。

首先，它是一种等价关系，具有自反性、对称性和传递性。

其次，同余定理具有乘法和加法性质。

首先，我们来讨论同余定理的基本性质。

同余关系是一种等价关系，即它具有自反性、对称性和传递性。

自反性指的是对于任意的整数a，a ≡ a (mod m)。

这意味着任意整数都与自己对模m同余。

对称性指的是如果a ≡ b (mod m)，那么b ≡ a (mod m)。

传递性指的是如果a ≡ b (mod m)且b ≡ c (mod m)，那么a ≡ c (mod m)。

这三种性质构成了同余关系的一个等价关系，可以将整数划分为同余类，使得具有相同除模m余数的整数在同一个同余类中。

其次，同余定理具有乘法和加法性质。

对于任意的整数a、b、c和模m，如果a ≡ b (mod m)和c ≡ d (mod m)，那么有以下性质：a + c ≡ b + d (mod m)和a * c ≡ b * d (mod m)。

这两个性质表明了同余定理在乘法和加法下的保持性。

同余定理在数论和代数中有广泛的应用。

首先，同余定理常常被用来简化计算。

通过使用同余定理，我们可以将复杂的计算转化为求余数的简单计算，从而节省时间和精力。

其次，同余定理在代数方程的求解中有着广泛的应用。

例如，对于一个模线性方程a * x ≡ b (mod m)，我们可以通过同余定理将其转化为x的一元一次同余方程，从而求解出x的取值范围。

此外，同余定理在密码学领域也有着重要的应用。

加密算法中常常使用同余定理来进行模运算，从而实现数据的加密和解密。

在数论中，同余定理还有一些重要的推论。

首先，费马小定理和欧拉定理是同余定理的重要推论。

费马小定理描述了素数模意义下的幂运算规律，欧拉定理描述了任意模意义下的幂运算规律。

同余问题知识点讲解数论中的同余问题同余问题是数论中的一个重要知识点，也是各大数学竞赛和小升初考试必考的奥数知识点。

因此，学好同余问题对学生来说非常重要。

许多孩子都接触过同余问题，但也有不少孩子说“遇到同余问题就基本晕菜了！”。

同余问题主要包括带余除法的定义，三大余数定理（加法余数定理、乘法余数定理和同余定理），以及中国剩余定理和弃九法原理的应用。

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

其中，当r=0时，我们称a可以被b整除，q称为a除以b的商或完全商；当r≠0时，我们称a不可以被b整除，q称为a除以b的商或不完全商。

一个完美的带余除法讲解模型可以将带余除法的概念用一个图形化的模型来解释。

假设有一堆书，共有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的余数。

同余定理及其应用同余定理是数论中的一个重要定理，广泛应用于代数、密码学、编码理论等领域。

它的核心思想是两个整数除以一个正整数所得的余数相同，则这两个整数被称为同余数。

本文将深入探讨同余定理的理论基础以及在实际应用中的具体应用案例。

一、同余定理的理论基础同余定理的理论基础建立在欧拉定理的基础之上。

欧拉定理表明，若a和n互质（即a与n没有公共因子），则a的φ(n)次方与1模n同余，其中φ(n)表示小于n且与n互质的正整数的个数。

而同余定理则扩展了欧拉定理的应用范围，使得即使a与n不互质，也可以进行同余运算。

同余定理可以形式化地表示为：若两个整数a和b满足a ≡ b (mod n)，其中n为正整数，则a与b除以n所得的余数相同。

二、同余定理的应用案例1. 哈希函数在密码学和信息安全领域，哈希函数被广泛用于将任意长度的输入映射为固定长度的输出。

同余定理可以用于设计哈希函数的压缩函数，通过对输入取模的方式生成哈希值。

同余定理保证了不同输入产生的哈希值在模运算下具有统一的分布特征，从而提高了哈希函数的均匀性和唯一性。

2. 线性同余发生器线性同余发生器是一种常见的伪随机数发生器，通过递推公式生成伪随机数序列。

递推公式的关键就是同余定理。

通过不断对前一项取模，可以生成满足特定分布特征的伪随机数序列。

线性同余发生器被广泛应用于模拟实验、密码学算法以及其他需要随机数的场景。

3. 错误检测与纠正码在编码理论中，同余定理可以用于错误检测与纠正码的设计。

通过巧妙地选择同余定理中的模数，并进行恰当的编码映射，可以实现对输入码字的差错检测和纠正。

这种应用广泛应用于数据传输和存储中，提高了数据的可靠性和完整性。

4. 中国剩余定理同余定理的一个重要应用是中国剩余定理。

中国剩余定理是一种用于求解一组同余方程的方法，即给定一组同余方程，通过对同余定理的灵活应用，可以找到满足全部方程的最小正整数解。

中国剩余定理在数学研究中有广泛的应用，同时也在信息安全和密码学中发挥着重要作用。