What is the Relatively Prime Calculator?
Two integers are relatively prime (also called coprime) when the only positive integer that divides both of them is 1. In other words, their greatest common divisor (gcd) is exactly 1. This calculator takes two whole numbers and instantly tells you whether they are coprime, along with their gcd.
Which prime number tool do you need?
- Prime number checker: whether a number is prime, with the previous and next prime.
- Prime number calculator: whether a number is prime and its smallest factor other than 1.
- Nth prime: the nth prime, or a list of the first N primes.
- Prime factorization: the prime factors of a number, with a factor tree.
- Relatively prime (this page): whether two numbers are coprime (no common factor other than 1).
How to use it
Enter your two integers in the fields for a and b and submit. The tool computes \(\gcd(a, b)\) using the Euclidean algorithm. If the gcd is 1, the numbers are relatively prime; otherwise they share a common factor and are not coprime. Negative signs are ignored because coprimality depends only on absolute values.
The formula explained
The Euclidean algorithm repeatedly replaces the pair \((a, b)\) with \((b, a \bmod b)\) until the second value becomes 0. The last non-zero value is the gcd. The numbers are coprime precisely when this gcd equals 1:
$$\text{Coprime} \iff \gcd\left(\text{a},\ \text{b}\right) = 1$$For example, 8 and 15 share no prime factors, so \(\gcd = 1\) and they are coprime, even though neither is itself prime.
Worked example
Take \(a = 12\) and \(b = 35\). The factors of 12 are 2 and 3; the factors of 35 are 5 and 7. They share no common prime factor, so \(\gcd(12, 35) = 1\). Therefore 12 and 35 are relatively prime. By contrast, 12 and 18 share the factor 6, so \(\gcd = 6\) and they are not coprime.
More Coprime Examples
The Euclidean algorithm repeatedly replaces the pair \((a,\ b)\) with \((b,\ a \bmod b)\) until the remainder is \(0\). The last non-zero remainder is \(\gcd(a,b)\), and the pair is relatively prime exactly when that value is \(1\).
Example 1 — a large coprime pair: gcd(1071, 1024)
- \(1071 \bmod 1024 = 47\)
- \(1024 \bmod 47 = 37\) (since \(47 \times 21 = 987\) and \(1024 - 987 = 37\))
- \(47 \bmod 37 = 10\)
- \(37 \bmod 10 = 7\)
- \(10 \bmod 7 = 3\)
- \(7 \bmod 3 = 1\)
- \(3 \bmod 1 = 0\) → stop
The last non-zero remainder is \(1\), so \(\gcd(1071, 1024) = \) 1. Verdict: 1071 and 1024 are relatively prime (coprime) — even though neither is prime (\(1071 = 3 \times 3 \times 7 \times 17\) and \(1024 = 2^{10}\)), they share no prime factor.
Example 2 — a non-coprime pair: gcd(84, 126)
- \(84 \bmod 126 = 84\), so the first step simply swaps the pair to \((126,\ 84)\)
- \(126 \bmod 84 = 42\)
- \(84 \bmod 42 = 0\) → stop
The last non-zero remainder is \(42\), so \(\gcd(84, 126) = \) 42. Verdict: 84 and 126 are NOT relatively prime. Factoring confirms it: \(84 = 2^2 \times 3 \times 7\) and \(126 = 2 \times 3^2 \times 7\), so the shared part is \(2 \times 3 \times 7 = 42\). Note that putting the smaller number first costs only one extra swap step — the algorithm does not require ordered inputs.
Example 3 — two composite numbers that are still coprime: gcd(25, 54)
- \(54 \bmod 25 = 4\) (since \(25 \times 2 = 50\) and \(54 - 50 = 4\))
- \(25 \bmod 4 = 1\) (since \(4 \times 6 = 24\) and \(25 - 24 = 1\))
- \(4 \bmod 1 = 0\) → stop
The last non-zero remainder is \(1\), so \(\gcd(25, 54) = 1\). Verdict: 25 and 54 are relatively prime. Here \(25 = 5^2\) and \(54 = 2 \times 3^3\); the prime sets \(\{5\}\) and \(\{2, 3\}\) are disjoint. This is the key point about coprimality: it is a property of a pair, not of the individual numbers — neither number has to be prime.
What Your Result Means
The calculator reports a single number, \(d = \gcd(a,b)\), and the verdict follows from whether \(d\) equals \(1\). Each branch carries a specific set of standard number-theoretic consequences.
If gcd(a, b) = 1 — the numbers are relatively prime
- The fraction \(a/b\) is already in lowest terms. There is no integer greater than \(1\) that cancels from numerator and denominator.
- \(a\) has a modular multiplicative inverse mod \(b\) (and \(b\) has one mod \(a\)): the congruence \(a \cdot x \equiv 1 \pmod b\) is solvable, with a unique solution among the residues \(0, 1, \ldots, b-1\). This follows from Bézout's identity, which guarantees integers \(x, y\) with $$a x + b y = 1$$ Reducing that equation mod \(b\) leaves \(a x \equiv 1\). For \(a = 25\), \(b = 54\): \(25 \cdot 13 - 54 \cdot 6 = 325 - 324 = 1\), so the inverse of \(25\) mod \(54\) is \(13\).
- The lcm is the plain product: \(\operatorname{lcm}(a,b) = a \cdot b\). With \(25\) and \(54\), \(\operatorname{lcm} = 25 \times 54 = 1350\).
- The Chinese Remainder Theorem applies to the moduli \(a\) and \(b\). Any system \(x \equiv r \pmod a\), \(x \equiv s \pmod b\) has a solution, unique modulo \(a \cdot b\) — e.g. unique mod \(1350\) for the moduli \(25\) and \(54\).
- Stepping by \(a\) around a cycle of length \(b\) visits every position. The multiples \(0, a, 2a, 3a, \ldots\) reduced mod \(b\) run through all \(b\) residues before repeating; \(a\) generates the full cycle. If the gcd were \(d > 1\), the walk would touch only the \(b/d\) positions divisible by \(d\).
- Equivalently, the prime factorisations of \(a\) and \(b\) share no prime, and \(a\) is counted by Euler's totient \(\varphi(b)\).
If gcd(a, b) = d > 1 — the numbers are not relatively prime
- The fraction \(a/b\) reduces. Dividing both parts by \(d\) gives \((a/d)\,/\,(b/d)\), and that pair is coprime, so the reduced fraction is in lowest terms. With \(a = 84\), \(b = 126\), \(d = 42\): \(84/126 = 2/3\), and \(\gcd(2,3) = 1\).
- No modular inverse of \(a\) mod \(b\) exists. The congruence \(a \cdot x \equiv 1 \pmod b\) has no solution, because every value of \(a x - 1\) that is a multiple of \(b\) would force \(d \mid 1\). More generally \(a x \equiv c \pmod b\) is solvable only when \(d \mid c\), and then it has exactly \(d\) solutions mod \(b\).
- The lcm is smaller than the product: \(\operatorname{lcm}(a,b) = \dfrac{a \cdot b}{d}\). For \(84\) and \(126\): \(\operatorname{lcm} = \dfrac{84 \times 126}{42} = \dfrac{10584}{42} = 252\).
- Bézout's identity still holds, but in the form \(a x + b y = d\) — the smallest positive value \(a x + b y\) can take is \(d\), never \(1\). The Chinese Remainder Theorem in its basic form does not apply to the moduli \(a\) and \(b\).
Edge cases
- \(\gcd(1, n) = 1\) for every integer \(n\), so \(1\) is coprime to everything, including \(0\) and itself: \(\gcd(1,1) = 1\).
- \(\gcd(0, n) = |n|\), because every integer divides \(0\). Therefore \(0\) is coprime only with \(1\) and \(-1\).
- \(\gcd(0, 0)\) has no greatest common divisor — every integer divides \(0\), so the set of common divisors is unbounded. It is conventionally defined as \(0\), and the pair \((0,0)\) is not coprime.
- Sign is irrelevant: \(\gcd(a,b) = \gcd(|a|, |b|)\), so \(\gcd(-25, 54) = 1\) just as \(\gcd(25, 54) = 1\).
- A number is coprime to itself only when \(|a| = 1\), since \(\gcd(a,a) = |a|\).
Conventions and edge cases
Each case below was run through this calculator; the result column is what it actually returns.
| Case | Input | Result |
|---|---|---|
| 1 and 9 | 1, 9 | Yes |
| 0 and 5 | 0, 5 | No |
Checked on 2026-11-08
FAQ
Do coprime numbers have to be prime? No. Coprime means they share no common factor greater than 1; the numbers themselves need not be prime (e.g., 8 and 9).
Is 1 coprime with every number? Yes. \(\gcd(1, n) = 1\) for any integer \(n\), so 1 is relatively prime to every integer.
Are two even numbers ever coprime? No. Any two even numbers share the factor 2, so their gcd is at least 2.