# Euclidean algorithm gcd lcm help..

• Aug 10th 2006, 04:50 AM
kodirl
Euclidean algorithm gcd lcm help..
Use the euclidean algorithm to find the gcd of 2232 and 3828 and find the lcm of 2232 and 3828.

I'm not expecting an answer maybe just a quick and easy example of how to solve the sum quickly..thanks
• Aug 10th 2006, 05:21 AM
ThePerfectHacker
Quote:

Originally Posted by kodirl
Use the euclidean algorithm to find the gcd of 2232 and 3828 and find the lcm of 2232 and 3828.

I'm not expecting an answer maybe just a quick and easy example of how to solve the sum quickly..thanks

Use the following theorem,
$\displaystyle \gcd(a,b)\mbox{lcm} (a,b)=ab$
Procede with Euclidean Algorithm,
$\displaystyle 3828=(1)2232+1596$
$\displaystyle 2232=(1)1596+636$
$\displaystyle 1596=(2)636+324$
$\displaystyle 636=(1)324+312$
$\displaystyle 324=(1)312+12$
$\displaystyle 312=(26)12+0$
Therefore,
$\displaystyle \gcd(3828,2232)=12$
Therefore,
$\displaystyle \mbox{lcm}(3828,2232)=\frac{3828\cdot 2232}{12}=712008$
• Aug 10th 2006, 05:46 AM
Soroban
Hello, Kerry!

Do you know the Euclidean Algorithm?
If you do, exactly where is your difficulty?

Quote:

Use the Euclidean Algorithm to find the GCD and LCM of 2232 and 3828.

Example: Find the GCD of 72 and 120.

Step 1: Divide the larger by the smaller.
. . . . . . $\displaystyle 120 \div 72 \:=\:1,\;rem.\,48$

Step 2: Divide the divisor by the remainder.
. . . . . . $\displaystyle 72 \div 48\:=\:1,\;rem.\,24$

Repeat Step 2 until a zero remainder is achieved.
. . . . . . $\displaystyle 48 \div 24\:=\:2,\;rem.\, 0$
. . . . . . . . . .$\displaystyle \uparrow$
. . The last divisor is the GCD.

Therefore: .$\displaystyle GCD(72,\,120)\:=$ 24

There is a formula for the LCM: .$\displaystyle \boxed{\boxed{LCM(a,b)\;=\;\frac{a\cdot b}{GCD(a,b)}}}$

Hence: .$\displaystyle LCM(72,120)\;=\;\frac{72\cdot120}{24}\;=$ 360