Click here for AnswerPool.com Home page


Google

    AnswerPool.com  Hop To Forum Categories  Science  Hop To Forums  Mathematics    Lowest Common Multiple

Moderators: clarebear
Go
Post
Find
Notify
Tools
Reply
  
  Login/Join 
Posted
How would you go about finding the lowest common multiple of the following numbers:

3, 7, 24, 86, 125, 214?
 
Posts: 64 | Location: Charleston SC | Registered: 06-11-02Reply With QuoteEdit or Delete MessageReport This Post
Diamond
Enthusiast

Picture of frankvan
Posted Hide Post
Go to this website for finding least common denominator, or all sorts of other things. CLICK HERE
 
Posts: 7121 | Location: Baltimore, MD, U.S.A | Registered: 06-03-02Reply With QuoteEdit or Delete MessageReport This Post
Posted Hide Post
269,640

but it seems awfully high. Is that right?
 
Posts: 64 | Location: Charleston SC | Registered: 06-11-02Reply With QuoteEdit or Delete MessageReport This Post
Gold Enthusiast
Posted Hide Post
Well, AlisonWonder, I am afraid the correct answer is even higher than 269640 (which is not divisible by 86 or 125)...

The lowest common multiple of 3, 7, 24, 86, 125 and 214 is
96621000   =   23 ´ 3 ´ 53 ´ 7 ´ 43 ´ 107. wink
 
Posts: 102 | Location: Los Angeles, CA | Registered: 06-03-02Reply With QuoteEdit or Delete MessageReport This Post
Gold Enthusiast
Posted Hide Post
I just realized that the link provided by Frankvan provides only the method which is applicable to small numbers like the ones in your question (which are not difficult to factor into primes).  Factoring larger numbers into primes is often very difficult, so it's not a realistic option (in fact some modern schemes in "public key" cryptography do rely on the fact that it's difficult to retrieve two large prime numbers from their product).

To find the least common multiple (LCM) of two large numbers, you're much better off computing first their greatest common divisor (GCD) with Euclid's algorithm (or related algorithms that are similarly efficient). Then use the relation:

LCM(a,b)   =   ( a ´ b ) / GCD(a,b)


Given huge numbers like:
a = 2562047788015215500854906332309589561
b = 6795454494268282920431565661684282819
This is how you would "easily" discover that:
LCM(a,b) = 15669251240038298262232125175172002594731206081193527869

Note: The above numbers (a and b) are not random ones.  They are both products of two very special 19-digit prime numbers.  (HINT: Their GCD is 1111111111111111111 and the other factors are of a similar nature...) cool
 
Posts: 102 | Location: Los Angeles, CA | Registered: 06-03-02Reply With QuoteEdit or Delete MessageReport This Post
Gold Enthusiast
Posted Hide Post
3, 7, 24, 86, 125, 214

Well, you could do it one by one.

3, 7 >>> 3*7 >>> 21
21, 24 >>> 3*7, 2*2*2*3 >>> 2*2*2*3*7 >>> 168
168, 86 >>> 2*2*2*3*7, 2*43 >>> 2*2*2*3*7*43 >>> 7224
7224, 125 >>> 2*2*2*3*7*43, 5*5*5 >>> 2*2*2*3*5*5*5*7*43 >>> 903000
903000, 214 >>> 2*2*2*3*5*5*5*7*43, 2*107 >>> 2*2*2*3*5*5*5*7*43*107 >>> 96,621,000

Darn you, DrGerard, you've beaten me again...
 
Posts: 1363 | Location: Lowell, MA, USA | Registered: 06-03-02Reply With QuoteEdit or Delete MessageReport This Post
 Previous Topic | Next Topic powered by eve community  
 

    AnswerPool.com  Hop To Forum Categories  Science  Hop To Forums  Mathematics    Lowest Common Multiple

© 2002-2008 AnswerPool.com



Visit DiscussionPool.com!