Relatively Prime Calculator

Enter two integers to check if they are coprime, with full Euclidean algorithm steps.

🔗 What is a Relatively Prime Calculator?

Relatively prime numbers (also called coprime or mutually prime numbers) are two integers that share no common factor other than 1. In formal terms, two integers a and b are relatively prime when their greatest common factor (GCF, also written GCD) equals exactly 1. The numbers themselves do not need to be prime. Composite numbers can still be coprime with each other if their prime factorizations do not overlap at all.

This calculator accepts any two positive integers, computes their GCF using the Euclidean algorithm, and immediately states whether the pair is coprime. It also shows the full step-by-step Euclidean algorithm working, the prime factorization of each number in exponent notation, and a complete list of every divisor the two numbers share. For coprime inputs the list of common divisors is simply {1}.

Coprimality appears across a wide range of contexts. In elementary arithmetic it determines whether a fraction is already in lowest terms: a/b is fully reduced when GCF(a, b) = 1. In scheduling problems, two periodic events that repeat every a and b units will next coincide after exactly a times b time units (rather than fewer) when a and b are coprime. In number theory and abstract algebra, coprimality underlies the Chinese Remainder Theorem, Euler's totient function, and modular inverses. In cryptography, RSA requires the public exponent to be coprime with the totient of the modulus so that a unique decryption exponent exists.

A common source of confusion is the difference between a number being prime and two numbers being coprime. Primality is a property of one number (it has no divisors other than 1 and itself). Coprimality is a relationship between two numbers (their GCF is 1). Composite numbers can be coprime: 8 and 9 are both composite but coprime because they share no prime factor. Conversely, two prime numbers are always coprime with each other, but a prime is not coprime with its own multiples.

📐 Formula

a ⊥ b ⇔ GCF(a, b) = 1

a, b = the two positive integers being tested

GCF(a, b) = greatest common factor, computed via the Euclidean algorithm

⊥ = notation for "is coprime with" (relatively prime)

Euclidean algorithm: GCF(a, b) = GCF(b, a mod b), repeated until remainder = 0

Example: GCF(14, 15): 15 = 1 × 14 + 1; 14 = 14 × 1 + 0. GCF = 1, so 14 and 15 are coprime.

Consequence: If GCF(a, b) = 1, then LCM(a, b) = a × b

📖 How to Use This Calculator

Steps

Enter the first integer - Type the first positive integer into the First Number field. Any positive integer up to 1 billion is accepted.

Enter the second integer - Type the second positive integer into the Second Number field.

Click Check - Press the Check button (or hit Enter) to run the Euclidean algorithm instantly.

Read the verdict and GCF - The top row shows the GCF, a clear Yes or No for relatively prime, and the count of common divisors.

Review the step-by-step working - The Euclidean algorithm steps, prime factorizations, and full list of common divisors are shown below the main result so you can follow every stage of the calculation.

💡 Example Calculations

Example 1 - Two consecutive integers (14 and 15)

Are 14 and 15 relatively prime?

Apply the Euclidean algorithm: 15 = 1 × 14 + 1

14 = 14 × 1 + 0. Remainder is 0, so GCF = 1.

Prime factorizations: 14 = 2 × 7 and 15 = 3 × 5. No shared primes.

GCF = 1 ⇒ Yes, 14 and 15 are relatively prime.

Try this example →

Example 2 - Numbers that share a common factor (12 and 18)

Are 12 and 18 relatively prime?

Apply the Euclidean algorithm: 18 = 1 × 12 + 6

12 = 2 × 6 + 0. GCF = 6.

Prime factorizations: 12 = 2² × 3 and 18 = 2 × 3². Both share the primes 2 and 3, giving GCF = 6.

GCF = 6 ⇒ No, 12 and 18 are NOT relatively prime. Common divisors: 1, 2, 3, 6.

Try this example →

Example 3 - Two large composite numbers (35 and 64)

Are 35 and 64 relatively prime?

Prime factorizations: 35 = 5 × 7 and 64 = 2⁶. No shared prime factors.

Euclidean algorithm: 64 = 1 × 35 + 29; 35 = 1 × 29 + 6; 29 = 4 × 6 + 5; 6 = 1 × 5 + 1; 5 = 5 × 1 + 0. GCF = 1.

GCF = 1 ⇒ Yes, 35 and 64 are relatively prime. LCM(35, 64) = 35 × 64 = 2,240.

Try this example →

Example 4 - A prime and a composite (7 and 49)

Are 7 and 49 relatively prime?

Prime factorizations: 7 = 7 and 49 = 7². Both contain the prime 7.

Euclidean algorithm: 49 = 7 × 7 + 0. GCF = 7.

GCF = 7 ⇒ No, 7 and 49 are NOT relatively prime. A prime p is not coprime with any of its multiples.

Try this example →

❓ Frequently Asked Questions

What does relatively prime mean in mathematics?+

Two integers are relatively prime (also called coprime or mutually prime) when their greatest common factor (GCF) equals 1. This means they share no common prime factors. For example, 8 and 9 are relatively prime because 8 = 2 cubed and 9 = 3 squared, so they share no primes. Being relatively prime is a relationship between two numbers, not a property of either number alone. The number 1 is relatively prime to every positive integer.

How do you check if two numbers are relatively prime?+

Use the Euclidean algorithm to find the GCF. If the result is 1, the numbers are coprime. Steps: divide the larger by the smaller and take the remainder; replace the larger with the smaller and the smaller with the remainder; repeat until the remainder is 0. The last non-zero remainder is the GCF. Alternatively, write both prime factorizations and check if they share any prime. If no prime appears in both, GCF = 1 and the numbers are coprime.

Are all prime numbers relatively prime to each other?+

Yes, any two distinct prime numbers are always relatively prime. Since a prime p has no factors other than 1 and itself, two distinct primes share only the factor 1, giving GCF = 1. For example, GCF(7, 11) = 1. However, a prime is not relatively prime to its own multiples: GCF(7, 14) = 7, not 1, because 14 = 2 times 7 contains 7 as a factor.

What is the LCM of two relatively prime numbers?+

When GCF(a, b) = 1, the LCM equals the product: LCM(a, b) = a times b. This follows from the general identity LCM(a, b) = a times b divided by GCF(a, b). When the GCF is 1, dividing changes nothing. For example, GCF(8, 9) = 1, so LCM(8, 9) = 8 times 9 = 72. This is the most efficient way to compute LCM for coprime pairs.

Are consecutive integers always relatively prime?+

Yes, any two consecutive integers n and n+1 are always relatively prime. If a number d divided both n and n+1, it would also have to divide their difference (n+1) minus n = 1. The only positive integer that divides 1 is 1 itself, so GCF(n, n+1) = 1 for every positive integer n. Examples: GCF(99, 100) = 1, GCF(1000, 1001) = 1.

What is the difference between coprime and prime?+

A prime number has exactly two positive divisors (1 and itself). This is a property of a single number. Coprime (relatively prime) describes a relationship between two numbers: their GCF is 1. Composite numbers can be coprime: 8 = 2 cubed and 9 = 3 squared are both composite but coprime because they share no prime factors. Every pair of distinct primes is coprime, but primality and coprimality are separate concepts.

How is coprimality used in RSA encryption?+

RSA public-key encryption requires the public exponent e to be coprime with the totient phi(n) = (p-1)(q-1), where p and q are large primes. The coprimality condition GCF(e, phi(n)) = 1 guarantees that a modular inverse d exists such that e times d is congruent to 1 mod phi(n). This d is the private key. Without coprimality, the modular inverse does not exist and decryption becomes impossible, breaking the encryption scheme.

How do you use GCF to simplify a fraction?+

Divide both the numerator and denominator by their GCF to get the fully reduced fraction. For 18/24: GCF(18, 24) = 6, so divide both by 6 to get 3/4. The fraction is in lowest terms because GCF(3, 4) = 1, meaning 3 and 4 are relatively prime. A fraction a/b is fully simplified if and only if a and b are coprime. You can verify this using the Relatively Prime Calculator by entering the simplified numerator and denominator.

Can three or more numbers be mutually relatively prime?+

Yes. A set of integers is pairwise (mutually) relatively prime when every pair from the set has GCF = 1. For example, 6, 35, and 143 are pairwise coprime: GCF(6, 35) = 1, GCF(6, 143) = 1, and GCF(35, 143) = 1. This is a stronger condition than just requiring the GCF of the entire set to equal 1. The set {6, 10, 15} has overall GCF = 1 but is not pairwise coprime because GCF(6, 10) = 2.

What happens when I enter two equal numbers?+

When both inputs are the same number n, GCF(n, n) = n. Since n equals 1 only when the input is 1, the only equal pair that is relatively prime is (1, 1). For any n greater than 1, GCF(n, n) = n, so the pair is not coprime. The common divisors of n with itself are all divisors of n, and the Euclidean algorithm terminates in one step because n divided by n leaves remainder 0.

What is the Euler totient function and how does it relate to coprimality?+

Euler's totient function phi(n) counts how many integers from 1 to n are coprime with n. For a prime p, phi(p) = p minus 1 because every integer from 1 to p-1 is coprime with p. For n = 12: the integers coprime with 12 are 1, 5, 7, and 11, so phi(12) = 4. Euler's theorem states that a raised to phi(n) is congruent to 1 mod n whenever GCF(a, n) = 1. This underpins modular exponentiation in both number theory and modern cryptography.

Is 1 relatively prime to every number?+

Yes. GCF(1, n) = 1 for every positive integer n because 1 has no divisors other than 1 itself, so the greatest common divisor of 1 and any number is always 1. This makes 1 the universal coprime partner. It is also the only positive integer that is coprime with itself: GCF(1, 1) = 1, while GCF(n, n) = n for any n greater than 1.

🔗 Related Calculators

What does relatively prime mean in mathematics?

Two integers are relatively prime (also called coprime or mutually prime) when their greatest common factor (GCF) equals 1. This means they share no common prime factors. For example, 8 and 9 are relatively prime because 8 = 2 cubed and 9 = 3 squared, so they share no primes. The number 1 is relatively prime to every positive integer. Being relatively prime is about the relationship between two numbers, not a property of either number alone.

How do you check if two numbers are relatively prime?

Use the Euclidean algorithm to find the GCF of the two numbers. If the result is 1, the numbers are relatively prime. Steps: (1) Divide the larger by the smaller and take the remainder. (2) Replace the larger with the smaller and the smaller with the remainder. (3) Repeat until the remainder is 0. The last non-zero remainder is the GCF. If it equals 1, the numbers are coprime. Example: GCF(14, 15) gives remainder 14 = 0 times 15 + 14, then 15 = 1 times 14 + 1, then 14 = 14 times 1 + 0. GCF = 1, so they are coprime.

Are all prime numbers relatively prime to each other?

Yes, any two distinct prime numbers are always relatively prime. Since a prime p has no factors other than 1 and itself, two distinct primes share only the factor 1, giving GCF = 1. For example, GCF(7, 11) = 1. However, note that a prime is NOT relatively prime to its own multiples: GCF(7, 14) = 7, not 1.

What is the relationship between coprime numbers and LCM?

When two numbers a and b are relatively prime, their LCM equals their product: LCM(a, b) = a times b. This follows from the general identity LCM(a, b) = a times b divided by GCF(a, b), and when GCF = 1 the division changes nothing. For example, GCF(8, 9) = 1, so LCM(8, 9) = 72 = 8 times 9.

Are 0 and any number relatively prime?

No. GCF(0, n) = n for any positive integer n (every integer divides 0), so GCF(0, n) equals n, which is greater than 1 for n greater than 1. Only GCF(0, 1) = 1, making 0 and 1 the single coprime pair involving 0 by this convention. Most calculators, including this one, require positive inputs to avoid this edge case.

What are some examples of relatively prime pairs?

Common coprime pairs include: (8, 9), (14, 15), (35, 36), (4, 9), (5, 7), (12, 25), (8, 15). All consecutive integers form coprime pairs. Two numbers whose prime factorizations share no prime in common are always coprime, regardless of how large they are.

Are 1 and any number always relatively prime?

Yes. GCF(1, n) = 1 for every positive integer n because the only positive divisor of 1 is 1 itself. So 1 is coprime with every positive integer. This makes 1 unique: it is the only positive integer coprime with itself (GCF(1, 1) = 1), while every other number has GCF(n, n) = n, which equals 1 only when n = 1.

What does relatively prime mean in number theory and cryptography?

In number theory, coprimality is central to modular arithmetic. Euler's theorem states that a raised to the power phi(n) is congruent to 1 mod n whenever GCF(a, n) = 1, where phi is Euler's totient function. RSA public-key cryptography exploits this: the key exponent e must satisfy GCF(e, phi(n)) = 1 to guarantee a unique decryption exponent d exists. Without coprimality, modular inverses fail to exist and the encryption scheme breaks down.

Can three or more numbers be mutually relatively prime?

Yes, a set of integers is mutually (or pairwise) relatively prime when every pair from the set has GCF = 1. Example: 6, 35, and 143 are pairwise coprime because GCF(6, 35) = 1, GCF(6, 143) = 1, and GCF(35, 143) = 1. Note that pairwise coprime is stronger than just requiring GCF of the whole set to be 1. For instance, GCF(6, 10, 15) = 1, but the numbers are not pairwise coprime because GCF(6, 10) = 2.

How does the Euclidean algorithm find the GCF?

The Euclidean algorithm uses the property that GCF(a, b) = GCF(b, a mod b). Starting with the two numbers, repeatedly replace the larger with the smaller and the smaller with the remainder, until the remainder is 0. The last non-zero value is the GCF. For GCF(48, 18): 48 = 2 times 18 + 12; 18 = 1 times 12 + 6; 12 = 2 times 6 + 0. GCF = 6. The algorithm is efficient even for numbers with hundreds of digits.

What is the difference between coprime and prime?

A prime number has exactly two positive divisors (1 and itself), and this is a property of a single number. Coprime (relatively prime) describes a relationship between two numbers: they are coprime if their GCF is 1. A composite number can be coprime with another number. For example, 8 (composite, 2 cubed) and 9 (composite, 3 squared) are coprime because they share no prime factors.

How do you simplify a fraction using GCF?

Divide both numerator and denominator by their GCF. For 18/24: GCF(18, 24) = 6, so 18/24 = 3/4. The fraction is now in lowest terms because 3 and 4 are relatively prime (GCF = 1). A fraction a/b is in lowest terms if and only if GCF(a, b) = 1. You can verify this with the Relatively Prime Calculator by entering the simplified numerator and denominator.

📌 Quick Tips

💡Two numbers are relatively prime if and only if their GCF equals 1. This is the fastest check: run the Euclidean algorithm and see if it terminates at 1.

💡Any two consecutive integers n and n+1 are always relatively prime. They share no common factor because any factor of both would have to divide their difference, which is 1.

💡A prime number p is relatively prime to any integer n that is not a multiple of p. So 7 is coprime with 9, 10, 11, 13, 20, and every number not divisible by 7.

💡If GCF(a, b) = 1, then LCM(a, b) = a times b. This is the quickest way to find the LCM of two coprime numbers without any extra steps.

💡In RSA encryption, the public key exponent e must be relatively prime to phi(n) = (p-1)(q-1). Coprimality is a core requirement for the modular inverse to exist.