GCD Calculator Formula
Understand the math behind the gcd calculator. Each variable explained with a worked example.
Formulas Used
Gcd Val
gcd_val = gcd(a, b)Lcm Val
lcm_val = abs(a * b) / gcd(a, b)A Div
a_div = a / gcd(a, b)B Div
b_div = b / gcd(a, b)Variables
| Variable | Description | Default |
|---|---|---|
a | Number A | 48 |
b | Number B | 36 |
How It Works
Greatest Common Divisor (GCD)
Definition
The GCD of two numbers is the largest positive integer that divides both numbers evenly.
Euclidean Algorithm
1. Divide the larger number by the smaller 2. Replace the larger number with the remainder 3. Repeat until the remainder is 0 4. The last nonzero remainder is the GCD
Relationship with LCM
LCM(a, b) = a × b
Worked Example
Find GCD(48, 36).
- 0148 = 1 × 36 + 12
- 0236 = 3 × 12 + 0
- 03GCD = 12
- 04LCM = (48 × 36) / 12 = 144
Frequently Asked Questions
What is the GCD?
The greatest common divisor (also called highest common factor or HCF) is the largest number that divides two numbers without leaving a remainder.
How is GCD used?
GCD is used to simplify fractions (divide numerator and denominator by their GCD), solve Diophantine equations, and in cryptography (RSA algorithm).
What if one number is zero?
GCD(a, 0) = a for any positive integer a. The GCD of zero and any number is that number itself.
Learn More
Guide
Understanding Prime Numbers - Complete Guide
Learn what prime numbers are, how to identify them, prime factorization, the Sieve of Eratosthenes, and why primes matter in cryptography and mathematics.
Ready to run the numbers?
Open GCD Calculator