- #1
0-RWHP
- 2
- 0
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 :)
How to use Euclids algorithim to find LCM?
- Thread starter 0-RWHP
- Start date
In summary, the Euclidean algorithm can be used to find the LCM of two numbers by dividing the product of the numbers by their GCD. For example, with 8 and 19, the GCD is 1 and the LCM is 152. This is a useful technique that can also be used to find the GCD.
- #2
Curious3141
Homework Helper
- 2,862
- 88
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.
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.
- #3
0-RWHP
- 2
- 0
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.
- #4
Curious3141
Homework Helper
- 2,862
- 88
0-RWHP said:
No worries.
1. What is Euclid's algorithm?
Euclid's algorithm is a method used to find the greatest common divisor (GCD) of two integers. It is based on the principle that the GCD of two numbers is equal to the GCD of the smaller number and the remainder when the larger number is divided by the smaller number.
2. How does Euclid's algorithm work?
To find the GCD of two numbers using Euclid's algorithm, divide the larger number by the smaller number and find the remainder. Then, divide the smaller number by the remainder and find the new remainder. Repeat this process until the remainder is equal to 0. The last non-zero remainder is the GCD of the two numbers.
3. How can I use Euclid's algorithm to find the LCM?
The LCM (least common multiple) of two numbers is equal to the product of the two numbers divided by their GCD. Therefore, you can use Euclid's algorithm to find the GCD of two numbers and then use this result to calculate the LCM.
4. Can Euclid's algorithm be used for more than two numbers?
Yes, Euclid's algorithm can be extended to find the GCD and LCM of more than two numbers. Simply apply the algorithm to the first two numbers, then use the result to find the GCD and LCM of this result and the next number, and continue until all numbers have been included.
5. Is Euclid's algorithm the most efficient method for finding the LCM?
While Euclid's algorithm is a commonly used and efficient method for finding the LCM, there are other algorithms that may be more efficient for specific types of numbers. For example, the binary GCD algorithm is faster for large numbers, and the sieve of Eratosthenes is more efficient for finding the LCM of a large set of numbers.
Similar threads
-
Precalculus Mathematics Homework Help
-
Calculus and Beyond Homework Help
-
Calculus and Beyond Homework Help
-
Calculus and Beyond Homework Help
-
Precalculus Mathematics Homework Help
-
Linear and Abstract Algebra
-
Engineering and Comp Sci Homework Help
-
Precalculus Mathematics Homework Help
-
General Math
-
Calculus and Beyond Homework Help