Basic Math | Mathematical Algorithms | GCD
& LCM
Data Structures and Algorithms
The greatest common divisor is a mathematical concept used to find the largest number that divides
two given numbers. The Euclidean algorithm is a commonly used algorithm to find the GCD of two
numbers. The main idea of the algorithm is to continuously subtract the smaller number from the larger
number until they become equal. At this point, the greatest common divisor has been found.
For example, let us say we want to find the GCD of 24 and 36. We start by subtracting the smaller
number, 24, from the larger number, 36.
36 - 24 = 12
Now, we subtract the smaller number from the result until we can no longer do so.
24 - 12 = 12
We continue this process until the two numbers are equal.
12 - 12 = 0
At this point, we have found that the GCD of 24 and 36 is 12.
Another important concept in number theory is the least common multiple (LCM). The LCM is the
smallest multiple that is common to both numbers. To find the LCM of two numbers, we can use the
GCD found using the Euclidean algorithm.
For example, let us say we want to find the LCM of 24 and 36. We start by finding the GCD of these two
numbers using the Euclidean algorithm.
36 - 24 = 12 24 - 12 = 12 12 - 12 = 0
The GCD of 24 and 36 is 12. To find the LCM, we can use the formula:
LCM = (n1 x n2) / GCD
In this case, the LCM of 24 and 36 is:
LCM = (24 x 36) / 12 = 72
In summary, the Euclidean algorithm is a useful tool in finding the greatest common divisor of two
numbers, which can be used to find the least common multiple.
& LCM
Data Structures and Algorithms
The greatest common divisor is a mathematical concept used to find the largest number that divides
two given numbers. The Euclidean algorithm is a commonly used algorithm to find the GCD of two
numbers. The main idea of the algorithm is to continuously subtract the smaller number from the larger
number until they become equal. At this point, the greatest common divisor has been found.
For example, let us say we want to find the GCD of 24 and 36. We start by subtracting the smaller
number, 24, from the larger number, 36.
36 - 24 = 12
Now, we subtract the smaller number from the result until we can no longer do so.
24 - 12 = 12
We continue this process until the two numbers are equal.
12 - 12 = 0
At this point, we have found that the GCD of 24 and 36 is 12.
Another important concept in number theory is the least common multiple (LCM). The LCM is the
smallest multiple that is common to both numbers. To find the LCM of two numbers, we can use the
GCD found using the Euclidean algorithm.
For example, let us say we want to find the LCM of 24 and 36. We start by finding the GCD of these two
numbers using the Euclidean algorithm.
36 - 24 = 12 24 - 12 = 12 12 - 12 = 0
The GCD of 24 and 36 is 12. To find the LCM, we can use the formula:
LCM = (n1 x n2) / GCD
In this case, the LCM of 24 and 36 is:
LCM = (24 x 36) / 12 = 72
In summary, the Euclidean algorithm is a useful tool in finding the greatest common divisor of two
numbers, which can be used to find the least common multiple.
