Notice

We and selected partners use cookies or similar technologies as specified in the cookie policy.
You can consent to the use of such technologies by closing this notice, by scrolling this page, by interacting with any link or button outside of this notice or by continuing to browse otherwise.
To find out more about the categories of personal information collected and the purposes for which such information will be used, please refer to our privacy policy.

California Consumer Notice

 0 AC +/- ÷ 7 8 9 × 4 5 6 - 1 2 3 + 0 00 , =

# 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

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
 You may also find the following calculators helpful Calculators (Number theory) Mathematical Expressions Calculator Calculator Parentheses Prime Factorization Calculator Gcd and Lcm Calculator With Steps Gcd and Lcm calculator using Euclidean algorithm Gcd and Lcm Calculator for Any Number of Numbers Break Down the Number Into Its Place Value Divide a Number by a Ratio. Online Calculator With Steps Percentage Calculator With Steps Scientific Notation to Decimal Conversion Calculator Scientific Notation Converter Factorial Calculator With Steps Logarithm Calculator Quadratic Equations Calculator With Steps Remainder Calculator Root Calculator Decimal Period Calculator Big Number Calculator Rounding Numbers Calculator Properties of Roots and Exponents Calculator Complex Number Calculator Fraction Calculators Simplifying Fractions Calculator Improper to Mixed Fraction Calculator Mixed Fraction to Improper Calculator Fractions Calculator With Step by Step Solution Raising a Fraction to a Power. Online Calculator. Decimal to Fraction Calculator Fraction to Decimal Calculator Compare Fractions Calculator Common Denominator Calculator Trigonometers Calculators Sine Calculator Cosine Calculator Tangent Calculator Cotangent Calculator Secant Calculator Cosecant Calculator Arcsine Calculator Arccosine Calculator Arctangent Calculator Arccotangent Calculator Arcsecant Calculator Arccosecant Calculator Numeral Systems Calculators Roman Numeral Calculator Roman Numerals From 1 to 3999 Numeral Systems Calculator Binary Calculator. Addition, Subtraction, Multiplication and Division of Binary Numbers. Area Calculators Area of a Square Calculator Area of a Rectangle Calculator Combinatorics Calculators Permutations of N Elements Calculator Combinations of N Elements by M Calculator Permutations of N Elements by M Calculator Linear Algebra and Analytical Geometers Calculators Matrix Addition and Subtraction Calculator Matrix Multiplication Calculator Matrix Transpose Calculator Matrix Determinant Calculator Inverse Matrix Calculator Length of a Line Segment. Distance Between Points Online Calculator. Vector Coordinates Calculator From Two Points Vector Modulus (Length) Calculator Vector Addition and Subtraction Calculator Vector Dot Product Calculator. By Using the Length of the Vectors and Cosine of the Angle Between Vectors. Vector Dot Product Calculator. By Using Vector Coordinates. Vector Product Calculator. By Using Vector Coordinates. Vector Triple Product Calculator Vector Multiplication by Number Calculator Angle Between Vectors Calculator Vector Collinearity Check Calculator Vector Coplanarity Calculator Math Trainers Addition Math Trainer Subtraction Math Trainer Multiplication Math Trainer Division Math Trainer Multiplication Table Math Trainer Online Preschool Counting Trainer Online Preschool Mindfulness Trainer Online Addition Subtraction Multiplication Division Math Trainer. Find the Correct Answer. Online Numeric Expression Trainer Converters Length Converter Speed Converter Acceleration Converter Physics Calculators Mechanics Speed Time Distance Calculator Acceleration Speed Distance Calculator Displacement Time Calculator Time Calculator Newton's Second Law Calculator Gravitational Force Calculator Momentum Calculator Impulse Calculator Object Weight Calculator Optics Light Reflection and Refraction Calculator Electricity and Magnetism Ohm's Law Calculator Coulomb's Law Calculator Electric Field Strength Calculator Point Electric Charge Calculator Q Force Acting on Charge Calculator Distance From Charge Calculator Potential Charge Energy Calculator Electric Field Potential Calculator Conductor and Sphere Capacitance Calculator Capacitors Capacitance of Parallel Plate, Cylindrical and Spherical Capacitors Calculator Electric Field Strength in Parallel Plate, Cylindrical and Spherical Capacitors Calculator Voltage (Potential Difference) of Parallel Plate, Cylindrical and Spherical Capacitors Calculator Distance Between Plates in Parallel Plate Capacitor Calculator Plate Area in Parallel Plate Capacitor Calculator Energy Stored in Charged Capacitor Calculator Energy Stored in Parallel Plate, Cylindrical and Spherical Charged Capacitors Calculator Volumetric Energy Density of Parallel Plate, Cylindrical and Spherical Capacitors Calculator Astronomy Calculators Object Weight on Other Planets Gravitational Acceleration on the Planets of the Solar System and Their Satellites Generators Random Number Generator Password Generator