Relatively Prime Calculator

What Are Relatively Prime (Coprime) Numbers?

In number theory, two integers $a$ and $b$ are called relatively prime (or coprime, or mutually prime) if the only positive integer that evenly divides both of them is $1$. In formal notation:

$$\gcd(a, b) = 1$$

Notice that two numbers do not need to be prime numbers themselves to be relatively prime to each other. For instance, $14$ (which factors as $2 \times 7$) and $15$ (which factors as $3 \times 5$) are both composite numbers, yet their greatest common divisor is $1$. Thus, $14$ and $15$ are relatively prime.

How to Determine if Two Numbers Are Coprime

There are two standard methods to check whether integers are relatively prime:

1. Prime Factorization Method

Decompose each number into its prime factors. If the two factorizations share zero common prime factors, the numbers are coprime:

Let $a = 28 = 2^2 \times 7$
Let $b = 45 = 3^2 \times 5$
Common prime factors: $\emptyset$ (none). Therefore, $\gcd(28, 45) = 1$.

2. The Euclidean Algorithm

For larger integers, repeatedly apply integer division with remainder: $\gcd(a, b) = \gcd(b, a \bmod b)$ until the remainder reaches $0$. The final non-zero remainder is the greatest common divisor. If that divisor equals $1$, the numbers are coprime.

Mutual vs. Pairwise Coprimality in Sets

When considering three or more numbers $\{a_1, a_2, \dots, a_n\}$, mathematics distinguishes between two levels of coprimality:

Type	Definition	Example
Pairwise Coprime	Every distinct pair of numbers in the set has $\gcd(a_i, a_j) = 1$.	$\{5, 7, 9\}$: $\gcd(5,7)=1$, $\gcd(5,9)=1$, $\gcd(7,9)=1$.
Mutually (Jointly) Coprime	The overall greatest common divisor across all elements is $1$, even if individual pairs share factors.	$\{6, 10, 15\}$: $\gcd(6,10,15) = 1$, but $\gcd(6,10)=2$, $\gcd(10,15)=5$, $\gcd(6,15)=3$. Not pairwise coprime, but mutually coprime!

Euler's Totient Function $\phi(N)$

Euler's totient function (also called phi function, denoted $\phi(N)$) counts the positive integers up to $N$ that are relatively prime to $N$. If $p_1, p_2, \dots, p_k$ are the distinct prime factors of $N$:

$$\phi(N) = N \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$$

For example, for $N = 12$, the distinct prime factors are $2$ and $3$:

$$\phi(12) = 12 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4$$

The $4$ integers less than or equal to $12$ that are coprime to $12$ are $\{1, 5, 7, 11\}$.

Worked Examples

Example 1: Are 35 and 64 Relatively Prime?

Find factors of $35$: $35 = 5 \times 7$.
Find factors of $64$: $64 = 2^6$.
Compare factor sets: there are no shared prime factors.
Conclusion: $\gcd(35, 64) = 1$. Yes, $35$ and $64$ are relatively prime.

Example 2: Are 42 and 99 Relatively Prime?

Find factors of $42$: $42 = 2 \times 3 \times 7$.
Find factors of $99$: $99 = 3^2 \times 11$.
Both numbers share the prime factor $3$.
Conclusion: $\gcd(42, 99) = 3 > 1$. No, $42$ and $99$ are not relatively prime.

Related Number Theory Tools

Explore related integer and arithmetic calculators:

Prime Factors Calculator: Find prime factorizations and factor trees.
Prime Number Calculator: Test primality and find next/previous prime numbers.
Modulo Calculator: Compute modular remainders and congruences.
First N Prime Numbers: Generate lists of prime numbers up to any bound.

Frequently Asked Questions

What does it mean for two numbers to be relatively prime?

Two numbers are relatively prime (or coprime) if their greatest common divisor (GCD) is equal to 1. This means they have no common positive factors other than the number 1.

Do relatively prime numbers have to be prime?

No. Individual numbers can be composite (non-prime) and still be relatively prime to each other. For example, 8 and 9 are both composite numbers, but gcd(8, 9) = 1, so they are relatively prime.

Is 1 relatively prime to every number?

Yes. For any positive integer n, gcd(1, n) = 1. Therefore, 1 is coprime to every positive integer, including itself.

What is the difference between mutually coprime and pairwise coprime?

A set of numbers is mutually coprime if no single factor greater than 1 divides all of them simultaneously (overall GCD is 1). A set is pairwise coprime if every possible pair within the set is coprime. Pairwise coprimality is a much stronger condition; for example, {6, 10, 15} is mutually coprime, but not pairwise coprime.

Why is coprimality important in cryptography and computer science?

Coprimality is fundamental in modern public-key cryptography algorithms like RSA, the Chinese Remainder Theorem, hash functions, and pseudo-random number generation, where modular arithmetic inverses depend on numbers having gcd equal to 1.

Report