Euclidean AlgorithmDate: 10/13/97 at 11:47:58 From: Kevin Duong Subject: Euclid's theorem I have this project to do that involves Euclid's theorem (actually it's about the Greatest Common Denominator). Can you tell me what it is in layman's terms, or try to simplify it, please? Thanks, Kevin Date: 10/16/97 at 12:20:45 From: Doctor Ezra Subject: Re: Euclid's theorem Dear Kevin, Euclid had a number of theorems, but I suspect that the one you're interested in is also known as the Euclidean Algorithm. This is an algorithm, or procedure, for finding the Greatest Common Divisor (or GCD) of two numbers, and it's based on something with which you are probably familiar. But first, what's the GCD of two numbers? It's just the largest number that divides both numbers exactly, leaving no remainder. For example, the divisors of 6 are 1, 2, 3 and 6, and the divisors of 15 are 1, 3, 5 and 15, so the GCD of 6 and 15 is the largest number to appear on both lists: 3. In the same way, you can check to see that the GCD of 36 and 210 is 6, and that the GCD of 15 and 8 is 1. Euclid knew that if you divide one number by another, you get a quotient and a remainder, and that the remainder is less than the divisor. For instance, if you divide 7 into 39, it goes 5 times (that's the quotient) with a remainder of 4: 39 = 5*7 + 4. Also, divide 17 into 829: it goes 48 times, with 13 left over: 829 = 816 + 13 = 48*17 + 13. So, said Euclid, to find the GCD of two numbers, divide one of them into the other, and I guarantee that the GCD will also exactly divide the remainder. For example, 210 = 5*36 + 30 the GCD of 210 and 36 is 6, and 6 does divide 30 exactly (30 = 5*6). Now divide the old remainder into the old divisor, and the GCD of the old divisor and the old remainder will exactly divide the new remainder. Keep doing this, said Euclid, until you get a remainder of 0. The last nonzero remainder you get will be the GCD of the two numbers you started with. Let's do this with 210 and 36: 210 = 5*36 + 30 Divisor 36, remainder 30 36 = 1*30 + 6 Divisor 30, remainder 6 30 = 5*6 + 0 Divisor 6, remainder 0. So, 6 is the last nonzero remainder, and that's the GCD of 210 and 36. Try this out with 21 and 36, with 21 and 34, and with 288 and 178. Good luck! -Doctor Ezra, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/