The Euclidean algorithm is a method to find the greatest common divisor of two positive integers, a and b, where a > b. We can denote the greatest common divisor of a and b as gcd(a,b)
The Euclidean algorithm is based on the following:
- If a and b are positive integers, there exist integers unique non-negative integers q and r so that a = bq + r , where r < b.
- a=bq+r→gcd(a,b)=gcd(b,r)
- gcd(z,0) = z, for any integer.
Algorithm steps:
- Express a in the form a = bq+ r.
- End if r = 0 and report b as the gcd. Otherwise b becomes our new a and r becomes our new b and repeat step 1.
Let's find the greatest common divisor of 732 and 345 using the Euclidean algorithm.
732=345(2)+42345=42(8)+942=9(4)+69=6(1)+36=3(2)+0
From above it follows that gcd(732,345) = gcd(345,42) = gcd(42,9) = gcd(9,6) = gcd(6,3) = gcd(3,0) = 3.
A common mistake is to report that the gcd(a,b) is the quotient, q, in the final line. In this case some might erroneously report gcd(732, 345) = 2. It helps to remember the second point above to avoid committing this mistake. The gcd is the last non-zero remainder.
No comments:
Post a Comment