1、教学目的和要求教学目的和要求（1）熟练掌握同余的基本概念及性质。（2）熟练掌握剩余类、完全剩余系、简化剩余系和欧拉函数的概念及其性质。（3）熟练掌握欧拉定理、费马定理和解某些同余问题。本章是初等数论的核心内容，是学生必须掌握的基础知识。第三章第三章 同同 余余2025/7/81 1第三章第三章 同同 余余 同余是数论中的重要概念，同余理论是研究整数同余是数论中的重要概念，同余理论是研究整数问题的重要工具之一问题的重要工具之一.本章介绍同余的基本概念，剩本章介绍同余的基本概念，剩余类和完全剩余系余类和完全剩余系.生活中我们经常遇到与余数有关的问题，比如：生活中我们经常遇到与余数有关的问题，比如：
2、某年级有将近某年级有将近400400名学生。有一次演出节目排队时出名学生。有一次演出节目排队时出现：如果每现：如果每8 8人站成一列则多余人站成一列则多余1 1人；如果改为每人；如果改为每9 9人人站成一列则仍多余站成一列则仍多余1 1人；如果每人；如果每1010人结成一列，结果人结成一列，结果还是多余还是多余1 1人；聪明的你知道该年级共有学生多少名？人；聪明的你知道该年级共有学生多少名？2025/7/82 2中学数学竞赛中学数学竞赛1 1、今天是星期一，再过、今天是星期一，再过100100天是星期几？天是星期几？3、13511，13903，14589被自然数被自然数m除所得余数除所得余数
3、相同，问相同，问m最大值是多少？最大值是多少？2 2、314592653=2910 93995314592653=2910 93995的横线处漏写了一个的横线处漏写了一个 数字，你能以最快的办法补出吗？数字，你能以最快的办法补出吗？2025/7/83 3一、同余一、同余3.13.1同余的概念及其基本性质同余的概念及其基本性质 1.定义定义1 给定正整数m，如果用m去除任意的两个整数a与b所得的余数相同，则称a与b对于模m同余。记为如果余数不同，则称a与b对于模m不同余。记为注：注：mod是英语是英语modulo(对对模模)的缩写的缩写2025/7/84 42 2、判断、判断a,b对模对模m同余
4、同余定义定义3.13.1同余的概念及其基本性质同余的概念及其基本性质 定理定理1 1 整数整数a,b对对m同余的充要条件是同余的充要条件是注：下面的三个表示是等价的：注：下面的三个表示是等价的：2025/7/85 5二、同余的性质二、同余的性质3 3、同余关系是等价关系、同余关系是等价关系2025/7/86 6二、同余的性质二、同余的性质2025/7/87 7推广：推广：2025/7/88 85.2025/7/89 96.6.a b(mod m)，k 0，k N，则，则 1）ak bk(mod mk)；7.7.若若a b(mod mi)，1 i k，则，则 a b(mod m1,m2,mk)；
5、2025/7/810108.8.若若 a b(mod m)，d m，d 0，则则 a b(mod d)；9.9.若若a b(mod m)，则，则(a,m)=(b,m)；2025/7/811112025/7/81212解：依次计算对模解：依次计算对模641的同余数的同余数22 4（mod641）,24 16（mod641mod641）,28 256（mod641mod641）2025/7/813132025/7/814142025/7/81515例例5判断判断75312289能否被能否被7（9，11，13）整除。）整除。所以，所以，75312289不能被不能被7（11）整除，）整除，能被能被13
6、13整除整除2025/7/816162025/7/817172025/7/81818例例8 设设n的十进制表示是的十进制表示是 且且792 n，求求 x，y，z.解解 因为因为792=8911，故，故8 n，9 n及及11 n。9 n 9（1 3 x y 4 5 z）=19 x y 9 x y 1，(1)11 n 11（z 5 4 y x 3 1）=3 y x 11（3 y x）。(2)即有即有 x y 1=9或或18，3 y x=0或或11解方程组，得到解方程组，得到x=8，y=0，z=6。2025/7/81919五、弃九法五、弃九法验算计算结果验算计算结果应用这种方法可以验算较大整数的乘法
7、应用这种方法可以验算较大整数的乘法。例例9.9.验算验算 2899739495289973949511452364151145236415是否正确。是否正确。注：若结论成立，其结果不一定正确；注：若结论成立，其结果不一定正确；所以结果不正确。所以结果不正确。也可以检查和、差的运算。也可以检查和、差的运算。2025/7/820202025/7/821213.2 3.2 剩余类与完全剩余系剩余类与完全剩余系 引言引言 一个整数被正整数一个整数被正整数n除后，余数有除后，余数有n种情形：种情形：0 0，1 1，2 2，3 3，n-1-1，它们彼此对模，它们彼此对模n不同余。这不同余。这表明，每个整
8、数恰与这表明，每个整数恰与这n个整数中某一个对模个整数中某一个对模n同同余。这样一来，按模余。这样一来，按模n是否同余对整数集进行分类，是否同余对整数集进行分类，可以将整数集分成可以将整数集分成n个两两不相交的子集。个两两不相交的子集。2025/7/822223.2 3.2 剩余类与完全剩余系剩余类与完全剩余系 一、一、剩余类剩余类 按余数的不同对整数分类按余数的不同对整数分类 是模是模m的一个剩余类，的一个剩余类，即即 余数相同的整数构成余数相同的整数构成m的的一个剩余类。一个剩余类。注：一个剩余类中任意一个数称为它同类注：一个剩余类中任意一个数称为它同类的数的剩余。的数的剩余。1.1.剩余
9、类剩余类 2025/7/82323K0(5)=nn 0(mod 5)，n Z K1(5)=nn 1(mod 5)，n Z K2(5)=nn 2(mod 5)，n Z K3(5)=nn 3(mod 5)，n Z K4(5)=nn 4(mod 5)，n Z 模模5 5的五个剩余类是的五个剩余类是2025/7/824242.2.定理定理1 1 2025/7/82525二、完全剩余系二、完全剩余系1.1.定义定义2 2 完全剩余系不唯一；完全剩余系不唯一；若把剩余系作为一个集合，则同一剩余类里若把剩余系作为一个集合，则同一剩余类里的整数，看作同一元素。的整数，看作同一元素。注：注：模模m的一个完全剩余
10、系有且仅有的一个完全剩余系有且仅有m个整数；个整数；2025/7/826262.2.定义定义3 3：集合集合0,6,7,13,24是模是模5的一个完全剩余系，的一个完全剩余系，如，集合如，集合0,1,2,3,4是模是模5的最小非负完全剩余系。的最小非负完全剩余系。叫做模叫做模m的绝对最小完全剩余系。的绝对最小完全剩余系。叫做模叫做模m的绝对最小完全剩余系。的绝对最小完全剩余系。0,1,2,m 1这这m个整数个整数叫做模叫做模m的最小非负的最小非负完全剩余系；完全剩余系；2025/7/82727例例1 1 写出模写出模7 7（或（或8 8）的）的最小非负完全剩余系和最小非负完全剩余系和绝对绝对最
11、小完全剩余系最小完全剩余系模模7的绝对最小完全剩余系为的绝对最小完全剩余系为-3,-2,-1,0,1,2,3解：解：模模7 7的的最小非负完全剩余系为最小非负完全剩余系为0,1,2,3,4,5,60,1,2,3,4,5,62025/7/828283 3、完全剩余系的构造、完全剩余系的构造推论推论 m个整数作成模个整数作成模m的完全剩余系的充要条件是的完全剩余系的充要条件是两两对模两两对模m不同余。不同余。注：由定理注：由定理1 1及定义及定义2 2易得证。易得证。思考思考：1 1、既然完全剩余系是不唯一的，不同的剩余系、既然完全剩余系是不唯一的，不同的剩余系 之间存在什么关系呢？之间存在什么关
12、系呢？2 2、一个完全剩余系的所有元素通过线性变换、一个完全剩余系的所有元素通过线性变换后，还是完全剩余系吗？后，还是完全剩余系吗？2025/7/82929检验：设检验：设x1,x2,xm是模是模m的一个完全剩余系，的一个完全剩余系，那么，那么，b+x1,b+x2,b+xm和和 ax1,ax2,axm是模是模m的一个完全剩余系吗？的一个完全剩余系吗？2025/7/83030定理定理2设设m 1，a，b是整数，是整数，(a,m)=1，x1,x2,xm是模是模m的一个完全剩余系，则的一个完全剩余系，则ax1 b,ax2 b,axm b也是模也是模m的完全剩余系。的完全剩余系。证明证明 由定理由定理
13、1，只需证明：若，只需证明：若xi xj，则则 axi b axj b(mod m)。假设假设 axi b axj b(mod m)，则则 axi axj(mod m)，且且(a,m)=1，xi xj(mod m)由由3.13.1中的结论中的结论,P50,P50第三行知：第三行知：2025/7/83131注意：注意：(2)(2)在定理在定理2 2中，条件中，条件(a,m)=1不可缺少，否则不能不可缺少，否则不能 成立；成立；(3)定理定理2也可以叙述为：设也可以叙述为：设m 1，a，b是整数，是整数，(a,m)=1，若若x通过模通过模m的一个完全剩余系，的一个完全剩余系，则则ax+b也通过模也
14、通过模m的一个完全剩余系；的一个完全剩余系；（4）特别地，若）特别地，若x通过模通过模m的一个完全剩余系，的一个完全剩余系，(a,m)=1,则则ax和和x+b也分别通过模也分别通过模m的一的一 个完全剩余系。个完全剩余系。(1)(1)任意任意m m个连续整数都能构成模个连续整数都能构成模m m的一个完全剩余系的一个完全剩余系；2025/7/83232例例1 设设p 5是素数，是素数，a 2,3,p 1，则，则在数列在数列a，2a，3a，(p 1)a，pa中有且仅有中有且仅有一个数一个数b，满足，满足 b 1(mod p).证证 ：因为因为1，2，3，(p 1)，p是模是模p的的 一个完全剩余系
15、一个完全剩余系，所以所以a，2a，3a，(p 1)a，pa构成模构成模p的的 一个完全剩余系。一个完全剩余系。因此必有唯一的数因此必有唯一的数b满足式满足式b 1(mod p)。2025/7/83333例例2 设设A=x1,x2,xm是模是模m的一个完全剩余系，的一个完全剩余系，以以x表示表示x的小数部分，证明：若的小数部分，证明：若(a,m)=1，则，则 证：证：当当x通过模通过模m的完全剩余系时，的完全剩余系时，ax b也通过也通过模模m的完全剩余系，的完全剩余系，因此对于任意的因此对于任意的i（1 i m），），axi b一定与且只与一定与且只与某个整数某个整数j（1 j m）同余，）
16、同余，即存在整数即存在整数k，使得，使得 axi b=km j，（，（1 j m）2025/7/83434定理定理3 若若m1,m2 N，(m1,m2)=1，当当x1与与x2分别通过分别通过 模模m1与模与模m2的完全剩余系时，的完全剩余系时，则则 m2x1 m1x2通过模通过模m1m2的完全剩余系。的完全剩余系。4 4、剩余系间的联系、剩余系间的联系2025/7/83535例例3 设设m 0是偶数，是偶数，a1,a2,am与与b1,b2,bm都是模都是模m的完全剩余系，的完全剩余系，则则a1 b1,a2 b2,am bm不是模不是模m的完全剩余系。的完全剩余系。证证 由由1,2,m与与a1,
17、a2,am都是模都是模m的完全的完全剩余系，剩余系，如果如果a1 b1,a2 b2,am bm是模是模m的完全剩余系，的完全剩余系，不可能！不可能！2025/7/83636例例4 设设mi N（1 i n），则当），则当xi通过模通过模mi（1 i n）的完全剩余系时，的完全剩余系时，x=x1 m1x2 m1m2x3 m1m2 mn 1xn通过模通过模m1m2 mn的完全剩余系。的完全剩余系。证明证明 对对n施行归纳法。施行归纳法。当当n=2时，结论成立。时，结论成立。假设定理结论当假设定理结论当n=k时成立，时成立，即当即当xi（2 i k 1）分别通过模）分别通过模mi的完全剩余系时，的完
18、全剩余系时，y=x2 m2x3 m2m3x4 m2 mkxk 1通过模通过模m2m3mk 1的完全剩余系。的完全剩余系。2025/7/83737y=x2 m2x3 m2m3x4 m2 mkxk 1通过模通过模m2m3 mk 1的完全剩余系。的完全剩余系。由定理由定理3，当，当x1通过模通过模m1的完全剩余系，的完全剩余系，xi（2 i k 1）通过模）通过模mi的完全剩余系时，的完全剩余系时，x1 m1y=x1 m1(x2 m2x3 m2 mkxk 1)=x1 m1x2 m1m2x3 m1m2 mkxk 1通过模通过模m1m2 mk 1的完全剩余系。的完全剩余系。即结论对于即结论对于n=k 1
19、也成立。也成立。2025/7/838382025/7/839393.3 3.3 简化剩余系与欧拉函数简化剩余系与欧拉函数 一、基本概念一、基本概念定义定义1 设设R是模是模m的一个剩余类，若有的一个剩余类，若有a R，使得，使得(a,m)=1，则称，则称R是模是模m的一个简化剩余类的一个简化剩余类。即与模即与模m互质的剩余类。互质的剩余类。注：若注：若R是模是模m 的简化剩余类，则的简化剩余类，则R中的数都与中的数都与m互素。互素。例如，模例如，模4的简化剩余类有两个：的简化剩余类有两个：R1(4)=,7,3,1,5,9,，R3(4)=,5,1,3,7,11,。2025/7/84040定义定义
20、2 对于正整数对于正整数k，令函数，令函数(k)的值等于模的值等于模k的所有的所有简化剩余类的个数，称简化剩余类的个数，称(k)为为Euler函数。函数。容易验证：容易验证：(2)=1，(3)=2，(4)=2，(7)=6。注注:(1)(m)就是在就是在m的一个完全剩余系中与的一个完全剩余系中与m互素的互素的 整数的个数，整数的个数，2025/7/84141定义定义3 对于正整数对于正整数m，从模，从模m的每个简化剩余类中的每个简化剩余类中 各取一个数各取一个数xi，构成一个集合，构成一个集合x1,x2,x(m)，称为模称为模m的一个简化剩余系（或简称为简化系）。的一个简化剩余系（或简称为简化系
21、注：由于选取方式的任意性，模注：由于选取方式的任意性，模m的简化剩余系的简化剩余系有无穷多个。有无穷多个。例如，集合例如，集合9,5,3,1是模是模8的简化剩余系；的简化剩余系；集合集合1,3,5,71,3,5,7也是模也是模8 8的简化剩余系的简化剩余系.集合集合1,3,5,71,3,5,7称为模称为模8 8的最小非负简化剩余系。的最小非负简化剩余系。注：模注：模m的任意一组简化剩余系中有的任意一组简化剩余系中有(m m)个整数个整数 2025/7/84242二、主要性质二、主要性质 1.定理定理1 整数集合整数集合A是模是模m的简化剩余系的充要条件是：的简化剩余系的充要条件是：A中含有
22、中含有(m)个整数；个整数；A中的任何两个整数对模中的任何两个整数对模m不同余；不同余；A中的每个整数都与中的每个整数都与m互素。互素。说明：简化剩余系是某个完全剩余系中的部分元素说明：简化剩余系是某个完全剩余系中的部分元素构成的集合，故满足条件构成的集合，故满足条件2；由定义由定义1易知满足条件易知满足条件3；由定义由定义3 3易知满足条件易知满足条件1 1。2025/7/843432.定理定理2 若若a1,a2,a(m)是是(m)个与个与m互质的整数，且两两对模互质的整数，且两两对模m不同余，不同余，则则a1,a2,a(m)是模是模m的一个简的一个简化系。化系。(留做练习留做练习)2025
23、/7/844443.定理定理3 设设a是整数，是整数，(a,m)=1，B=x1,x2,x(m)是模是模m的简化剩余系，则集合的简化剩余系，则集合 A=ax1,ax2,ax(m)也是模也是模m的简化剩余系。的简化剩余系。证明证明:1)显然，集合显然，集合A中有中有(m)个整数。个整数。2)由于由于(a,m)=1，对于任意的对于任意的xi（1 i (m)），xi B，有有(axi,m)=(xi,m)=1。故故A中的每一个数都与中的每一个数都与m互素。互素。3)A中的任何两个不同的整数对模中的任何两个不同的整数对模m不同余。不同余。因为，若有因为，若有x ,x B，使得，使得 a x ax (mod
24、 m)，那么，那么，x x (mod m)，于是于是x =x 。由以上结论及定理由以上结论及定理1可知集合可知集合A是模是模m的一个简化系。的一个简化系。注注:条件条件(a,m)=1不可少。不可少。2025/7/84545注：在定理注：在定理3的条件下，若的条件下，若b是整数，集合是整数，集合ax1 b,ax2 b,ax(m)b不一定是模不一定是模m的简化剩余系。的简化剩余系。例如，取例如，取m=4，a=1，b=1，以及模以及模4的简化剩余系的简化剩余系1,3。但但2 2，4 4不是模不是模4 4的简化剩余系。的简化剩余系。2025/7/846464.定理定理4 设设m1,m2 N，(m1,m
25、2)=1，又设，又设分别是模分别是模m1与与m2的简化剩余系，的简化剩余系，则则 A=m1y m2xx X，y Y 是模是模m1m2的简化剩余系。的简化剩余系。证明证明 由第二节定理由第二节定理3 3可知，可知，若以若以X 与与Y 分别表示分别表示 模模m1与与m2的完全剩余系，使得的完全剩余系，使得X X ，Y Y ，则则A =m1y m2xx X ，y Y 是模是模m1m2的完全的完全 剩余系。剩余系。因此只需证明因此只需证明A 中所有与中所有与m1m2互素的整数的集合互素的整数的集合R 即模即模m1m2的简化剩余系是集合的简化剩余系是集合A。2025/7/84747若若m1y m2x R
26、则，则(m1y m2x,m1m2)=1，所以所以(m1y m2x,m1)=1，于是于是 (m2x,m1)=1，(x,m1)=1，x X。同理可得到同理可得到y Y，因此，因此m1y m2x A。这说明这说明R A。另一方面，若另一方面，若m1y m2x A，则，则x X，y Y，即即 (x,m1)=1，(y,m2)=1。由此及由此及(m1,m2)=1得到得到 (m2x m1y,m1)=(m2x,m1)=1(m2x m1y,m2)=(m1y,m2)=1。因为因为m1与与m2互素，所以互素，所以(m2x m1y,m1m2)=1，于是于是m2x m1y R。因此。因此A R。从而从而A=R。202
27、5/7/84848推论推论 设设m1,m2 N,(m1,m2)=1,则则(m1m2)=(m1)(m2)证证 由定理由定理4知，若知，若x1,x2分别通过分别通过m1,m2的简化剩余系，的简化剩余系，则则m1x2 m2x1通过通过m1m2的简化剩余系，的简化剩余系，即有即有 m1x2 m2x1通过通过(m1m2)个整数。个整数。另一方面，另一方面，x1m2x1通过通过(m1)个整数，个整数，x2m1x2通过通过(m2)个整数个整数,从而从而m1x2 m2x1通过通过(m1)(m2)个整数。个整数。故有故有 (m1m2)=(m1)(m2)。注：可以推广到多个两两互质数的情形。注：可以推广到多个两两
28、互质数的情形。2025/7/84949注：由上式立即得到注：由上式立即得到若若n=2m，（，（2，m）=1，则，则(n)=(m)；若若m是奇数，则是奇数，则(4m)=2(m)。2025/7/850505.定理定理5 设设n是正整数，是正整数，p1,p2,pk是它的全部素因数，是它的全部素因数，证证 设设n的标准分解式是的标准分解式是 由定理由定理4 4推论得到推论得到 对任意的素数对任意的素数p，(p)等于数列等于数列1,2,p 中与中与p 互素的整数的个数，互素的整数的个数，从而定理得证。从而定理得证。2025/7/85151证：证：显然显然mn与与m,n有相同的素因数，有相同的素因数，设它
29、们是设它们是pi（1 i k），则），则由此两式及由此两式及mn=(m,n)m,n即可得证。即可得证。例例2.2.证明：若证明：若m,n N，则，则(mn)=(m,n)(m,n)三、应用举例三、应用举例2025/7/85252例例3 设设n N，证明：，证明：1)若若n是奇数，则是奇数，则(4n)=2(n)；的充要条件是的充要条件是n=2k，k N；的充要条件是的充要条件是n=2k3l，k,l N；4)若若6 n，则，则(n)2025/7/853531)若若n是奇数，则是奇数，则(4n)=2(n)；(4n)=(22n)=(22)(n)=2(n)2025/7/85454的充要条件是的充要条件是n
30、2k，k N；若若n=2k，若若(n)=设设n=2kn1，由由 (n)=(2kn1)=(2k)(n1)=2k 1(n1)所以所以n1=1，即，即n=2k；2025/7/85555的充要条件是的充要条件是n=2k3l，k,l N；设设 n=2k3ln1，所以所以n1=1，即，即n=2k3l；若若 n=2k3l，则则 (n)=(2k)(3l)2025/7/856564)若若6 n，则，则(n)设设 n=2k3ln1，则则 (n)=(2k)(3l)(n1)2025/7/857572025/7/858583.43.4欧拉定理欧拉定理 费马定理及其对循环小数的应用费马定理及其对循环小数的应用 本节主要
31、通过应用简化剩余系的性质证明本节主要通过应用简化剩余系的性质证明数论中的两个重要定理，欧拉定理和费马定理数论中的两个重要定理，欧拉定理和费马定理,并说明其在理论和解决实际问题中的应用。并说明其在理论和解决实际问题中的应用。2025/7/85959一、两个基本定理一、两个基本定理定理定理1 Euler 设设 m是正整数，是正整数，(a,m)=1，则则 a m)1(mod m).证明：证明：设设x1,x2,x(m)是模是模m的一个简化剩余系，的一个简化剩余系，则则ax1,ax2,ax(m)也是模也是模m的简化剩余系，的简化剩余系，所以所以 ax1ax2 ax(m)x1x2 x(m)(mod m)，
32、即即 a(m)x1x2 x(m)x1x2 x(m)(mod m).得得 (x1x2 x(m),m)=1，所以所以 a(m)1(mod m).2025/7/86060定理定理2(Fermat)设设p是素数，是素数，a p a(mod p)。注：注：FermatFermat定理即是欧拉定理的推论。定理即是欧拉定理的推论。证：证：由于由于p是素数，是素数，若若(a,p)1，则由定理则由定理1 1得到得到 a p 1 1(mod p)a p a(mod p)若若(a,p)1，则，则p a，所以所以 a p 0 a(mod p)a m)1(mod m)2025/7/86161注注:根据欧拉定理，当根据欧
33、拉定理，当(a,m)=1时，时，总能找到总能找到x=(m)，使得，使得ax 1(mod m)。但但(m)并不是使并不是使ax 1(mod m)成立的自成立的自然数然数x中的最小数。中的最小数。2025/7/86262二、定理的应用举例二、定理的应用举例例例1 求求131956 被被60除的余数。除的余数。a m)1(mod m)即即 131956被被60除的余数为除的余数为1。解：解：2025/7/86363练习练习 求求313159被被7除的余数。除的余数。所以由欧拉定理得所以由欧拉定理得 a m)1(mod m)从而从而 5159=(56)2653 53(mod 7)53=25 5 4 5
34、 6(mod 7)。即即 313159被被7除的余数为除的余数为6。解：解：3131592025/7/86464a m)1(mod m)即即 所求余数为所求余数为52025/7/86565例例3 如果今天是星期一，再过如果今天是星期一，再过101010天是星期几？天是星期几？即得：再过即得：再过101010天是星期五。天是星期五。解：解：2025/7/86666三、在分数与小数互化中的应用三、在分数与小数互化中的应用 有理数，即有限小数和无限循环小数，可以用有理数，即有限小数和无限循环小数，可以用分数来表示。利用欧拉定理可以解决分数、小数的分数来表示。利用欧拉定理可以解决分数、小数的转化问题。
35、转化问题。1.1.定义定义 如果对于一个无限小数如果对于一个无限小数 则称之为循环小数，并简记为则称之为循环小数，并简记为 注：注：若找到的若找到的t是最小的，则称是最小的，则称 为循环节；为循环节；t称为循环节的长度；若最小的称为循环节的长度；若最小的s0，则称该小数为纯循环小数，否则为混循环小数。则称该小数为纯循环小数，否则为混循环小数。2025/7/867672.2.定理定理3 3 有理数有理数 能表示为能表示为纯纯循环小数循环小数 即：分母不含质因数即：分母不含质因数2 2或或5 5。2025/7/86868定理定理3 3 有理数有理数 能表示为能表示为纯纯循环小数循环小数 (b,10
36、)=1 由由Euler定理可知，有正整数定理可知，有正整数k，使得，使得10k 1(mod b)，0 k (b)，因此存在整数因此存在整数q使得使得 而且而且ak,a1不能都等于不能都等于0，也不能都等于，也不能都等于9。=0.akak 1a1akak 1a1。2025/7/869693.定理定理4 设设a与与b是正整数，是正整数，0 a b，(a,b)=1，并且并且 b=2 5 b1，(b1,10)=1，b1 1，此处此处 与与 是不全为零的正整数，是不全为零的正整数，其中不循环的位数码个数是其中不循环的位数码个数是 =max=max .则则 可以表示成可以表示成混混循环小数，循环小数，证明
37、不妨假设证明：不妨假设 =，其中其中0 a1 b1，0 M 10，且且(a1,b1)=(2 a Mb1,b1)=(2 a,b1)=(a,b1)=1。因此，由定理因此，由定理3，可以表示成纯循环小数：可以表示成纯循环小数：2025/7/87070M=m110 1 m210 2 m（0 mi 9，1 i ），），下面说明，上式中的下面说明，上式中的 是最小的不循环位数码的个数。是最小的不循环位数码的个数。若不然，设又有正整数若不然，设又有正整数，2025/7/87171由定理由定理3 3有有 其中其中 b1 ，10 ab1 =ba。上式右端可以被上式右端可以被5 整除，整除，但是但是(a,10)
38、1，(b1,10)=1，所以所以5 ，。这就证明了不循环位数码个数不能再少了。这就证明了不循环位数码个数不能再少了。2025/7/87272证明：证明：4.4.2025/7/87373证明：证明：5.5.2025/7/874742025/7/875753.53.5公开钥匙公开钥匙RSARSA体制体制 2025/7/87676 该算法于该算法于1977年由美国麻省理工学院年由美国麻省理工学院mit(massachusetts institute of technology)的的ronal rivest，adi shamir和和len adleman三位年轻教授提出，并以三三位年轻教授提出，并以
39、三人的姓氏人的姓氏rivest，shamir和和adlernan命名为命名为rsa算法。算法。该算法利用了数论领域的一个事实，那就是虽然把该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数却十分困难。合数分但要把一个合数分解为两个质数却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题，至解问题目前仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法。与今没有任何高效的分解方法。与diffie-hellman算法相算法相比，比，rsa算法具有明显的优越性，因为它无须
40、收发双方算法具有明显的优越性，因为它无须收发双方同时参与加密过程，且非常适合于电子函件系统的加同时参与加密过程，且非常适合于电子函件系统的加密。密。2025/7/87777RSARSA中的密钥中的密钥RSARSA中的加密与解密中的加密与解密2025/7/87878RSARSA中密钥中参数的选择中密钥中参数的选择2025/7/87979RSARSA中密钥中参数的选择（示例一）中密钥中参数的选择（示例一）2025/7/88080RSARSA中密钥中参数的选择（示例二）中密钥中参数的选择（示例二）2025/7/88181RSARSA安全性取决于对模安全性取决于对模n n因数分解的困难性。因数分解的困
41、难性。19991999年年8 8月，荷兰国家数学与计算机科学研究所的一月，荷兰国家数学与计算机科学研究所的一组科学家成功分解了组科学家成功分解了512bit512bit的整数，大约的整数，大约300300台高速台高速工作站与工作站与PCPC机并行运行，整个工作花了机并行运行，整个工作花了7 7个月。个月。19991999年年9 9月，以色列密码学家月，以色列密码学家Adi ShamirAdi Shamir设计了一种设计了一种名叫名叫“TWINKLE”TWINKLE”的因数分解设备，可以在几天内攻的因数分解设备，可以在几天内攻破破512bit512bit的的RSARSA密钥。（但要做到这一点，需要密钥。（但要做到这一点，需要300-300-400400台设备，每台设备价值台设备，每台设备价值50005000美圆）。美圆）。RSARSA算法的安全性算法的安全性2025/7/88282
免费区 
