第2章-数学基础-网络10课件.pptVIP

第二章 数学基础;2.1数论基础;2.1.1 因子;定义2.1.3 设a, b, c∈Z，如果a |c且b| c，c≥1，则称c为a和b的公倍数。特别地，把a和b的所有公倍数中最小的，称为a和b的最小公倍数，记作lcm(a,b)。 可以证明a和b的最大公因子必然存在，且唯一； a和b的最小公倍数一定存在，且唯一。 例如：gcd(12，60)=12 lcm(15，20，30)=60 ;2.1.2素数;定理2.1.1 （算术基本定理）任何一个整数m（1） ，都存在唯一的因数分解形式： m=p1e1p2e2……pnen 其中ei ∈N，pi均为素数且p1p2……pn，又称为m的标准分解形式。 例如： 6=21×31×50， 20=22×3 0×51， 100=22×30×52 ;定义2.1.6 Euler函数（欧拉函数）是定义在正整数上的函数，它在正整数m的值等于1，2，...，i，...，m-1中与m互素的数的个数，记作φ(m)。 例如m=6，{1，2，3，4，5}中与m互素的数为{1，5}，则有： φ(m)= φ(6)=2 定理2.1.2 设正整数m的标准分解形式为： m=p1e1p2e2……pnen 则 φ(m)= m(1-1/p1) (1-1/p2)… (1-1/pn) 例如m=6， 其标准分解形式为6=21×31 因此，φ(m)= φ(6)=6×(1-1/2) (1-1/3)=2。;定理2.1.3 Euler定理（欧拉定理）若整数a和m互素，则 a φ(m) ≡1 (mod m) 例如a=3，m=10 由定理2.1.2，10=21×51，因此 φ(m)= φ(10)=10×(1-1/2) (1-1/5)=4 代入定理2.1.3公式中有： aφ(m)=34=81≡1 (mod 10) ≡1 (mod m);用算术基本定理求最大公因/倍数 ;2.1.3 Eulid（欧几里德）算法 ;定理2.1.6（Eulid算法）又称辗转除法，给定整数a和b且 b0，反复使用带余数除法，得等式如下： a=bq1+r1 0r1b b=r1q2+r2 0r2r1 r1=r2q3+r3 0r3r2 … rn-2=rn-1qn+rn 0rnrn-1 rn-1=rnqn+1+rn+1 rn+1=0 则有： gcd(a,b)= rn 重复使用带余数除法（即用每次的余数做除数去除上一次的除数）。每进行一次带余数除法，余数会递减，而b是有限的，因此经过一定次数的带余数除法，余数变为0。 最后一个不为0的余数rn就是a和b的最大公因数。;例：求gcd (666，1414)=？ 【解】 用欧几里德算法的计算过程如下： 1414＝2×666+82 666＝8×82+10 82＝10×8+2 10＝ 5×2+0 因此gcd (666，1414) = 2 ;进行回代： 2=82-10×8=82- (666-8×82)×8 =65×82-666×8 =65×(1414-666×2)-666×8 =65×1414-138×666 故：2=65×1414-138×666 与定理2.1.5中ua+bv= gcd(a,b)相对应： 2 = 65×1414-138×666 即 gcd(666, 1414) = 65×1414-138×666 因此 a=1414，b=666， u =65，v=-138 由此可见，gcd(a,b)可以以线性形式ua+bv表达。;例：求gcd (1970，1066)=？ 【解】 用欧几里德算法的计算过程如下： 1970＝1×1066+904 1066＝1×904+162 904＝5×162+94 162＝ 1×94+68 94＝1×68+26 68＝2×26+16 26＝1×16+10 16＝1×10+6 10＝1×6+4 6＝ 1×4+2 4＝2×2+0 因此gcd (1970，1066) = 2 ;进行回代： 2=6-1×4=6-1×(10-1×6)=6-10+1×6=2×6-10 =2×(16-1×10)-10=2×16-2×10-10=2×16-3×10 =2×16-3×(26-1×16)=2×16-3×26+3×16