最大公约数 oC Gcd greatest common devisors GCD递推定理:gcd(ab)=gcd(b, a mod b) ■定理:如果a和b是任意不等于0的整数,则 ■辗转相除法【如何说明其正确性?】 gcd(ab)=集合ax+byx,yin2}的最小整数 【证明!】 存在x和y使得 gcd(a, b)=xa+yb 互素: Relative prime integers ■西方人叫 Euclid算法 如果gcd(a,b)=1称a和b互素 ■唯一分解定理 法i e,p是素数单调升【是否可以通过 ■?如何证明有无穷多素数??【课堂提问】 清手大学城想 Euclid算法 扩展欧几里德算法 Euclid(a, b) Extended-Euclid(a, b) a If b=0 then return(a, 1, 0) Retum Euclid(b, a mod b) a(d, x, y)Extended-Euclid(b, a mod b) Steps of division: o(Ig a)=o(n) n is the bit length of Lame' s theorem:欧几里德算法迭代步数小于k,其 中F是第k个 Fibonaco数 证明提示:数学归纳法证明:如果a>b>=1而且上述 Euclid算法进行了k步递归,则a>=Fk*2andb>=F*t 手大学想 计算最大公约数及其线性组合表示 群的概念 b [a/b d x y 群(S,⊕) 91491 7 -1 2 X-a/bly 元 49421 -1 x-a/bly' 3.结合率 4276 701×-{a/b] 逆元 交换率:交换群= Abelian群 大学证制2 清华大学 宋斌恒 7 最大公约数 „ Gcd: greatest common devisors „ 定理：如果a和b是任意不等于0的整数，则 gcd(a,b)=集合{ax+by:x,y in Z}的最小整数。 【证明！】 „ 互素：Relative prime integers „ 如果gcd(a, b)=1称a和b互素 „ 唯一分解定理 „ a=Πi=1,…n (pi ei), pi 是素数单调升【是否可以通过 此方法计算gcd? 复杂度？】 „ ？如何证明有无穷多素数？？【课堂提问】 清华大学 宋斌恒 8 gcd „ GCD递推定理：gcd(a,b)=gcd(b,a mod b) „ 辗转相除法【如何说明其正确性？】 „ 存在x和y使得 gcd(a,b)=xa+yb。 „ 西方人叫Euclid算法 清华大学 宋斌恒 9 Euclid算法 1. Euclid(a,b) 1. If b==0 return a 2. Return Euclid(b,a mod b) „ Running time: „ Steps of division: O(lg a) = O(n) n is the bit length of a. „ Lame’s theorem: 欧几里德算法迭代步数小于k，其 中Fk是第k个Fibonacci数。 „ 证明提示：数学归纳法证明：如果a>b>=1而且上述 Euclid算法进行了k步递归，则a>= Fk+2 and b>= Fk+1 清华大学 宋斌恒 10 扩展欧几里德算法 „ Extended-Euclid(a,b) „ If b=0 then return (a,1,0) „ (d’,x’,y’)ÅExtended-Euclid(b,a mod b) „ Return (d’,y’,x’-[a/b]y’); 清华大学 宋斌恒 11 计算最大公约数及其线性组合表示 a b [a/b] d x y 140 91 1 7 2 -3 91 49 1 7 -1 2 x’-[a/b]y’ 49 42 1 7 1 -1 x’-[a/b]y’ 42 7 6 7 0 1 x’-[a/b]y’ 70- 710 清华大学 宋斌恒 12 群的概念？ „ 群(S，⊕ ) 1. 封闭性 2. 么元 3. 结合率 4. 逆元 交换率：交换群＝ Abelian群