离散数学课件第2章.ppt

《离散数学课件第2章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1离散数学DiscreteMathematics汪荣贵教授合肥工业大学软件学院专用课件2010.047/30/20211第二章算法基础7/30/202122.1Algorithms算法2.2ComplexityofAlgorithms算法的复杂性2.3TheIntegersandDivision整数和除法2.4IntegersandAlgorithm整数和算法2.5ApplicationsofNumberTheory数论的应用2.6Matrices矩阵2.7Recursion递归学习内容7/30/20213基础知识中国余数定理大整数的运算技巧伪素数密码学应用数论的应用7

2、/30/20214定理1若a和b为正整数，则存在整数s和t，使gcd（a，b）=sa+tb基础知识最大公因数的基本性质7/30/202157/30/20216引理1如果a，b和c为正整数，使得gcd（a，b）=1且a

3、bc，那么a

4、c7/30/20217引理2如果p是素数，且p

5、a1a2…an，其中ai为整数，则对于某个i，p

6、ai基础知识由数学归纳法及引理1易证：7/30/20218定理2令m为整数，a，b和c为整数。如果ac≡bc（modm）且gcd（c，m）=1，那么a≡b（modm）。基础知识7/30/20219线性同余形为ax≡b（modm）的同余式.m为正整

7、数，a和b为整数，x为变量如果aa-≡1(modm),a-称为a的模m逆线性同余7/30/202110定理3如果a和m为互素的整数，m>1,则存在a的模m逆。而且这个a的模m逆是唯一的。（即有小于m的唯一正整数a-，它是a的模m逆，且a的任何别的模m逆均和a-模m同余1）线性同余7/30/202111证：由定理1及gcd（a，m）=1知有整数s和t，成立：sa+tm=1于是sa+tm=1(modm)由于tm=0（modm）所以sa≡1（modm）s为a的模m逆7/30/202112例求3模7的逆解由于gcd(3,7)=1,由定理3知存在3模7的逆7=2×3+1-2×3+

8、1×7=1所以：-2是3模1的一个逆线性同余7/30/202113给出一个在a和m互素的条件下，求a的模m逆的方法：求a和m的线性组合使之等于1；这一线性组合中a的系数就是a模m的一个逆线性同余7/30/202114例线性同余3x≡4(mod7)的解是什么？解从上例知道-2是3模7的逆。在同余式同乘以-2得：-2×3x=-2×4（mod7）因为-6≡1(mod7)且-8≡6（mod7），所以若x是解，必有x≡-8≡6（mod7）。验证：3x≡3×6=18≡4(mod7)6,13,20,…及-1，-8，-15线性同余7/30/202115基础知识中国余数定理大整数的运算技

9、巧伪素数密码学应用数论的应用7/30/202116定理4令m1,m2,..,mn为两两互素的正整数，则同余方程组x≡a1（modm1）x≡a2（modm2）x≡an（modmn）有唯一的模m=m1m2…mn的解。（即有一个解x，使0≤x

10、有方程的解，令x≡a1M1y1+a2M2y2+…+anMnyn7/30/202118现在证明x就是所求的一个解。由于只要j≠k，就有Mj=0（modmk）x的计算式中除第k项以外的各项模mk均同余于0.由于Mkyk≡1（modmk），我们看到，对k=1,2,…,n,均有x≡akMkyk≡ak(modmk)所以，x是这n个同余方程的同一解。中国余数定理7/30/202119例一世纪时，中国数学家孙聪问道：某物不知其数，三分之余二，五分之与三，气分之余而，此物几何？这一问题可以翻译成：求同余方程组x≡2(mod3)x≡3(mod5)x≡2(mod7)的解中国余数定理7/30

11、/202120解令m=3×5×7=105，M1=m/3=35,M2=m/5=21,M3=m/7=15.2是M1=35的模3逆，因为35≡2（mod3）1是M2=21的模5的逆，因为21≡1(mod5)1也是M3=15的模7逆，因为15≡1（mod7）于是这一方程组的解是那些满足下式的x：x≡a1M1y1+a2M2y2+a3M3y3=2×35×2+3×21×1+2×15×1（mod105）=233≡23(mod105)23是所有解中最小正整数，被3除时余2，被5除时余3，被7除时余27/30/202121基础知识中国余数定理大整数的运算技巧