Math Is Fun Forum

xXxEmZyxXx

Member

Registered: 2007-10-15

Posts: 12

greatest common divisors

find the greatest common divisor of 2241 and 1411. check your answer by factorizing these numbers into a product of primes

pi man

Member

Registered: 2006-07-06

Posts: 251

Re: greatest common divisors

The prime factorizations are:

2241 = 3^3 * 83
1411 = 17 * 83

The only factor they have in common is 83 so that is the greatest common factor.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: greatest common divisors

Remember that is how to check your answer, by no means is it the easiest way to do it.  Use the Euclidean algorithm.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Identity

Member

Registered: 2007-04-18

Posts: 934

Re: greatest common divisors

2241 = 1411 *1 +830

So gcd(2241,1411) = gcd(1411,830)

and 1411 = 830*1+581

So gcd(1411,830)=gcd(830,581)

830 = 581*1+249

So gcd(830,581)=gcd(581,249)

581 = 249*2+83

So gcd(581,249)=gcd(249,83)

249 = 83*3 + 0

So gcd(249,83)=gcd(83,0)

Everything divides 0, and the greatest divisor of 83 is 83, so the GCD is 83

pi man

Member

Registered: 2006-07-06

Posts: 251

Re: greatest common divisors

Identity, Ricky

Eucludian Method - Is that method demonstrated by Identity?   Pretty simple.   I don't remember ever being taught that method in school.     I was taught to compute the prime factorization which then could also be used to find the LCM (Least common multiple).

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: greatest common divisors

ab = lcm(a, b)*gcd(a,b)

As soon as you know a and b and the gcd, you can compute the lcm.

The Euclidean algorithm is relatively simple to calculate for any number.  Factoring primes can take a very long time by hand for numbers with 5 or more digits, depending on how many prime factors they have.  Imagine trying to factor a number which you don't know, but is, prime.  But the Euclidean algorithm is a bit more simple than what Identity did.  At least, when you cut off all the extra fat it is.

1411 into 2241 has remainder 830
830 into 1411 has remainder 581
581 into 830 has remainder 249
249 into 581 has remainder 83
83 into 249 has remainder 0

Therefore, the gcd is 83.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

pi man

Member

Registered: 2006-07-06

Posts: 251

Re: greatest common divisors

Cool.   Thanks Ricky.