GCD Calculator Formula

Understand the math behind the gcd calculator. Each variable explained with a worked example.

Use the GCD Calculator

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

VariableDescriptionDefault
aNumber A48
bNumber B36

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| / GCD(a, b)

Worked Example

Find GCD(48, 36).

a = 48b = 36
  1. 0148 = 1 × 36 + 12
  2. 0236 = 3 × 12 + 0
  3. 03GCD = 12
  4. 04LCM = (48 × 36) / 12 = 144

Ready to run the numbers?

Open GCD Calculator