🎓 Mathematics • Number Theory
100% Client-Side Privacy
GCD Calculator (GCF / HCF)
Computes Greatest Common Divisor (GCD/GCF/HCF) with Euclidean division steps and coprime verification.
Fractions & Number Theory
Fractions, Primes & Factors Studio
Precision fraction reduction to lowest terms, primality tests, Sieve of Eratosthenes generator, divisor sums, and Euclidean GCD/LCM steps.
Input Integers
Preset Pairs:
Greatest Common Divisor
gcd(144, 84)
12
Least Common Multiple
lcm(144, 84)
1008
= (144 × 84) / 12
Euclidean Division Algorithm Proof
| Step | Dividend (a) | Divisor (b) | Quotient (q) | Remainder (r) |
|---|---|---|---|---|
| 1 | 144 | 84 | 1 | 60 |
| 2 | 84 | 60 | 1 | 24 |
| 3 | 60 | 24 | 2 | 12 |
| 4 | 24 | 12 | 2 | 0 |
What is the Greatest Common Divisor?
The GCD of two integers is the largest positive integer that divides both numbers without leaving a remainder.
Formula & Step-by-Step Calculation
gcd(a, b) = gcd(b, a mod b)
Euclidean division algorithm replacing larger number with remainder.
Worked Step-by-Step Examples
Example 1
GCD of 48 and 18
Solution: 6
• 48 = 18 × 2 + 12; 18 = 12 × 1 + 6; 12 = 6 × 2 + 0. GCD = 6.
Common Real-World & Academic Use Cases
- ✓ Reducing fractions to lowest terms
- ✓ Modular arithmetic in RSA cryptography
- ✓ Tiling geometric grids
How to Use the GCD Calculator (GCF / HCF)
1
Input Integers
Enter two positive numbers.
2
View Euclidean Steps
Inspect division remainder table and GCD.
Frequently Asked Questions
Q: What are coprime numbers?
Two numbers whose GCD equals 1 (they share no common factors other than 1).