Register to reply

How to use Euclids algorithim to find LCM?

by 0-RWHP
Tags: algorithim, euclids
Share this thread:
0-RWHP
#1
Dec26-11, 06:00 PM
P: 2
I know it's a really basic problem. I can find GCD with it but I can't find how to use the euclidean algorithm to find the LCM of two numbers? Sorry for the noob question :)
Phys.Org News Partner Science news on Phys.org
What lit up the universe?
Sheepdogs use just two simple rules to round up large herds of sheep
Animals first flex their muscles
Curious3141
#2
Dec26-11, 07:07 PM
HW Helper
Curious3141's Avatar
P: 2,950
Once you have the GCD, use the well known equation

LCM(a,b)*GCD(a,b) = a*b

or LCM = (a*b)/GCD

Just divide the product by the GCD and you have the LCM.
0-RWHP
#3
Dec26-11, 07:56 PM
P: 2
Oh ok, so with 8, 19 for example you would just do 8x19 then divide that by GCD of 8, 19. The GCD of 8, 19 is 1 so the answer is just 152 right? This is great, I loved when I discovered Euclids algorithm for GCD and was really excited when I found it could do LCM as well. Thanks so much for your help, I appreciate it.

Curious3141
#4
Dec26-11, 09:05 PM
HW Helper
Curious3141's Avatar
P: 2,950
How to use Euclids algorithim to find LCM?

Quote Quote by 0-RWHP View Post
Oh ok, so with 8, 19 for example you would just do 8x19 then divide that by GCD of 8, 19. The GCD of 8, 19 is 1 so the answer is just 152 right? This is great, I loved when I discovered Euclids algorithm for GCD and was really excited when I found it could do LCM as well. Thanks so much for your help, I appreciate it.
No worries.


Register to reply

Related Discussions
Find the upper and lower boundary curve to find the area between two curves. Calculus & Beyond Homework 2
Shell method to find volumes: need to find intersections of the curves involved? Calculus 0
Find Find the point in this plane where it intersects the z axis Calculus & Beyond Homework 3
Proving an algorithim Set Theory, Logic, Probability, Statistics 1
Algorithim for charging SLA batteries Electrical Engineering 0