How do you find the GCF using the Euclidean algorithm?

Divide the larger number by the smaller and take the remainder. Replace the larger with the smaller and the smaller with the remainder. Repeat until the remainder is 0. The last non-zero remainder is the GCF. Example: GCF(48, 18): 48 = 2 × 18 + 12; 18 = 1 × 12 + 6; 12 = 2 × 6 + 0. GCF = 6.

How do you find the GCF using prime factorization?

Write each number as a product of prime factors. Identify the primes shared by all numbers. Multiply the shared primes using the lowest exponent for each. Example: GCF(12, 18): 12 = 2² × 3; 18 = 2 × 3². Shared primes: 2 (min exp 1) and 3 (min exp 1). GCF = 2¹ × 3¹ = 6.

GCF(12, 18) = 6. Using the Euclidean algorithm: 18 = 1 × 12 + 6; 12 = 2 × 6 + 0. GCF = 6. Using prime factorization: 12 = 2² × 3 and 18 = 2 × 3². Common factors with lowest exponents: 2¹ × 3¹ = 6.

What is GCF used for in real life?

GCF has several practical uses. Simplifying fractions: divide numerator and denominator by GCF to reach lowest terms. Dividing objects into equal groups: GCF(24, 36) = 12 means 24 apples and 36 oranges can be divided into 12 equal bags with no leftovers. Tiling rooms: the largest square tile that fits both 360 cm and 480 cm dimensions is GCF(360, 480) = 120 cm.

How do you find the GCF of three or more numbers?

Apply the Euclidean algorithm iteratively. Find GCF of the first two numbers, then find GCF of that result with the third number, and so on. For GCF(12, 18, 24): GCF(12, 18) = 6; GCF(6, 24) = 6. So GCF(12, 18, 24) = 6.

What does it mean when GCF equals 1?

When GCF(a, b) = 1, the numbers are called coprime or relatively prime. They share no common factor other than 1. For example, GCF(8, 15) = 1 because 8 = 2³ and 15 = 3 × 5 share no prime factors. Coprime numbers are important in fractions (already in lowest terms) and in modular arithmetic.

GCF Calculator (Greatest Common Factor)

Q: What is the greatest common factor (GCF)?

The greatest common factor (GCF) of two or more integers is the largest integer that divides all of them without a remainder. For example, GCF(12, 18) = 6 because 6 is the largest number that divides both 12 and 18 exactly. GCF is also called GCD (Greatest Common Divisor) or HCF (Highest Common Factor).

Q: What is the difference between GCF, GCD, and HCF?

GCF (Greatest Common Factor), GCD (Greatest Common Divisor), and HCF (Highest Common Factor) all mean the same thing: the largest integer that divides a set of numbers exactly. GCF and HCF are common in US and UK elementary math respectively; GCD is standard in university-level number theory and computer science.

Q: What is the relationship between GCF and LCM?

For any two positive integers a and b: GCF(a, b) × LCM(a, b) = a × b. This means once you know the GCF, you can find the LCM without additional computation: LCM(a, b) = a × b / GCF(a, b). For example: a = 12, b = 18; GCF = 6; LCM = (12 × 18) / 6 = 216 / 6 = 36.

Q: What is the GCF of two consecutive numbers?

The GCF of any two consecutive integers n and n+1 is always 1. They are always coprime. Proof: any divisor d of n also divides (n+1 - n) = 1, so d = 1. For example, GCF(7, 8) = 1; GCF(100, 101) = 1. This is why consecutive integers cannot be reduced in a fraction.

Find the greatest common factor of any set of numbers, with step-by-step Euclidean algorithm and prime factorizations.

➗ What is the Greatest Common Factor?

The greatest common factor (GCF) of two or more integers is the largest positive integer that divides each of them without leaving a remainder. For example, GCF(12, 18) = 6 because 6 is the largest number that divides both 12 and 18 exactly. The GCF is also called the greatest common divisor (GCD) or highest common factor (HCF) depending on the country and context, but all three names refer to the same mathematical quantity.

GCF appears in many practical situations. Simplifying fractions requires dividing numerator and denominator by their GCF: the fraction 24/36 simplifies to 2/3 by dividing both by GCF(24, 36) = 12. Dividing quantities equally uses GCF to find the largest group size with no remainder: if you have 24 apples and 36 oranges and want equal bags with both fruits in each bag, GCF(24, 36) = 12 tells you the maximum number of bags possible. Tiling and measurement problems use GCF to find the largest unit that fits exactly into multiple dimensions.

There are two standard methods to find the GCF. The Euclidean algorithm repeatedly divides the larger number by the smaller and replaces the larger with the remainder, until the remainder is 0. The last non-zero remainder is the GCF. The prime factorization method decomposes each number into prime factors and takes the product of shared primes using the lowest exponent. The Euclidean algorithm is faster for large numbers because it avoids full factorization.

A closely related value is the Least Common Multiple (LCM), which is the smallest positive integer divisible by all input numbers. GCF and LCM are linked by the formula: GCF(a, b) × LCM(a, b) = a × b. This means knowing GCF immediately gives LCM for two numbers. This calculator displays both values and shows the full Euclidean algorithm derivation so you can verify or learn the process step by step.

📐 Formula

GCF(a, b) = GCF(b, a mod b) (Euclidean Algorithm)

a, b = positive integers (a > b)

a mod b = remainder when a is divided by b

Base case: GCF(a, 0) = a

Example: GCF(48, 18): 48 = 2×18+12; 18 = 1×12+6; 12 = 2×6+0 → GCF = 6

GCF by Prime Factorization = product of shared primes (lowest exponents)

Step 1: Factor each number into primes

Step 2: Identify primes present in ALL numbers

Step 3: Multiply each shared prime raised to its lowest exponent

Example: GCF(12, 18): 12=2²×3; 18=2×3² → GCF = 2¹×3¹ = 6

GCF(a,b) × LCM(a,b) = a × b

Example: GCF(12,18)=6; LCM = (12×18)/6 = 216/6 = 36

📖 How to Use This Calculator

Steps

Enter your numbers in the input field, separated by commas. You can enter 2 to 8 positive integers up to 1 billion. For example: 12, 18, 24.

Click Find GCF to see the greatest common factor and LCM, the prime factorization of each number, and a step-by-step Euclidean algorithm walkthrough.

Read the results. The GCF is the primary result. The steps section shows each division in the Euclidean algorithm so you can follow and verify the computation.

💡 Example Calculations

Example 1 — GCF of 48 and 18

Find GCF(48, 18) using the Euclidean algorithm

48 = 2 × 18 + 12 (48 divided by 18 gives remainder 12)

18 = 1 × 12 + 6 (18 divided by 12 gives remainder 6)

12 = 2 × 6 + 0 (remainder is 0, so GCF = last divisor = 6)

GCF(48, 18) = 6 | LCM = (48 × 18) / 6 = 144

Try this example →

Example 2 — Simplify the fraction 36/60

Use GCF to reduce 36/60 to lowest terms

Find GCF(36, 60): 60 = 1×36+24; 36 = 1×24+12; 24 = 2×12+0 → GCF = 12

Divide numerator and denominator by GCF: 36/12 = 3 and 60/12 = 5

36/60 simplified = 3/5 (GCF = 12)

Try this example →

Example 3 — GCF of three numbers: 12, 18, 24

Find GCF(12, 18, 24) by applying GCF iteratively

GCF(12, 18): 18 = 1×12+6; 12 = 2×6+0 → GCF(12, 18) = 6

GCF(6, 24): 24 = 4×6+0 → GCF(6, 24) = 6

GCF(12, 18, 24) = 6

Try this example →

Example 4 — Coprime numbers: GCF of 35 and 48

Show that 35 and 48 share no common factor

35 = 5 × 7 | 48 = 2⁴ × 3 (no shared prime factors)

Euclidean: 48 = 1×35+13; 35 = 2×13+9; 13 = 1×9+4; 9 = 2×4+1; 4 = 4×1+0 → GCF = 1

GCF(35, 48) = 1 (coprime numbers)

Try this example →

❓ Frequently Asked Questions

What is the greatest common factor (GCF)?+

The greatest common factor (GCF) is the largest positive integer that divides two or more numbers exactly with no remainder. GCF(12, 18) = 6 because 6 is the largest number that goes into both 12 and 18 evenly. It is also called GCD (Greatest Common Divisor) or HCF (Highest Common Factor).

How do you find the GCF of two numbers step by step?+

Use the Euclidean algorithm: (1) Divide the larger number by the smaller and find the remainder. (2) Replace the larger number with the smaller, and the smaller with the remainder. (3) Repeat until the remainder is 0. The last non-zero divisor is the GCF. Example: GCF(48, 18): 48 = 2×18+12; 18 = 1×12+6; 12 = 2×6+0. GCF = 6.

What is GCF(12, 18)?+

GCF(12, 18) = 6. The factors of 12 are 1, 2, 3, 4, 6, 12. The factors of 18 are 1, 2, 3, 6, 9, 18. The common factors are 1, 2, 3, and 6. The greatest of these is 6. Confirmed by prime factorization: 12 = 2² × 3; 18 = 2 × 3²; GCF = 2¹ × 3¹ = 6.

What is the difference between GCF, GCD, and HCF?+

GCF, GCD, and HCF all mean the same mathematical value: the largest integer that divides a set of numbers exactly. GCF (Greatest Common Factor) is common in US school math. GCD (Greatest Common Divisor) is standard in university number theory and computer science. HCF (Highest Common Factor) is preferred in UK and Commonwealth curricula.

How do you find GCF using prime factorization?+

Factor each number into primes, then multiply the shared prime factors using the lowest exponent. For GCF(12, 18): 12 = 2² × 3 and 18 = 2 × 3². Shared primes are 2 (lower exponent is 1) and 3 (lower exponent is 1). GCF = 2 × 3 = 6. For GCF(24, 36): 24 = 2³ × 3 and 36 = 2² × 3². GCF = 2² × 3 = 12.

What is the relationship between GCF and LCM?+

GCF(a, b) × LCM(a, b) = a × b for any two positive integers. This means LCM(a, b) = a × b / GCF(a, b). Example: GCF(12, 18) = 6, so LCM(12, 18) = (12 × 18) / 6 = 216 / 6 = 36. This relationship only holds directly for two numbers; for three or more, apply iteratively.

What does GCF equal 1 mean?+

When GCF(a, b) = 1, the numbers are coprime (or relatively prime): they share no common factor other than 1. For example, GCF(8, 15) = 1 because 8 = 2³ and 15 = 3 × 5 have no shared prime factor. A fraction a/b where GCF(a, b) = 1 is already in lowest terms and cannot be simplified further.

How do you find GCF of three or more numbers?+

Apply GCF iteratively: find GCF of the first pair, then find GCF of that result with the third number, and continue. GCF(12, 18, 24): GCF(12, 18) = 6; GCF(6, 24) = 6. Result: 6. This works because GCF is associative: GCF(a, b, c) = GCF(GCF(a, b), c).

What is GCF used for in simplifying fractions?+

To simplify fraction a/b to lowest terms, divide both numerator and denominator by GCF(a, b). Example: 24/36 simplified by GCF(24, 36) = 12 gives 2/3. The result is in lowest terms because GCF(2, 3) = 1. This is the only mathematically correct method to ensure full simplification in one step.

What is the GCF of two consecutive numbers?+

GCF of any two consecutive integers is always 1. For any n: GCF(n, n+1) = 1. Reason: if d divides both n and n+1, then d divides their difference (n+1) - n = 1, so d = 1. Examples: GCF(5, 6) = 1; GCF(99, 100) = 1; GCF(1000, 1001) = 1. This is why fractions n/(n+1) are always already in lowest terms.

How fast is the Euclidean algorithm for large numbers?+

The Euclidean algorithm runs in O(log min(a, b)) steps, which is very fast. For two 10-digit numbers, it typically takes fewer than 50 division steps. This makes it practical even for cryptographic applications involving numbers hundreds of digits long. By comparison, listing all factors of a 10-digit number would require up to 100,000 trial divisions.

🔗 Related Calculators

📌 Quick Tips

💡GCF is also called GCD (Greatest Common Divisor) or HCF (Highest Common Factor). All three terms refer to the same value.

💡If GCF(a, b) = 1, the numbers are coprime (relatively prime): they share no common factor other than 1. For example, GCF(8, 15) = 1.

💡GCF times LCM always equals the product of the two numbers: GCF(a,b) × LCM(a,b) = a × b. Use this to find LCM quickly once you know GCF.

💡To simplify a fraction a/b to lowest terms, divide both numerator and denominator by GCF(a, b). For example: 24/36 simplified by GCF = 12 gives 2/3.

💡The Euclidean algorithm is efficient for large numbers. GCF(987654, 123456) can be found in a few steps without needing to list all factors.