Find the GCF (Greatest Common Factor), also known as GCD or HCF, of up to 5 numbers. Shows prime factorization method, Euclidean algorithm steps, and coprime check.
The greatest common factor (GCF) β also called the greatest common divisor (GCD) in mathematics, or the highest common factor (HCF) in the UK β is one of the most fundamental concepts in number theory. It is the largest positive integer that divides all of the given numbers without leaving a remainder.
Our free GCF calculator handles up to 5 numbers simultaneously, shows both the prime factorization method and the Euclidean algorithm step-by-step, and checks whether the numbers are coprime (GCF = 1).
These three terms refer to exactly the same concept. The terminology difference is regional:
Steps: (1) Find the prime factorization of each number. (2) Identify all prime factors common to every number. (3) For each common prime, take the lowest exponent. (4) Multiply these together.
Example: GCF(48, 18)
The Euclidean algorithm is far more efficient for large numbers. It uses the principle that GCF(a, b) = GCF(b, a mod b), repeating until the remainder is 0.
Example: GCF(48, 18)
The Euclidean algorithm was described by Euclid around 300 BCE in his Elements and remains one of the oldest and most efficient algorithms in mathematics. It runs in O(log(min(a,b))) steps.
The most common use of GCF in everyday mathematics is simplifying fractions. To reduce 48/18 to its lowest terms: GCF(48,18) = 6, so 48/18 = (48Γ·6)/(18Γ·6) = 8/3. UK GCSE and US Math curricula both require students to simplify fractions to lowest terms using GCF/HCF.
If you have 48 apples and 18 oranges to distribute into identical bags with the maximum items per bag while keeping all items together, the answer is GCF(48,18) = 6 bags with 8 apples and 3 oranges each.
The GCD is central to RSA encryption (the most widely used public-key cryptosystem). RSA key generation requires finding two large primes p and q, and verifying that the public exponent e is coprime with (p-1)(q-1) β i.e., GCD(e, (p-1)(q-1)) = 1. The extended Euclidean algorithm also computes modular inverses needed in RSA.
GCF and LCM are related: LCM(a,b) = (a Γ b) / GCF(a,b). Once you know the GCF, computing the LCM is trivial. LCM is used for adding fractions with different denominators.
Two numbers are coprime (or relatively prime) if their GCF = 1. They share no common factors other than 1. Examples: 8 and 9 are coprime (factors of 8: 1,2,4,8; factors of 9: 1,3,9 β only 1 in common). Consecutive integers are always coprime.
Coprimeness is crucial in fractions (a fraction a/b is in lowest terms iff GCF(a,b)=1), modular arithmetic, and number theory.
In the UK, HCF (Highest Common Factor) is a required topic in the GCSE Mathematics syllabus at Foundation and Higher tiers (AQA, OCR, Edexcel). Students must find HCF using both prime factorization (factor trees) and listing factors. In US schools, GCF is introduced in Grade 6 Common Core Math (6.NS.B.4) and revisited in algebra when factoring polynomials.
To find the GCF of three or more numbers, apply the GCF operation sequentially:
GCF(a, b, c) = GCF(GCF(a, b), c)
Example: GCF(12, 18, 24) = GCF(GCF(12,18), 24) = GCF(6, 24) = 6.
All three mean exactly the same thing: the largest positive integer that divides all given numbers exactly. GCF is used in the US, HCF in the UK, and GCD in mathematics and computer science worldwide.
Two methods: (1) List all factors of each number and identify the largest one they share. (2) Use the Euclidean algorithm: GCF(a,b) = GCF(b, a mod b), repeating until remainder = 0. For large numbers, the Euclidean algorithm is much more efficient.
If GCF(a,b) = 1, the numbers are coprime (relatively prime). They share no common factors other than 1. This means the fraction a/b is already in its lowest terms. Consecutive integers are always coprime.
Divide both numerator and denominator by their GCF. Example: 36/48 β GCF(36,48) = 12 β 36/12 = 3, 48/12 = 4 β simplified fraction = 3/4.
For any two positive integers a and b: GCF(a,b) Γ LCM(a,b) = a Γ b. So LCM(a,b) = (a Γ b) / GCF(a,b). For GCF(12,18) = 6: LCM(12,18) = (12Γ18)/6 = 36.
An ancient efficient method: repeatedly replace the larger number with (larger mod smaller) until 0 is reached. The last non-zero remainder is the GCF. Example: GCF(100,35) β GCF(35,30) β GCF(30,5) β GCF(5,0) = 5. Runs in O(log n) steps.
No. The GCF is always β€ the smallest of the numbers. The GCF equals the smallest number only if the smaller divides the larger exactly (e.g., GCF(6,12) = 6).
GCD is used in RSA key generation (checking GCD(e, Ο(n)) = 1), modular inverse computation (extended Euclidean algorithm), fraction reduction, and testing divisibility. Python's math.gcd() and Java's BigInteger.gcd() implement the Euclidean algorithm natively.
Results are for educational purposes only. For professional mathematical or cryptographic applications, verify using specialised software.