研fmis-ch2-theoryofdivisibility-資料下載頁
2025-03-08 18:50本頁面
【正文】 r r? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?11,0.n n nr r q???????????????32 Euclid’ s Algorithm (2) Values of x and y in gcd(a, b)=ax + by = rn can be obtained by writing each ri as a linear bination of a and b. rn = rn?2 ? rn?1 qn?1=…= ax + by. 33 Euclid’ s Algorithm ? Remark . Euclid’ s algorithm is found in Book VII, Proposition 1 and 2 of his Elements(幾何原本 ), but it probably wasn’ t his own invention. Scholars believe that the method was known up to 200 years earlier. However, it first appeared in Euclid’ s Elements, and more importantly, it is first nontrivial algorithm that has survived to this day. ? Remark . If Euclid’ s algorithm is applied to two positive integers a and b with a b, then the number of divisions required to find gcd(a, b) is O(log b), a polynomialtime plexity. The bigO notation is used to denote the upper bound of a plexity function, ., f(n)=O (g(n)) if there exists some constant c 0 such that f(n)? c?g(n). 34 Euclid’ s Algorithm ? Example . Use Euclid’ s algorithm to find the gcd of 1281 and 243. Since 1281=243?5+66, 243=66?3+45, 66=45?1+21, 45=21?2+3, 21=3?7+0, we have gcd(1281, 243)=3, and 3=45?21?2=45?(66 ?45?1)?2 =45?3?66?2 =(243?66?3)?3?66?2 =243?3 ?66?11 =243?3 ?(1281?243?5)?11 =243?58 ?1281?11 = 1281x +243y, where x = ?11, y = 58. 35 Chapter 2 Theory of Divisibility Basic Concepts and Properties of Divisibility Fundamental Theorem of Arithmetic Mersenne Prime and Fermat Number Euclid’ s Algorithm Continued Fraction 36 Continued Fraction (連分數(shù) ) ? Definition . Let a and b be positive integers and let Euclid’ s algorithm run as a = b q0 + r1, b = r1 q1 + r2, r1 = r2 q2 + r3, r2 = r3 q3 + r4, … rn?2 = rn?1 qn?1 + rn, rn?1 = rn qn +0. nnqqqqqbaba1.... .. 111 :fract ion con tinu ed sim ple a as exp resse d becan fract ion Then the1210????? where q0, q1, …, qn?1, qn are called the partial quotients of the continued fraction. 37 Continued Fraction ].,... ,[11...11 asit trn usu all y wr is offrac tion con ti nued The12101210 nnnnqqqqqqqqqqbaba??????.712111315 ]7,2,1,3,5[2431281 So??????? Example . Expand the rational number 1281/243 as a continued fraction. First let a=1281 and b=243, and then let Euclid’ s algorithm run as follows: 1281=243?5+66, 243=66?3+45, 66=45?1+21, 45=21?2+3, 21=3?7+0. 38 Exercise 2 ? Exercise Let a , b and c be integers. Show that (1) 1 | 0, a | a, a | 0. (2) If a | b and b | a, then a = ? b. (3) If a | b and b | c, then for all integers m and n we have a |(mb + nc). (4) If a | b and a and b are positive integers, then ab. ? Exercise . If n is an integer ? 2, then there are no primes between n!+2 and n!+n. ? Exercise . Calculate gcd(1403, 549) using Euclid’ s algorithm. 39 Exercise 2 ? Exercise . Expand the rational numbers .fract ion gs con tinu ed th eas 23951 and 5123940 演講完畢，謝謝觀看！
研究報告相關推薦
鄂ICP備17016276號-1