GCF Gcd Calculator
gcf/gcd calculator. Get instant, accurate results. Enter values for instant results with step-by-step formulas.
Reviewed for accuracy by Manoj Kumar, Mathematics Educator
GCF Gcd Calculator
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: GCD(a,b) = GCD(b, a mod b) | LCM = a×b / GCD(a,b)
Worked example — GCD=12, LCM=144
Formula
GCD(a,b) = GCD(b, a mod b) | LCM = a×b / GCD(a,b)
The Euclidean algorithm repeatedly replaces the larger number with the remainder of dividing it by the smaller number until the remainder reaches zero — the last nonzero remainder is the GCD. Once the GCD is known, the LCM follows directly from the identity GCD(a,b) × LCM(a,b) = a × b.
Worked Examples
Example 1: 48 and 36
Problem:GCD(48, 36)
Solution:48 = 2⁴×3, 36 = 2²×3². GCD = 2²×3 = 12. LCM = 48×36/12 = 144
Result:GCD=12, LCM=144
Example 2: Coprime numbers: 17 and 25
Problem:GCD(17, 25)
Solution:17 is prime and does not divide 25, so their only common factor is 1. GCD = 1. LCM = 17×25/1 = 425.
Result:GCD=1 (coprime), LCM=425
Frequently Asked Questions
What is the difference between GCF and GCD?
GCF (Greatest Common Factor) and GCD (Greatest Common Divisor) describe exactly the same value — the largest positive integer that divides two or more numbers with no remainder. GCF is the term most US elementary and middle school textbooks use; GCD is the term used in higher mathematics, computer science, and most calculators and programming languages (e.g. Python's math.gcd()). You can use either name interchangeably.
How does the Euclidean algorithm find the GCD?
The Euclidean algorithm repeatedly replaces the larger number with the remainder of dividing it by the smaller number until the remainder is zero. For example, GCD(48, 36): 48 mod 36 = 12, then 36 mod 12 = 0, so GCD = 12. Each step at least halves the smaller number in the worst case, so the algorithm finds the GCD of even huge numbers (hundreds of digits, as used in RSA cryptography) in a small number of steps.
When would I use GCD vs LCM in practice?
Use the GCD to simplify a fraction — divide both numerator and denominator by their GCD to reduce it to lowest terms (e.g., 36/48 → divide by GCD 12 → 3/4). Use the LCM to add or subtract fractions with different denominators, or to determine when repeating events line up — two delivery trucks that depart every 6 and 8 minutes will next leave together after LCM(6,8) = 24 minutes.
What are the mathematical properties of the GCD?
Key properties: GCD(a, 0) = a; GCD(a, b) = GCD(b, a mod b), which is the basis of the Euclidean algorithm; GCD(a, b) × LCM(a, b) = a × b for any positive integers; and if GCD(a, b) = 1, the numbers are called coprime (or relatively prime), meaning they share no prime factors at all.
How do I find the GCD using prime factorization instead of the Euclidean algorithm?
List the prime factorization of each number, then multiply together the lowest power of every prime that appears in both factorizations. For 48 = 2⁴×3 and 36 = 2²×3², the shared primes are 2 (lowest power 2² ) and 3 (lowest power 3¹), giving GCD = 2²×3 = 12. This method is intuitive for small numbers but becomes slower than the Euclidean algorithm once numbers get large, since factoring itself is computationally expensive.
Why is the GCD important in cryptography?
The Euclidean algorithm (and its extended version, which also returns the integer coefficients of Bézout's identity) underlies RSA key generation: choosing two numbers that are coprime (GCD = 1) with a public modulus is essential to guarantee that a private key exists. Modular multiplicative inverses, needed throughout public-key cryptography, are computed using the extended Euclidean algorithm.
Can the GCD of more than two numbers be found the same way?
Yes. GCD(a, b, c) = GCD(GCD(a, b), c) — compute the GCD of the first two numbers, then take the GCD of that result with the third number, and so on. The same Euclidean process applies at each step, so the technique scales to any list of integers.
What does it mean if the GCD equals 1?
A GCD of 1 means the two numbers are coprime (relatively prime) — they share no common prime factors, even though either number individually may not be prime. For example, 8 and 9 are coprime (GCD = 1) even though neither is prime. Coprime denominators cannot be simplified further, and coprime pairs are central to modular arithmetic and cryptographic key selection.
How is the GCD used when simplifying fractions?
To reduce any fraction to its lowest terms, divide both the numerator and denominator by their GCD. For 84/126, GCD(84, 126) = 42, so dividing both by 42 gives 2/3 — the simplest possible form. Skipping this step and dividing by a smaller common factor (like 2 or 6) still leaves the fraction reducible, so using the true GCD guarantees the fraction is fully simplified in one step.
References
History
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
🧮Greatest Common Factor Calculator
Find the GCF (GCD) of two or more numbers using prime factorization and Euclidean algorithm.
🧮GCF and LCM Calculator
Calculate gcfand lcmcalculator with inputs, formulas, and instant results.
🧮GCF Calculator - Greatest Common Factor
Calculate gcfcalculator greatest common factor with inputs, formulas, and instant results.
🧮Least Common Multiple Calculator
Find the LCM of two or more numbers using prime factorization and the GCF method.
🧮Annulus Area Calculator
Calculate annulus area with inputs, formulas, and instant results.
🧮Area Calculator
Calculate area with inputs, formulas, and instant results.
🧮Area of a Rectangle Calculator
Calculate the area, perimeter, and diagonal of a rectangle. Find missing sides from known area. Convert between metric and imperial area units.
🧮Area of Crescent Calculator
Calculate area of crescent with inputs, formulas, and instant results.