12
72
0
1=yes, 0=no
-5
-119
12
0.5
12
72
0
1=yes, 0=no
-5
-119
12
0.5
The Common Factor Calculator finds all integers that divide evenly into both of two given numbers, culminating in their Greatest Common Factor (GCF). Also known as the Greatest Common Divisor (GCD) or Highest Common Factor (HCF), this value is the cornerstone of fraction simplification, modular arithmetic, and Diophantine equations.
For two positive integers $$a$$ and $$b$$, a common factor is any integer $$d$$ satisfying:
$$d \mid a \quad \text{and} \quad d \mid b$$
The GCF is the largest such $$d$$. This calculator checks divisibility of both numbers by every integer from 1 to 20, flags each common factor found, and computes the GCF using the Euclidean Algorithm. It also determines whether the two numbers are coprime (GCF = 1), meaning they share no common factors other than 1.
Common factors appear everywhere in mathematics. When simplifying $$\frac{24}{36}$$, you divide both numerator and denominator by GCF(24, 36) = 12 to get $$\frac{2}{3}$$. In modular arithmetic, the equation $$ax \equiv c \pmod{b}$$ has solutions only when $$\text{GCF}(a, b)$$ divides $$c$$. In music theory, frequency ratios reduced by GCF determine consonance. The concept even appears in computer graphics for determining pixel grid alignments.
The calculator operates in two phases:
Phase 1 — Common Factor Scan: For each integer $$d$$ from 1 to 20, the calculator checks whether both $$a \bmod d = 0$$ and $$b \bmod d = 0$$. If both conditions hold, $$d$$ is a common factor.
Phase 2 — Euclidean Algorithm: To find the exact GCF (which may exceed 20), the calculator applies:
$$\text{GCF}(a, b) = \text{GCF}(b, a \bmod b)$$
This recurrence continues until the remainder is 0, at which point the last nonzero value is the GCF. The algorithm is guaranteed to terminate in at most $$2 \log_2(\min(a,b))$$ steps.
The LCM is also computed via the identity:
$$\text{LCM}(a, b) = \frac{a \times b}{\text{GCF}(a, b)}$$
Two numbers are coprime when their GCF equals 1, meaning no integer greater than 1 divides both.
A high shared factor count indicates the two numbers have rich overlapping divisibility structures — they share many building blocks. If the numbers are coprime (GCF = 1), they share no prime factors, which is important in number theory (e.g., the Chinese Remainder Theorem requires pairwise coprime moduli). The GCF directly tells you the maximum simplification factor for the fraction $$\frac{a}{b}$$.
Inputs
Results
Common factors: 1, 2, 3, 4, 6, 12. GCF = 12. The fraction 24/36 simplifies to 2/3.
Inputs
Results
Only common factor is 1. These numbers are coprime — 15 = 3×5 and 28 = 2²×7 share no primes.
They are three names for the same concept. GCF (Greatest Common Factor) and HCF (Highest Common Factor) are used primarily in elementary mathematics. GCD (Greatest Common Divisor) is the standard term in higher mathematics and computer science. All refer to the largest positive integer dividing both numbers.
Two numbers are coprime (or relatively prime) when their GCF equals 1. This means they share no prime factors. Examples: 8 and 15 are coprime (8 = 2³, 15 = 3×5). Note that neither number needs to be prime itself — they just need no shared prime factors.
Divide both numerator and denominator by the GCF. For $$\frac{48}{60}$$: GCF(48,60) = 12, so $$\frac{48}{60} = \frac{48 \div 12}{60 \div 12} = \frac{4}{5}$$. This always produces the fraction in lowest terms.
No. The GCF is always ≤ the smaller of the two numbers. The maximum possible GCF equals the smaller number itself, which happens when the smaller number divides the larger evenly (e.g., GCF(5, 20) = 5).
Each step of the Euclidean Algorithm reduces the larger number by at least half, giving a time complexity of $$O(\log(\min(a,b)))$$. This makes it dramatically faster than listing all factors of both numbers, especially for large values. It was described by Euclid around 300 BCE and remains one of the oldest known algorithms.
Common factors are used in fraction arithmetic (simplification), cryptography (RSA key generation requires testing coprimality), music theory (frequency ratios), tiling problems (largest square tile for a rectangle), and gear design (tooth count relationships).
Roboculator Team
The Roboculator Team explains calculations, planning tools, and practical formulas in clear language for real-life situations.
How helpful was this calculator?
Be the first to rate!
