最大公因数、辗转相除法、整除性质、最小公倍数ppt课件.ppt

最大公因数与辗转相除法整除的性质与最小公倍数,复习,带余数除法的内涵,它可以看作是整除的推广，也可以用带余除法定理来定义整除性将一个未知的整数表示为小于除数的余数，将整数进行分类，从而可将无限问题转化为有限问题其他应用：辗转相除法、进制间转换算法,2 最大公因数与辗转相除法,辗转相除法的应用,求出两个正整数的最大公因数推出最大公因数的重要性质解一次不定方程的基本工具,辗转相除法在密码学中的应用,RSA算法的重要部分还被用来解丢番图方程，寻找满足中国剩余定理得数，或者求有限域的倒数。还可以用来构造连分数，在一些整数分解算法中也有应用。同时在处理大数时非常高效，它需要的步骤不会超过较小数的位数（十进制下）的五倍。,辗转相除法求最大公约数问题,步骤：,时间复杂性：O(log n),3 整除的进一步性质及最小公倍数,作业2,1、辗转相除法求以下数组的最大公因数，并把它表为这些数的整系数线性组合（i）2947,3997 ；（ii）-1109,49992、设p是素数，(a,p2)=p,(b,p3)=p2,求(ab,p4),(a+b,p4)3、P9 1，P14 1,2,