Calculate the Greatest Common Factor (GCF), Greatest Common Divisor (GCD), or Highest Common Factor (HCF) of two numbers using the Euclidean algorithm and prime factorization.
Verification: 48 / 24 = 2 and 72 / 24 = 3. Since gcd(2, 3) = 1, 24 is the greatest common factor.
How It Works & Formula
Mathematical Formula
Euclidean Algorithm: GCF(a, b) = GCF(b, a mod b) | Prime Factorization: GCF(a, b) = ∏ pᵢ^min(eₐ, e_b)
The Euclidean algorithm repeatedly computes the remainder of division between two integers until the remainder reaches zero; the final non-zero remainder is the GCF. Prime factorization determines the product of all shared prime factors raised to their lowest powers.
📐 Step-by-Step Calculation Breakdown
Substituted values from your current calculation inputs:
First Number: 48
Second Number: 72
How to Use This Calculator
Enter two non-zero integers in the input fields.
Click Calculate to compute the Greatest Common Factor (GCF / GCD / HCF).
Review the step-by-step Euclidean division breakdown, Least Common Multiple (LCM), and simplified fraction ratio.
Example Calculation
For 48 and 72: 48 = 2⁴ × 3 and 72 = 2³ × 3². The common prime factors are 2³ × 3 = 24. Using Euclid's method: 72 mod 48 = 24, then 48 mod 24 = 0, giving GCF = 24.
Understanding the Results
The GCF is the largest positive integer that divides both numbers without leaving a remainder. It is used to reduce fractions to lowest terms, solve linear Diophantine equations, and determine the Least Common Multiple (LCM) via LCM(a, b) = (|a × b|) / GCF(a, b).
GCF Calculator — Greatest Common Factor (GCD / HCF) Step-by-Step
The Greatest Common Factor (GCF), also called GCD or HCF, is the largest positive integer that divides two or more numbers without leaving a remainder. It's essential for simplifying fractions, solving algebraic expressions, and competitive math problems.
Method 1: The Euclidean Algorithm (Fastest)
Worked Example: Find GCF(252, 105)
252 ÷ 105 = 2 remainder 42
105 ÷ 42 = 2 remainder 21
42 ÷ 21 = 2 remainder 0
Last non-zero remainder: GCF = 21
Method 2: Prime Factorization
Worked Example: Find GCF(48, 180)
48 = 2⁴ × 3¹
180 = 2² × 3² × 5¹
Shared: 2² × 3¹ = 4 × 3 = 12
GCF × LCM = a × b
For any two positive integers: GCF(a,b) × LCM(a,b) = a × b. Calculate LCM with our LCM Calculator, or simplify fractions with our Fraction Calculator.
Frequently Asked Questions
What is the difference between GCF, GCD, and HCF?
Greatest Common Factor (GCF), Greatest Common Divisor (GCD), and Highest Common Factor (HCF) are mathematically identical terms used interchangeably across US, UK, CBSE, and ICSE curricula.
How does the Euclidean algorithm find the GCF?
The Euclidean algorithm divides the larger integer by the smaller integer and computes the remainder. It then replaces the larger integer with the divisor and the smaller integer with the remainder, repeating until the remainder is 0. The final non-zero remainder is the GCF.
How do you find the GCF using prime factorization?
To find the GCF by prime factorization, decompose both numbers into their prime components (e.g. 48 = 2⁴ × 3, 72 = 2³ × 3²). Identify the shared prime factors, raise each to the lowest exponent that appears in either factorization, and multiply them together (2³ × 3 = 24).
How are GCF and LCM mathematically related?
For any two positive integers a and b, their product equals the product of their GCF and LCM: a × b = GCF(a, b) × LCM(a, b). This means you can always calculate the LCM directly using LCM = (a × b) / GCF.
Can the GCF of two numbers ever be 1?
Yes. When two integers share no common positive factor other than 1, their GCF is 1, and the numbers are called coprime or relatively prime (for example, 9 and 28).
How do you find the GCF of three or more numbers?
To find the GCF of three numbers a, b, and c, compute the GCF of the first two numbers, and then find the GCF of that result with the third number: GCF(a, b, c) = GCF(GCF(a, b), c).
What is the GCF of two consecutive integers?
The GCF of any two consecutive integers (like 14 and 15, or 99 and 100) is always 1, because any common factor must also divide their difference, which is 1.
Why is finding the GCF essential for simplifying fractions?
Dividing both the numerator and the denominator of a fraction by their GCF reduces the fraction to its irreducible lowest terms in a single operation, eliminating the need for repetitive trial division.
🔢Number Theory, Factors & Binary Systems Cluster
Related Calculators & Recommended Tools
Greatest common factor, least common multiple, prime factoring, number sequences, binary, and hexadecimal conversion. Use these interconnected tools to verify results and explore alternative calculation scenarios:
