Gcd and Lcm Calculator Using Euclidean Algorithm With Steps

Theory
The greatest common divisor of GCD (a; b) is the largest number by which the numbers a and b are divisible without remainder.
Among all the ways to find the greatest common divisor for two numbers, Euclid's algorithm is the most convenient and simple.

Finding GCD and LCM by the Euclidean algorithm by division:

As you know, division with the remainder of integers, where a is the dividend and b is the divisor, where b ≠ 0, implies finding such integers q and r that the equality holds:
a = b ∙ q + r, where
q - called quotient,
r - remainder after division, which cannot be a negative number and the modulus cannot be greater than the divisor.

The essence of the method is that first we select the largest of the two numbers for which it is required to find the GCD and divide the larger number by the smaller one. If the remainder of the division is not zero, divide the divisor by the remainder of the division, so we continue until the remainder of the division is equal to zero. Here are some examples:

Find GCD (36; 30), to do this, first find the remainder of 36 divided by 30
36: 30 = 1 (remainder 6), because 36 = 30 ∙ 1 + 6 , the remainder of the division is not zero, so we continue division, divide 30 by 6
30: 6 = 5 (remainder 0) because 30 = 6 ∙ 5 + 0, the remainder of the division is zero, so GCD is equal to the previous remainder of the division 6
Answer: GCD (36; 30) = 6
To find the least common multiple LCM of numbers a and b, you need to divide the product of a and b by GCD (a; b)
LCM (36; 30) = (36 ∙ 30): 6 = 180

Find GCD (176; 36), for this first find the remainder of 176 divided by 36
176: 36 = 4 (remainder 32) because 176 = 36 ∙ 4 + 32, the remainder of the division is not zero, so we continue to divide, divide 36 by 32
36: 32 = 1 (remainder 4) because 36 = 32 ∙ 1 + 4 , the remainder of the division is not zero, so we continue division, divide 32 by 4
32: 4 = 8 (remainder 0) because 32 = 4 ∙ 8 + 0, the remainder of the division is zero, so GCD is equal to the previous remainder of the division 4
Answer: GCD (176; 36) = 4
To find the least common multiple LCM of numbers a and b, you need to divide the product of a and b by GCD (a; b)
LCM (176; 36) = (176 ∙ 36): 4 = 1584

Finding GCD and LCM by the Euclidean algorithm by the subtraction method:

The essence of the subtraction method is that it is necessary to subtract the smaller from the larger number, if the result of the subtraction is not zero, then we replace the decreasing with the resulting difference, if the difference is zero, then the GCD is equal to the previous value of the difference. Here are some examples:

Find GCD (36; 30)
36 - 30 = 6
30 - 6 = 24
24 - 6 = 18
18 - 6 = 12
12 - 6 = 6
6 - 6 = 0
Answer: GCD (36; 30) = 6
To find the least common multiple LCM of numbers a and b, you need to divide the product of a and b by GCD (a; b)
LCM (36; 30) = (36 ∙ 30): 6 = 180

Find GCD (176; 36)
176 - 36 = 140
140 - 36 = 104
104 - 36 = 68
68 - 36 = 32
36 - 32 = 4
32 - 4 = 28
28 - 4 = 24
24 - 4 = 20
20 - 4 = 16
16 - 4 = 12
12 - 4 = 8
8 - 4 = 4
4 - 4 = 0
Answer: GCD (176; 36) = 4
To find the least common multiple LCM of numbers a and b, you need to divide the product of a and b by GCD (a; b)
LCM (176; 36) = (176 ∙ 36): 4 = 1584