CalcTrace

Greatest Common Factor Calculator

Find the greatest common factor of two or more whole numbers: the largest number that divides all of them exactly. It is also called the greatest common divisor (GCD) or highest common factor (HCF). The answer is worked out by Euclid’s method with every division shown, and checked against the prime factorisation.

Last updated .

Your numbers

Enter two or more whole numbers, separated by commas or spaces. A comma always starts a new number, so type 1250, not 1,250.

Up to 20 numbers of up to 30 digits each. Minus signs are ignored, because a number and its negative have the same factors.

Result

Greatest common factor

–

–Least common multiple
–Numbers divided by the GCF
–Coprime (GCF of 1)
–Numbers entered

Show the working

Euclid’s method

    Prime factorisation method

    NumberPrime factors

    Two ways to find the greatest common factor

    The greatest common factor of a set of whole numbers is the largest whole number that divides every one of them with no remainder. Schools in Australia and the UK usually call it the highest common factor (HCF), mathematicians and programmers say greatest common divisor (GCD), and American textbooks say GCF. All three names mean the same thing.

    Euclid’s method: gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a

    Here a and b are the two numbers, and “a mod b” is the remainder left when a is divided by b. Each step swaps the pair for a smaller pair with the same common factors, and the last remainder before zero is the answer. For more than two numbers, find the GCF of the first two, then the GCF of that result and the third number, and so on.

    Prime factorisation: GCF = product of each shared prime raised to its lowest exponent

    Write each number as a product of primes. A prime belongs in the GCF only if it appears in every number, and it is raised to the smallest power it has in any of them.

    Worked example: the GCF of 1071 and 462

    By Euclid’s method. Divide, keep the remainder, and repeat with the previous divisor.

    1. 1071 ÷ 462 = 2 remainder 147, because 2 × 462 = 924 and 1071 − 924 = 147.
    2. 462 ÷ 147 = 3 remainder 21, because 3 × 147 = 441 and 462 − 441 = 21.
    3. 147 ÷ 21 = 7 remainder 0.

    The remainder has reached zero, so the last divisor, 21, is the greatest common factor.

    By prime factorisation. 1071 = 3² × 7 × 17 and 462 = 2 × 3 × 7 × 11. The shared primes are 3 and 7. The lowest power of 3 is 3¹ and the lowest power of 7 is 7¹, so the GCF is 3 × 7 = 21. Both methods agree.

    Three numbers. For 84, 126 and 210, first gcd(84, 126) = 42, then gcd(42, 210) = 42. Dividing each number by 42 leaves 2, 3 and 5, which share nothing further.

    Which method to use

    Prime factorisation is easy to follow for small numbers and shows why the answer is what it is. It becomes impractical quickly, because factorising a large number is hard work. Euclid’s method never factorises anything. It only divides, and the numbers shrink fast: the count of division steps is never more than five times the number of digits in the smaller number. The slowest cases are neighbouring Fibonacci numbers, such as 89 and 55, which need 9 steps against a limit of 10. This is why the calculator can handle 30-digit numbers instantly by Euclid’s method but shows the prime factorisation only when every number is 1,000,000,000,000 or less.

    Where the GCF is used

    Simplifying fractions and ratios

    Dividing the top and bottom of a fraction by their GCF puts it in lowest terms in one step: 462/1071 becomes 22/51 after dividing both by 21. Ratios work the same way, so 84 : 126 : 210 simplifies to 2 : 3 : 5.

    Splitting things into equal groups

    The GCF is the largest group size that uses everything up. A floor measuring 360 cm by 480 cm can be covered with whole square tiles of at most 120 cm, the GCF of the two sides, and it takes 3 × 4 = 12 of them.

    Finding the least common multiple

    For two numbers, the GCF multiplied by the least common multiple equals the product of the numbers. With 1071 and 462 the product is 494,802, so the least common multiple is 494,802 ÷ 21 = 23,562. This shortcut holds for exactly two numbers and fails for three or more.

    Points that trip people up