Relatively Prime (Coprime) Calculator
Enter two positive integers to find out whether they are relatively prime (coprime). The calculator computes the GCD using the Euclidean algorithm and shows every step, plus the prime factorizations, LCM, and Euler's totient. If the GCD equals 1, the numbers share no common factor other than 1, which means they are coprime.
Formula
Worked example
Check whether 14 and 15 are coprime. Euclidean algorithm: 15 = 14 x 1 + 1, then 14 = 1 x 14 + 0. The last non-zero remainder is 1, so GCD(14, 15) = 1. Because the GCD is 1, the numbers are relatively prime. Their LCM is (14 x 15) / 1 = 210.
What does relatively prime mean?
Two integers are relatively prime (also called coprime or mutually prime) when their greatest common divisor is 1. That means they share no prime factor. The numbers do not have to be prime themselves: 8 and 9 are coprime even though neither is prime (8 = 2 x 2 x 2 and 9 = 3 x 3 share no factor). The key is that their sets of prime factors have no element in common. The integer 1 is coprime to every positive integer by this definition, because GCD(1, n) = 1 for all n.
How the Euclidean algorithm finds the GCD
The Euclidean algorithm is the fastest practical method for computing the GCD. It works by repeated division with remainder: divide the larger number by the smaller, replace the larger with the smaller and the smaller with the remainder, and repeat until the remainder is zero. The last non-zero remainder is the GCD. For example, GCD(48, 18): 48 = 18 x 2 + 12, then 18 = 12 x 1 + 6, then 12 = 6 x 2 + 0, so GCD = 6. If that final GCD is 1, the numbers are coprime. The calculator shows every division step in the "Show your work" panel so you can follow the logic.
GCD, LCM and the fundamental identity
The greatest common divisor and least common multiple of two integers are linked by the identity GCD(a, b) x LCM(a, b) = |a x b|. For a coprime pair this simplifies to LCM(a, b) = a x b, because GCD = 1. That identity is why coprime numbers arise naturally in fraction arithmetic (a fraction a/b is already in lowest terms when a and b are coprime) and in modular arithmetic (the Chinese Remainder Theorem requires pairwise coprime moduli to guarantee a unique solution).
Euler's totient and why coprimality matters in cryptography
Euler's totient function phi(n) counts how many integers from 1 to n are coprime to n. For a prime p, phi(p) = p - 1, because every integer from 1 to p - 1 is coprime to p. RSA encryption relies directly on this: the public and private key exponents must be coprime to phi(n), where n is the product of two large primes. In gear-ratio design, two meshing gears with a coprime tooth count will ensure every tooth on one gear eventually contacts every tooth on the other, spreading wear evenly. Musical rhythm patterns called Euclidean rhythms also exploit coprimality to distribute beats as evenly as possible.
Common coprime pairs and their properties
| Pair (a, b) | GCD | LCM | Coprime? | Note |
|---|---|---|---|---|
| 8 and 9 | 1 | 72 | Yes | Consecutive integers are always coprime |
| 14 and 15 | 1 | 210 | Yes | Consecutive integers |
| 8 and 12 | 4 | 24 | No | Share factor 2 and 4 |
| 25 and 35 | 5 | 175 | No | Share factor 5 |
| 7 and 13 | 1 | 91 | Yes | Both prime, always coprime to each other |
| 4 and 9 | 1 | 36 | Yes | Squares of distinct primes |
| 12 and 35 | 1 | 420 | Yes | 12=2^2x3, 35=5x7 - no overlap |
| 100 and 101 | 1 | 10100 | Yes | Consecutive integers |
| 36 and 48 | 12 | 144 | No | Share factors 2, 3, 4, 6, 12 |
| 1 and any n | 1 | n | Yes | 1 is coprime to every positive integer |
Pairs of numbers that appear frequently in mathematics, cryptography and engineering.
Frequently asked questions
Can two even numbers be relatively prime?
No. Any two even numbers share the factor 2, so their GCD is at least 2, not 1. For example, GCD(4, 6) = 2, so 4 and 6 are not coprime. One of the pair must be odd for them to possibly be coprime.
Are all consecutive integers coprime?
Yes. Consecutive integers n and n + 1 are always coprime, because any common divisor must divide their difference (n + 1) - n = 1, so it can only be 1. That means GCD(n, n+1) = 1 for every positive integer n.
Is 1 coprime to every number?
Yes. The only divisor of 1 is 1 itself, so GCD(1, n) = 1 for every positive integer n. The integer 1 is therefore coprime to all positive integers.
Are two distinct prime numbers always coprime?
Yes. A prime number has no factors other than 1 and itself. Two distinct primes have no prime factor in common, so their GCD is 1 and they are always coprime.
What is the difference between pairwise coprime and mutually coprime?
For a set of more than two numbers, "mutually coprime" (or "setwise coprime") means the GCD of the entire set is 1, while "pairwise coprime" means every pair of distinct numbers in the set is coprime. Pairwise coprimality is the stronger condition: a pairwise coprime set is always mutually coprime, but the reverse is not always true. For example, {6, 10, 15} is mutually coprime (GCD = 1) but not pairwise coprime because GCD(6, 10) = 2.
How do I make two numbers coprime?
Divide both numbers by their GCD. If GCD(a, b) = g, then a/g and b/g are coprime. For example, 12 and 18 have GCD = 6, so 12/6 = 2 and 18/6 = 3, and GCD(2, 3) = 1. This is exactly what happens when you reduce a fraction to lowest terms.
Why do gear designers care about coprime tooth counts?
If two meshing gears have tooth counts that share a common factor, the same pair of teeth will always meet, causing uneven wear. With coprime tooth counts, every tooth on one gear eventually meshes with every tooth on the other, spreading wear uniformly and extending gear life.