GCD and LCM: Find Both by Hand, With Worked Examples

The greatest common divisor (GCD, also called the highest common factor or HCF) of two whole numbers is the largest number that divides both. The least common multiple (LCM) is the smallest number that both divide into. For 36 and 48, the GCD is 12 and the LCM is 144.

The rest of this guide shows how to get those answers by hand, the link between GCD and LCM, and where they are used.

What is the GCD?

The greatest common divisor (also called the greatest common factor or highest common factor) of two integers is the largest positive integer that divides both numbers evenly. For two integers $a$ and $b$ :

\gcd(a, b) = \text{largest } d \text{ such that } d \mid a \text{ and } d \mid b

Example 1: GCD by listing factors

Find $\gcd(36, 48)$ :

Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36

Factors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48

Common factors: 1, 2, 3, 4, 6, 12

\gcd(36, 48) = 12

Methods for finding the GCD

Method 1: Prime factorisation

Express each number as a product of prime factors, then take the product of the common prime factors raised to their lowest powers.

Example 2: GCD by prime factorisation

Find $\gcd(60, 90)$ :

60 = 2^{2} \times 3 \times 5

90 = 2 \times 3^{2} \times 5

Take the smaller power of each prime:

\gcd(60, 90) = 2^{\min(2,1)} \times 3^{\min(1,2)} \times 5^{\min(1,1)} = 2^{1} \times 3^{1} \times 5^{1} = 30

Each row is a prime and the bars are how many times it divides 60 and 90. The dashed line marks the smaller count, which builds the GCD (30). The larger count builds the LCM (180).

Method 2: The Euclidean algorithm

The Euclidean algorithm is much faster than listing factors or factorising when the numbers are large. It is based on the fact that $\gcd(a, b) = \gcd(b, a \bmod b)$ , and repeats until the remainder is zero:

\gcd(a, b) = \gcd(b, a \bmod b) = \gcd(r_1, r_2) = \cdots = \gcd(r_n, 0) = r_n

Example 3: Euclidean algorithm

Find $\gcd(252, 105)$ :

252 = 2 \times 105 + 42

105 = 2 \times 42 + 21

42 = 2 \times 21 + 0

The last non-zero remainder is 21, so $\gcd(252, 105) = 21$ .

The same steps as squares. A 252 by 105 rectangle is cut into the largest squares that fit, then what is left is cut again. The smallest square has side 21, the GCD, and it tiles the whole rectangle.

Method 3: Extended Euclidean algorithm

The extended Euclidean algorithm also finds integers $x$ and $y$ such that:

ax + by = \gcd(a, b)

This is Bezout's identity. It is how modular inverses are found, which is used in RSA encryption.

Example 4: Extended Euclidean algorithm

Find $x$ and $y$ such that $252x + 105y = \gcd(252, 105)$ . Working backwards from the divisions above gives $x = -2$ and $y = 5$ , and indeed:

252(-2) + 105(5) = -504 + 525 = 21

What is the LCM?

The least common multiple of two integers is the smallest positive integer that is divisible by both numbers:

\text{lcm}(a, b) = \text{smallest } m \text{ such that } a \mid m \text{ and } b \mid m

Example 5: LCM by listing multiples

Find $\text{lcm}(4, 6)$ :

Multiples of 4: 4, 8, 12, 16, ...

Multiples of 6: 6, 12, 18, ...

\text{lcm}(4, 6) = 12

LCM by prime factorisation

Express each number as a product of primes, then take the product of all prime factors raised to their highest powers.

Example 6: LCM by prime factorisation

Find $\text{lcm}(60, 90)$ :

\text{lcm}(60, 90) = 2^{\max(2,1)} \times 3^{\max(1,2)} \times 5^{\max(1,1)} = 4 \times 9 \times 5 = 180

The GCD-LCM relationship

One property connects the two:

\gcd(a, b) \times \text{lcm}(a, b) = |a \times b|

So you can compute the LCM from the GCD, and the other way round:

\text{lcm}(a, b) = \frac{|a \times b|}{\gcd(a, b)}

Example 7: Using the relationship

Find $\text{lcm}(252, 105)$ using the GCD we already computed:

\text{lcm}(252, 105) = \frac{252 \times 105}{21} = \frac{26{,}460}{21} = 1{,}260

GCD and LCM of more than two numbers

To find the GCD or LCM of more than two numbers, apply the operation one number at a time:

\gcd(a, b, c) = \gcd(\gcd(a, b), c)

\text{lcm}(a, b, c) = \text{lcm}(\text{lcm}(a, b), c)

Example 8: GCD of three numbers

Find $\gcd(24, 36, 54)$ :

\gcd(24, 36) = 12

\gcd(12, 54) = 6

So $\gcd(24, 36, 54) = 6$ .

Properties of GCD and LCM

Commutative: $\gcd(a, b) = \gcd(b, a)$ and $\text{lcm}(a, b) = \text{lcm}(b, a)$ .
Associative: $\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)$ .
Identity: $\gcd(a, 0) = a$ and $\text{lcm}(a, 1) = a$ .
Coprime numbers: If $\gcd(a, b) = 1$ , then $a$ and $b$ are coprime, and $\text{lcm}(a, b) = ab$ .
Divisibility: $\gcd(a, b)$ divides both $a$ and $b$ , and both divide $\text{lcm}(a, b)$ .

Where the GCD is used

Simplifying fractions: Divide numerator and denominator by their GCD. For example, $\frac{48}{64} = \frac{48 \div 16}{64 \div 16} = \frac{3}{4}$ .
Modular inverses: The extended Euclidean algorithm finds them, which RSA encryption uses.
Tiling: The largest square tile that exactly covers a floor of $a \times b$ metres has side $\gcd(a, b)$ , as the squares diagram shows.

Where the LCM is used

Adding fractions: The least common denominator is the LCM of the denominators. For $\frac{1}{4} + \frac{1}{6}$ , the least common denominator is $\text{lcm}(4, 6) = 12$ .
Scheduling: If one event repeats every 4 days and another every 6 days, they coincide every 12 days.

Worked example: a scheduling problem

Example 9: Bus schedules

Bus A departs every 15 minutes and Bus B departs every 20 minutes. If both depart at 9:00, when do they next depart at the same time?

15 = 3 \times 5, \quad 20 = 2^{2} \times 5

\text{lcm}(15, 20) = 2^{2} \times 3 \times 5 = 60

They next depart together after 60 minutes, at 10:00.

Worked example: fraction addition

Example 10: Adding fractions with the LCM

Add $\frac{5}{12} + \frac{7}{18}$ :

12 = 2^{2} \times 3, \quad 18 = 2 \times 3^{2}

\text{lcm}(12, 18) = 2^{2} \times 3^{2} = 36

Convert and add:

\frac{5}{12} = \frac{15}{36}, \quad \frac{7}{18} = \frac{14}{36}

\frac{15}{36} + \frac{14}{36} = \frac{29}{36}

Common mistakes

Confusing GCD with LCM. The GCD is never larger than either number. The LCM is never smaller than either number.
Using the wrong powers in prime factorisation. For the GCD, take the smaller power. For the LCM, take the larger power.
Forgetting $\gcd(a, 0) = a$ . Every integer divides zero.
Not checking the final fraction. After dividing by the GCD, the numerator and denominator should have a GCD of 1.

Try it yourself

Compute the GCD and LCM of two numbers or a whole list with the free GCD & LCM Calculator. It shows the Euclidean algorithm and prime factorisations step by step. For all the factors of a number, use the Factor Calculator, and to put the LCM to work on fractions, the Fraction Calculator.