How to use Euclids algorithim to find LCM?


by 0-RWHP
Tags: algorithim, euclids
0-RWHP
0-RWHP is offline
#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
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
Curious3141
Curious3141 is offline
#2
Dec26-11, 07:07 PM
HW Helper
Curious3141's Avatar
P: 2,885
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
0-RWHP is offline
#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
Curious3141 is offline
#4
Dec26-11, 09:05 PM
HW Helper
Curious3141's Avatar
P: 2,885

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