Euclidean algorithm gcd lcm help..

**kodirl** · August 10th 2006, 04:50 AM

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

**ThePerfectHacker** · August 10th 2006, 05:21 AM

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,
$\gcd(a,b)\mbox{lcm} (a,b)=ab$
Procede with Euclidean Algorithm,
$3828=(1)2232+1596$
$2232=(1)1596+636$
$1596=(2)636+324$
$636=(1)324+312$
$324=(1)312+12$
$312=(26)12+0$
Therefore,
$\gcd(3828,2232)=12$
Therefore,
$\mbox{lcm}(3828,2232)=\frac{3828\cdot 2232}{12}=712008$

**Soroban** · August 10th 2006, 05:46 AM

Hello, Kerry!

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

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.
. . . . . . $120 \div 72 \:=\:1,\;rem.\,48$

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

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

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

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

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

Thread: Euclidean algorithm gcd lcm help..

LinkBack

Thread Tools

Display

Euclidean algorithm gcd lcm help..

Similar Math Help Forum Discussions

Euclidean Algorithm

Euclidean Algorithm

[SOLVED] Euclidean Algorithm

GCD and the Euclidean Algorithm

Euclidean algorithm

Search Tags