# Gcd and Lcm Calculator Using Euclidean Algorithm With Steps

## This calculator calculates the greatest common divisor (GCD) and the least common multiple (LCM) by subtraction or division by Euclid's algorithm and gives a detailed solution

**You can also use Gcd and Lcm Calculator With Steps and Gcd and Lcm Calculator for Any Number of Numbers**

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.

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 +

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 +

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

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 = 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 = 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

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 630: 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 432: 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