GCD & LCM Formulas: Euclidean Algorithm and Factor Count

PublishedToolFactors, GCF & LCM Calculator

Contents
  1. 1. Counting Factors and the Prime Factorization Formula
  2. 2. The Euclidean Algorithm and the GCD and LCM Formulas
  3. How to Use the Factors, GCF & LCM Calculator
  4. Summary
  5. Frequently Asked Questions

1. Counting Factors and the Prime Factorization Formula

Checking every factor of a huge number one by one takes a lot of computing resources and time. Number theory gets around this quickly with the prime factorization formula.

  • Formula for the number of factors: When a natural number N is prime factorized as follows,

    N = a^p × b^q × c^r × …

    (Here a, b, and c are distinct primes, and p, q, and r are positive integer exponents.)

    Total number of factors = (p + 1) × (q + 1) × (r + 1) × …

  • Worked example (finding the number of factors of 72):

    • Prime factorization: 72 = 8 × 9 = 2^3 × 3^2
    • Plug in the exponents: p = 3, q = 2
    • Number of factors: (3 + 1) × (2 + 1) = 4 × 3 = 12 What this means: Without counting the factors of 72 on your fingers, the formula confirms there are 12 in total (1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72).

2. The Euclidean Algorithm and the GCD and LCM Formulas

A classic programming algorithm for efficiently finding the greatest common divisor of two natural numbers is the Euclidean algorithm, established around 300 BCE.

Recursive Formula for the Euclidean Algorithm

Given two numbers a and b (a > b), let r be the remainder when a is divided by b. The following identity holds.

GCD(a, b) = GCD(b, r)

The divisor at the point when the remainder becomes 0 is the final greatest common divisor of the two numbers.

  • Example (finding GCD(120, 36)):
    1. 120 ÷ 36 = 3, remainder 12 → GCD(120, 36) = GCD(36, 12)
    2. 36 ÷ 12 = 3, remainder 0 → Since the remainder is 0, the last divisor, 12, is the final greatest common divisor.

Least Common Multiple Formula

Once you know the greatest common divisor (GCD), you can get the least common multiple (LCM) immediately with the proportional identity below.

LCM(a, b) = (a × b) ÷ GCD(a, b)

How to Use the Factors, GCF & LCM Calculator

If factoring multi-digit numbers by hand or repeating the Euclidean division loop sounds tedious, try a dedicated number theory calculator.

Factors, GCF & LCM Calculator

Free · no sign-up · enter two numbers to get the factor list, GCD, and LCM instantly

The tool's workflow is very clear.

  1. Enter the numbers: Enter the two natural numbers you want to calculate in the Number A and Number B fields (range: 1 to 10,000,000).
  2. As soon as you type, the detailed analysis area shows the factor list for A and B, the list of common factors, and the prime factorization results.
  3. At the same time, the greatest common divisor (GCD) and least common multiple (LCM) values appear in bold highlight cards at the top, along with the step-by-step calculation using prime factors.

Summary

Factors, greatest common divisors, and least common multiples may look like basic arithmetic, but they are essential calculations that form the backbone of the digital world: the four operations with fractions, bit operations in computer number systems, and key encryption in information security. Manual calculations with multi-digit numbers are prone to error, so checking your work against the calculator's Euclidean algorithm results lets you spot numerical errors quickly.

Factors, GCF & LCM Calculator

Free · no sign-up · enter two numbers to get the factor list, GCD, and LCM instantly

Frequently Asked Questions

What do you call two natural numbers whose greatest common divisor is 1, and why does it matter?

When two numbers have no common divisor other than 1, mathematicians call them relatively prime (or coprime).

  • Coprimality is the key benchmark for reducing a fraction to lowest terms when it cannot be reduced any further.
  • In computer cryptography (RSA), in particular, you pick two large primes, multiply them to get n, and use an integer that is relatively prime to a value derived from n when generating the public key. Judging whether numbers are coprime is a basic prerequisite of the key-generation process.

How do you find the greatest common divisor and least common multiple of three or more numbers (say, A, B, and C)?

This calculator takes two numbers at a time, so for three or more numbers you work through them in pairs and carry the result forward.

  • Extending the GCD formula:

    GCD(A, B, C) = GCD(GCD(A, B), C)

    (In other words, enter A and B first to get their greatest common divisor, then enter that result and C to get the greatest common divisor of all three numbers.)

  • Extending the LCM formula:

    LCM(A, B, C) = LCM(LCM(A, B), C)

    Use the same approach: find the LCM of A and B first, then enter that value with C. You can extend this process one number at a time no matter how many numbers you have.


This article is for informational purposes and references standard number theory, including the Euclidean algorithm.

This article was adapted from our Korean original. Read the Korean original

Related articles

  1. Lotto 1st Prize Odds Explained: Dream Symbol Number PicksSee why a 6/45 lotto line has a 1 in 8,145,060 chance, which numbers dream symbols like pigs and fire map to, and how to turn them into picks.
  2. 4:6 Pour Over Recipe: Brew Ratio Formula and TimerSee the brew ratio formula (1:15) behind the 4:6 method, plan each pour in grams, and follow a step-by-step timer from bloom to final pour.
  3. Due Date Calculator: Naegele's Rule and the 280-Day FormulaUse Naegele's rule to get your due date from your last period, plus how pregnancy weeks are counted and adjusted for your cycle length.
  4. Deposit Early Withdrawal Penalty: What You Get After TaxSee how early withdrawal interest on deposits and savings is calculated: the rate tiers, the 15.4% tax, and how it compares to a secured loan.
  5. Energy Unit Conversion: Joules, Calories, Wh, and BTULearn how joules, calories, watt-hours, and BTU convert, with exact constants, real examples like AC cooling capacity, and a free calculator.
  6. Flesch-Kincaid Readability Score: How to Calculate ItLearn the Flesch Reading Ease and Flesch-Kincaid Grade Level formulas, what the scores mean, and how to tune your English writing for your target readers.

Related tools