GCD Calculator
Greatest Common Divisor (Euclidean Algorithm)
$$ \gcd(A, B) = ? $$
Number A
Number B
1
2
3
4
5
6
7
8
9
CLR
0
NEXT
Greatest Common Divisor
Euclidean Algorithm Steps
👨🏫
By Prof. David Anderson
Mathematics Professor | 20+ Years Exp.
"Welcome to the most confusingly named concept in math! In the US, we call it GCF. In the UK, it's HCF. Programmers call it GCD. Here's the secret: they are all the same thing. Today, I won't just give you the answer; I'll show you the beautiful logic behind it using Venn Diagrams and the ancient Euclidean Algorithm."
GCD Calculator (GCF / HCF)
Calculate Greatest Common Factor & Least Common Multiple with Steps
GCF (GCD/HCF)
-
LCM
-
Method 1: Prime Factorization (Venn Diagram)
Unique to 24
2
Shared (GCF)
Unique to 36
3
Method 2: Euclidean Algorithm (Steps)
1. GCF vs. GCD vs. HCF: The Name Game
Mathematics is a universal language, but the dialects differ. Depending on where you live or what you study, this concept has different names.
GCF
Greatest Common Factor
Used in: 🇺🇸 USA, 🇨🇦 Canada
HCF
Highest Common Factor
Used in: 🇬🇧 UK, 🇦🇺 Australia, 🇮🇳 India
GCD
Greatest Common Divisor
Used in: 💻 Computer Science, Higher Math
2. Three Methods to Find the GCF
There isn't just one way to find the GCF. Depending on the size of the numbers, different methods are faster.
Method A: The List Method (For small numbers)
This is the elementary school method. You list all factors and circle the largest match.
Find GCF(12, 18):
• Factors of 12: 1, 2, 3, 4, 6, 12
• Factors of 18: 1, 2, 3, 6, 9, 18
• Common Factors: 1, 2, 3, 6
• Greatest: 6
Method B: Prime Factorization (Venn Diagram)
As shown in the calculator above, you break numbers into "atoms" (primes) and multiply the shared atoms. This is great for understanding why the GCF works. It even works for 3 numbers (e.g., GCF of 12, 18, and 30) by finding the intersection of three circles.
Method C: Euclidean Algorithm (For big numbers)
What if you need the GCF of 1,234,567 and 765,432? Enter Euclid (circa 300 BC).
Principle: $GCD(a, b) = GCD(b, a \mod b)$.
It turns a hard problem into a series of smaller division problems until the remainder is 0.
| Method | Best Used For | Pros |
|---|---|---|
| Listing | Numbers < 50 | Easy to visualize |
| Prime Factors | Numbers < 1000 | Shows connection to LCM |
| Euclidean | Any Size | Extremely fast, used by computers |
3. Properties of the GCD
Understanding these properties can help you solve problems faster without always reaching for a calculator.
- Commutative Property: $GCD(a, b) = GCD(b, a)$. The order doesn't matter.
- Associative Property: $GCD(a, b, c) = GCD(GCD(a, b), c)$. You can calculate the GCF of the first two numbers, then use that result with the third.
- Multiples: If $a$ divides $b$ evenly (e.g., 4 and 8), then $GCD(a, b) = a$.
- Prime Numbers: If $a$ and $b$ are prime, their GCF is always 1.
4. The Secret Link: GCF and LCM
Once you have the GCF, you don't need to do more work to find the Least Common Multiple (LCM). They are connected by this beautiful formula:
The Product Formula
$$ GCD(a, b) \times LCM(a, b) = |a \times b| $$
Meaning: The product of the GCF and LCM equals the product of the numbers themselves.
5. Real World Word Problems (Why do we need this?)
GCF isn't just for math class. It appears in construction, design, and even party planning.
🏠 Scenario 1: Tiling a Floor
You have a room that is 240cm by 360cm. You want to tile it with the largest possible square tiles without cutting any. What size tile should you use?
Solution: Find $GCD(240, 360)$.
• $360 = 240 \times 1 + 120$
• $240 = 120 \times 2 + 0$
Answer: 120cm tiles.
🍎 Scenario 2: Splitting Groups
A teacher has 24 girls and 32 boys. She wants to make groups with the same number of girls and boys in each group, with no one left over. What is the greatest number of groups?
Solution: Find $GCD(24, 32)$.
Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
Factors of 32: 1, 2, 4, 8, 16, 32
Answer: 8 groups (each with 3 girls and 4 boys).
🎁 Scenario 3: The Ribbon Problem
You have two ribbons, one 120cm long and the other 150cm long. You want to cut them into smaller pieces of equal length, with nothing leftover. What is the longest length you can cut?
Solution: $GCD(120, 150) = 30$. You can cut 30cm strips.
6. Professor's FAQ Corner
Can GCF be 1?
Yes. If the GCF is 1, the numbers are called Co-prime (or relatively prime). Example: 8 and 9 share no factors other than 1.
How do I find the GCF of 3 numbers?
First, find the GCF of the first two numbers. Then, find the GCF of that result and the third number.
Formula: $GCD(a, b, c) = GCD(GCD(a, b), c)$.
Formula: $GCD(a, b, c) = GCD(GCD(a, b), c)$.
Is the GCF always smaller than the numbers?
It is always less than or equal to the smaller number. For example, if you find the GCF of 12 and 24, the answer is 12.
Can the GCF be negative?
No. By mathematical definition, the "Greatest Common Factor" is always positive. $GCD(-12, -18) = 6$.
What is the GCF of two different prime numbers?
The GCF of two distinct prime numbers (like 13 and 7) is always 1.
What is the GCD of a number and 0?
The GCD of any non-zero number $n$ and 0 is the absolute value of $n$. This is because 0 is divisible by everything, so the largest factor they share is $n$ itself.
References
- Euclid. Elements (Book VII, Propositions 1-2). c. 300 BC. (Source of the Euclidean Algorithm).
- Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley.
- Hardy, G. H., & Wright, E. M. (2008). An Introduction to the Theory of Numbers. Oxford University Press.
Ready to Calculate?
Enter your numbers above to find the GCF and LCM instantly with steps.
Calculate GCD Now