Find the Greatest Common Factor (GCD) of multiple numbers with a step-by-step solution using the Euclidean algorithm. Perfect for math students and teachers.
You have 12 slices of pepperoni and 18 slices of cheese pizza. What's the largest number of friends you can serve so each gets the same number of each type?
Solution: GCF(12, 18) = 6
You can serve up to 6 friends, each getting 2 pepperoni slices and 3 cheese slices.
A song has a pattern that repeats every 24 beats and another that repeats every 36 beats. When will both patterns repeat together?
Solution: GCF(24, 36) = 12
Every 12 beats, the patterns align — this is the fundamental period of the combined rhythm.
Simplify the fraction 42/56 to its lowest terms.
Solution: GCF(42, 56) = 14
42 ÷ 14 = 3, 56 ÷ 14 = 4 → Simplified fraction: 3/4
You need to tile a rectangular floor that is 48 inches wide and 60 inches long with square tiles of the largest possible size without cutting any tiles.
Solution: GCF(48, 60) = 12
Use 12-inch square tiles. You'll need 4 tiles across and 5 tiles down, totaling 20 tiles.
The Euclidean algorithm is one of the oldest and most efficient methods for computing the greatest common divisor (GCD) of two numbers. It was first described by the ancient Greek mathematician Euclid in his work Elements (c. 300 BCE).
To find the GCF of more than two numbers, we apply the Euclidean algorithm iteratively:
The Greatest Common Factor (GCF), also known as the Greatest Common Divisor (GCD) or Highest Common Factor (HCF), is the largest positive integer that divides each of the given numbers without leaving a remainder. For example, the GCF of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly.
The concept of the greatest common factor is one of the most fundamental ideas in number theory and arithmetic. It appears throughout mathematics, from simplifying fractions and solving ratio problems to more advanced topics like modular arithmetic and cryptography. The GCF is closely related to the Least Common Multiple (LCM) — for any two numbers a and b, the product of their GCF and LCM always equals the product of the two numbers: GCF(a,b) × LCM(a,b) = a × b.
The most efficient method for calculating the GCF is the Euclidean algorithm, which has been used for over 2,300 years. This algorithm works by repeatedly applying the principle that the GCF of two numbers also divides their remainder when one is divided by the other. This makes it extremely fast even for very large numbers, requiring only logarithmic time relative to the input size.
The Euclidean algorithm is based on a simple observation: if a and b are two positive integers with a > b, then GCF(a, b) = GCF(b, a mod b). This works because any common divisor of a and b must also divide their difference (or remainder), so we can repeatedly replace the larger number with the remainder until we reach zero. At that point, the non-zero number is the GCF.
For example, to find GCF(48, 18): 48 ÷ 18 = 2 remainder 12, so GCF(48, 18) = GCF(18, 12). Then 18 ÷ 12 = 1 remainder 6, so GCF(18, 12) = GCF(12, 6). Then 12 ÷ 6 = 2 remainder 0, so GCF = 6. This elegantly simple process makes the Euclidean algorithm one of the most celebrated algorithms in mathematics.
The greatest common factor is far more than just a classroom concept — it has practical applications across many areas of mathematics and everyday life. Understanding GCF helps develop strong number sense and lays the foundation for more advanced mathematical thinking.
To reduce a fraction to its lowest terms, divide both the numerator and denominator by their GCF. For example, simplify 18/24 by dividing both by 6 to get 3/4.
GCF helps solve problems where you need to divide items into equal groups, like splitting 24 apples and 36 oranges into identical gift baskets with the largest possible number of baskets.
Musical intervals are based on frequency ratios. The GCF helps simplify these ratios to find the fundamental relationship between notes, which is essential in understanding harmony and tuning systems.
The security of RSA encryption — one of the most widely used encryption systems — relies on the difficulty of finding factors of large numbers, and the Euclidean algorithm is a key tool in the process.
⚠️ Educational Use Notice: This GCF Calculator is designed for educational and reference purposes. While the Euclidean algorithm implementation is mathematically accurate, results should be verified for critical applications such as cryptography, engineering calculations, or academic assessments. Always double-check your work and consult additional resources when needed.