GCF Calculator
Enter two numbers to see their product and ratio. The Greatest Common Factor (also called GCD or HCF) requires the Euclidean algorithm or prime factorization — both methods are explained in detail with worked examples. Use the product shown here together with the LCM relationship to verify your GCF.
Advertisement
Calculator
See your GCF Calculator results
Enter your email to unlock results — free forever.
No spam, ever. Unsubscribe at any time.
Advertisement
Formula
GCF(a, b) via Euclidean: GCF(a, b) = GCF(b, a mod b)
The GCF (Greatest Common Factor) is the largest integer that divides both a and b without remainder. The Euclidean algorithm finds it efficiently: divide the larger number by the smaller, take the remainder, and repeat until the remainder is 0. The last nonzero remainder is the GCF. For a and b: GCF = a×b / LCM(a,b). The product shown in this calculator lets you verify: once you find the GCF, multiply it by the LCM and the result should equal the product.
How to use the GCF Calculator
- 1
Enter your first number
- 2
Enter your second number
- 3
Read your results instantly
Results update in real time as you type.
Advertisement
Finding GCF by prime factorization
To find GCF(24, 36) by prime factorization:
24 = 2 × 12 = 2 × 2 × 6 = 2 × 2 × 2 × 3 = 2³ × 3¹ 36 = 2 × 18 = 2 × 2 × 9 = 2² × 3²
The GCF takes the minimum exponent of each shared prime: GCF = 2^min(3,2) × 3^min(1,2) = 2² × 3¹ = 4 × 3 = 12.
Verification: 24/12 = 2 ✓, 36/12 = 3 ✓. And 24 × 36 = 864 = GCF × LCM = 12 × 72 = 864 ✓.
Prime factorization is transparent and easy to follow, but for large numbers, factoring itself becomes slow. The Euclidean algorithm is faster in those cases.
GCF by the Euclidean algorithm
The Euclidean algorithm is the fastest hand method for GCF. For GCF(24, 36):
Step 1: 36 ÷ 24 = 1 remainder 12. So GCF(36, 24) = GCF(24, 12). Step 2: 24 ÷ 12 = 2 remainder 0. Remainder = 0, so GCF = 12.
The algorithm works because any common divisor of a and b also divides a mod b. The sequence of remainders strictly decreases, so it always terminates.
For very large numbers like GCF(1,860,498, 570,945): this takes just a few steps, while factoring either number might require testing hundreds of primes.
Advertisement
Applications of GCF
The GCF has many practical uses. Simplifying fractions: to reduce 24/36, divide both by GCF(24, 36) = 12 to get 2/3. This is the canonical way to reach lowest terms.
Tiling and packing: if you have a 24 cm × 36 cm rectangle and want to tile it with identical square tiles (no cutting), the largest square tile that works has side length GCF(24, 36) = 12 cm.
Dividing into equal groups: 24 students and 36 books to be distributed equally among as many groups as possible — GCF(24, 36) = 12 groups of 2 students and 3 books each.
Cryptography: the RSA encryption algorithm uses GCF computations (via the Euclidean algorithm) in its key generation and decryption steps.
Tips & Insights
GCF of consecutive numbers is always 1
Any two consecutive integers (e.g., 17 and 18) are always coprime — their GCF is 1. This is because they differ by 1, and no integer greater than 1 can divide two numbers that differ by 1.
GCF divides the difference
GCF(a, b) also divides |a − b|. So GCF(24, 36) must divide 12. The divisors of 12 are 1, 2, 3, 4, 6, 12 — and indeed the GCF is 12. This gives you a quick shortcut for nearby numbers: if a − b is small, the GCF divides that difference.
Extended Euclidean Algorithm finds coefficients
The extended Euclidean algorithm finds integers x and y such that ax + by = GCF(a, b) — a result called Bézout's identity. For 24x + 36y = 12: one solution is x = −1, y = 1 (24×(−1) + 36×1 = 12). This is essential in modular arithmetic and RSA cryptography.
Worked Examples
Simplifying a fraction
GCF(24, 36) = 12. Divide both by 12: 24/36 = 2/3. The fraction in lowest terms is 2/3.
Tiling a floor
GCF(48, 60): 60 mod 48 = 12; 48 mod 12 = 0; GCF = 12. The largest square tile that covers the floor without cutting is 12 cm × 12 cm. You need (48/12) × (60/12) = 4 × 5 = 20 tiles.
Advertisement
Frequently Asked Questions
What is the difference between GCF, GCD, and HCF?
They are all the same thing: Greatest Common Factor (GCF), Greatest Common Divisor (GCD), and Highest Common Factor (HCF) all refer to the largest integer that divides both numbers. Different textbooks and countries use different names.
How do I find the GCF of three numbers?
Find GCF of the first two, then find GCF of that result with the third. GCF(12, 18, 24): GCF(12, 18) = 6; GCF(6, 24) = 6. So GCF(12, 18, 24) = 6.
What if one number divides the other?
If a divides b (i.e., b mod a = 0), then GCF(a, b) = a. For example, GCF(6, 18) = 6 because 6 divides 18 evenly.
Is GCF always smaller than both numbers?
Not if the numbers are equal. GCF(7, 7) = 7. In all other cases, GCF(a, b) ≤ min(a, b). The GCF equals one of the numbers only when that number divides the other.
Why does GCF appear in the RSA algorithm?
RSA uses GCF to check that a chosen encryption exponent e is coprime to Euler's totient φ(n). If GCF(e, φ(n)) = 1, the exponent is valid. The extended Euclidean algorithm then computes the modular inverse of e, which becomes the decryption exponent d.
Advertisement