course5.pdf(204kb)-tioj.pdfVIP

培訓 -5 算數 算數 Angrybird11 c2251393 momohuang October30,2013 1 數 1.1 公因數與最大公因數與互質 1.1.1 If and ,thendisthecommon divisorof a and b. GreatestCommonDivisor of a, b is writtenas gcd . aandbarerelatively prime iff gcd . 1.1.2 性質 1. and 2. gcd 3. gcd gcd 4. gcd gcd 5. gcd gcd 6. AnonymousTheorem: Ifaandbareintegers,notboth0,thengcd isthesmallestpos- itiveelementoftheset Proof: Let s be the smallest positive, s.t. s =ax + by. Let g gcd(a,b),itisobviousthatg|s. Nowwellshowthatsisacommon I 1.1 公因數與最大公因數與互質 算數 divisor of a and b, thus g =s. a mod s =a - qs =a(1-qx)+b(-qy). And0 amodss,soamod s =0. 7. and gcd . (Corollaryfrom6.) 8. ifn | abandgcd(a,n) =1, then n | b. (Corollary from 6.) 1.1.3 歐 gcd gcd gcd mod gcd 性質 lg(max(a,b)) 的 Algorithm1 EuclidAlgorithm 1: function Euclid( ) 2: if b 0 then 3: returna 4: else 5: returnEuclid(b,amod b) 6: endif 7: endfunction 1.1.4 歐 Target: 組 ax+by=gcd(a, b) 的數 的同歐 ax+by=g 的組 bx+(a mod b)y=g 的 bx+ (a-⌊ ⌋*b)y=g 因ay+b(x-⌊ ⌋*by)=g 因 b 0 x=1,y=0 Algorithm2 ExtendedEuclidAlgorithm 1: function Extended-Euclid( ) 2: if b 0 then 3: return(a,1,0) 4: else 5: (d,x,y)=Extended-Euclid(b, a mod b) 6: return(d, y,x- ⌊ ⌋y) 7: endif 8: endfunction 的的組組 ax+by=0 的 ax +by=gcd(a,b) 的ax+by=0 的gcd(