Given two positive integers a and b such that a > b, the Euclid's Algorithm is a method to compute the greatest common d

[answerhappygod]

Given Two Positive Integers A And B Such That A B The Euclid S Algorithm Is A Method To Compute The Greatest Common D 1 (44.67 KiB) Viewed 17 times

Given two positive integers a and b such that a > b, the Euclid's Algorithm is a method to compute the greatest common divisor, ged(a, b), of a and b. This algorithm is based on the following main idea: if a b-q+r, for integers q,r20 with 0 <r<b, then: ° ged(a, q) = gcd(b, r) Ⓒgcd(a, b) = ged(b, a) Ⓒgcd(a, b) = gcd(q, r) ged(a, b) = ged(b, r) ° ged(a, b) = ged(a+b, r)