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