Pythagorist
Numbers

HCF Calculator — Highest Common Factor

Find the highest common factor (HCF) of two numbers, also called the greatest common divisor (GCD). Uses the Euclidean algorithm with full step-by-step working shown.

HCF(48, 36)

12

How it works

  1. Apply the Euclidean algorithm

    The Euclidean algorithm: divide the larger number by the smaller, then repeat with (divisor, remainder) until the remainder is 0. The last non-zero remainder is the HCF.

  2. 48 = 36 × 1 + 12

    48=36×1+1248 = 36 \times 1 + 12

    Remainder is 12. Now apply the algorithm to (36, 12).

  3. 36 = 12 × 3 + 0

    36=12×3+036 = 12 \times 3 + 0

    The remainder is 0, so the algorithm ends. The HCF is the last non-zero remainder (or divisor): 12.

    Result:HCF = 12

The formula

HCF(a,b)=HCF(b,amod  b)\text{HCF}(a, b) = \text{HCF}(b, a \mod b)
a,ba, bThe two numbers
amodba mod bThe remainder when a is divided by b

Example substitution

HCF(48,18):48=2×18+12,  18=1×12+6,  12=2×6+0\text{HCF}(48, 18): 48 = 2 \times 18 + 12, \; 18 = 1 \times 12 + 6, \; 12 = 2 \times 6 + 0

Keep applying until remainder is 0. Last non-zero remainder is the HCF = 6.

Worked examples

Find the highest common factor of 48 and 36.

  1. 1
    Step 1: 48 = 1 × 36 + 12
  2. 2
    Step 2: 36 = 3 × 12 + 0
  3. 3
    Remainder 0: HCF = 12
Answer: 12

Find the highest common factor of 120 and 45.

  1. 1
    Step 1: 120 = 2 × 45 + 30
  2. 2
    Step 2: 45 = 1 × 30 + 15
  3. 3
    Step 3: 30 = 2 × 15 + 0
Answer: 15

Find the highest common factor of 56 and 98.

  1. 1
    Step 1: 98 = 1 × 56 + 42
  2. 2
    Step 2: 56 = 1 × 42 + 14
  3. 3
    Step 3: 42 = 3 × 14 + 0
Answer: 14

Frequently asked questions

What is the HCF?+

The highest common factor (HCF), also called the greatest common divisor (GCD), is the largest number that divides exactly into two or more numbers.

How do you find the HCF?+

List all factors of each number and find the largest one they share. Alternatively, use the Euclidean algorithm for large numbers.

What is the HCF of 24 and 36?+

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24. Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36. HCF = 12.

What is the Euclidean algorithm?+

Divide the larger number by the smaller, take the remainder, repeat with (smaller, remainder) until the remainder is 0. The last divisor is the HCF.

Related calculators

LCM Calculator

Find the lowest common multiple with step-by-step working

Prime Factorisation Calculator

Break any number into its prime factors with a factor tree

Factors Calculator

Find all factors of any number instantly