Relatively Prime Calculator

Relatively Prime Calculator

Popular AI Skill PRO

Enter Calculation

Formula

Coprime⇔gcd⁡(a,b)=1\text{Coprime} \iff \gcd\left(\text{a},\ \text{b}\right) = 1

Example

Coprime⇔gcd⁡(84,126)=1=1\text{Coprime} \iff \gcd\left(84,\ 126\right) = 1 = 1
Usage stats

Advertisement

Results

Are 84 and 126 relatively prime?
No
gcd(84, 126) = 42
Greatest common divisor 42
Relatively prime No (gcd > 1)

Report an error on this page

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.

Advertisement
Two numbers sharing only the common factor 1, shown as overlapping factor sets
Two numbers are coprime when their only shared factor is 1, so \(\gcd(a, b) = 1\).

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.

Euclidean algorithm steps reducing two numbers down to gcd of 1
The Euclidean algorithm reduces the pair step by step until the remainder reveals \(\gcd = 1\).

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)

  1. \(1071 \bmod 1024 = 47\)
  2. \(1024 \bmod 47 = 37\)  (since \(47 \times 21 = 987\) and \(1024 - 987 = 37\))
  3. \(47 \bmod 37 = 10\)
  4. \(37 \bmod 10 = 7\)
  5. \(10 \bmod 7 = 3\)
  6. \(7 \bmod 3 = 1\)
  7. \(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)

  1. \(84 \bmod 126 = 84\), so the first step simply swaps the pair to \((126,\ 84)\)
  2. \(126 \bmod 84 = 42\)
  3. \(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)

  1. \(54 \bmod 25 = 4\)  (since \(25 \times 2 = 50\) and \(54 - 50 = 4\))
  2. \(25 \bmod 4 = 1\)  (since \(4 \times 6 = 24\) and \(25 - 24 = 1\))
  3. \(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.

Advertisement

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.

CaseInputResult
1 and 91, 9Yes
0 and 50, 5No

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.

Last updated:

Most popular in Math and Statistics

View all Math and Statistics calculators