离散数学课件-第2章.pptxVIP

2025/4/2211离散数学DiscreteMathematics汪荣贵教授合肥工业大学软件学院专用课件2010.04

2025/4/222第二章算法基础

学习内容2025/4/223Algorithms算法1ComplexityofAlgorithms算法的复杂性2TheIntegersandDivision整数和除法3IntegersandAlgorithm整数和算法4ApplicationsofNumberTheory数论的应用5Matrices矩阵6Recursion递归7

数论的应用02基础知识中国余数定理大整数的运算技巧伪素数密码学应用01

基础知识最大公因数的基本性质定理1若a和b为正整数，则存在整数s和t，使gcd（a，b）=sa+tb12

2025/4/226

引理1如果a，b和c为正整数，使得gcd（a，b）=1且a|bc，那么a|c

基础知识由数学归纳法及引理1易证：引理2如果p是素数，且p|a1a2…an，其中ai为整数，则对于某个i，p|ai12

定理2令m为整数，a，b和c为整数。如果ac≡bc（modm）且gcd（c，m）=1，那么a≡b（modm）。基础知识

线性同余形为ax≡b（modm）的同余式.m为正整数，a和b为整数，x为变量如果aa-≡1(modm),a-称为a的模m逆01线性同余02

定理3如果a和m为互素的整数，m1,则存在a的模m逆。而且这个a的模m逆是唯一的。（即有小于m的唯一正整数a-，它是a的模m逆，且a的任何别的模m逆均和a-模m同余1）线性同余12

证：2025/4/2212由定理1及gcd（a，m）=1知有整数s和t，成立：1sa+tm=12于是3sa+tm=1(modm)4由于tm=0（modm）所以5sa≡1（modm）6s为a的模m逆7

例求3模7的逆解由于gcd(3,7)=1,由定理3知存在3模7的逆7=2×3+12×3+1×7=1所以：-2是3模1的一个逆01线性同余02

给出一个在a和m互素的条件下，求a的模m逆的方法：

求a和m的线性组合使之等于1；这一线性组合中a的系数就是a模m的一个逆线性同余

例线性同余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线性同余

基础知识中国余数定理大整数的运算技巧伪素数密码学应用数论的应用12

中国余数定理2025/4/2217定理4令m1,m2,..,mn为两两互素的正整数，则同余方程组x≡a1（modm1）x≡a2（modm2）x≡an（modmn）有唯一的模m=m1m2…mn的解。（即有一个解x，使0≤xm，且所有其他的解均与次解模m同余）

证明：要构造一个适合各方程的解，首先对k=1,2,…,n,令MK=m/mk,即Mk是除mk以外所有模数的乘积。由于i≠k时，mi和mk没有大于1的公因子，所以gcd（mk，Mk）=1。从而由定理3知有Mk模mk的逆，整数yk，使得Mkyk=1（modmk）要得到合适所有方程的解，令x≡a1M1y1+a2M2y2+…+anMnyn

中国余数定理2025/4/2219现在证明x就是所求的一个解。由于只要j≠k，就有Mj=0（modmk）x的计算式中除第k项以外的各项模mk均同余于0.由于Mkyk≡1（modmk），我们看到，对k=1,2,…,n,均有x≡akMkyk≡ak(modmk)所以，x是这n个同余方程的同一解。

中国余数定理2025/4/2220例一世纪时，中国数学家孙聪问道：某物不知其数，三分之余二，五分之与三，气分之余而，此物几何？这一问题可以翻译成：求同余方程组x≡2(mod3)x≡3(mod5)x≡2(mod7)的解

解令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除时余2

数论的应用基础知识中国余数定理大整数的运算技巧寻找伪素数密码学应用