Results 1 to 3 of 3

Math Help - Euclidean algorithm gcd lcm help..

  1. #1
    Newbie
    Joined
    Aug 2006
    Posts
    12

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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,
    \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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,861
    Thanks
    742
    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

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 30th 2010, 11:46 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2010, 07:53 AM
  3. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 07:45 PM
  4. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 04:20 AM
  5. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 09:28 AM

Search Tags


/mathhelpforum @mathhelpforum