Relatively Prime (Coprime) Calculator - GCD = 1

What Does Relatively Prime (Coprime) Mean?

Two integers $a$ and $b$ are relatively prime, also called coprime or mutually prime, when their only common positive factor is 1. In other words, the Greatest Common Divisor (GCD) of the two numbers is exactly 1.

The important point is that two numbers do not have to be prime themselves to be relatively prime. A pair of composite numbers can also be relatively prime if they do not share any factor greater than 1. A Relatively Prime Calculator checks this relationship by finding the GCD of the two numbers.

Example: 14 and 15

• Factors of 14: 1, 2, 7, 14.
• Factors of 15: 1, 3, 5, 15.
• Common factor: Only 1.
• $\gcd(14,15)=1$.
• Therefore, 14 and 15 are relatively prime.

How to Check if Two Numbers Are Relatively Prime

There are several ways to determine whether two integers are relatively prime. The most direct method is to find their common factors and check whether 1 is the only factor they share. For larger numbers, calculating the Greatest Common Divisor is much more efficient.

1. Choose the two integers you want to compare.
2. Find the factors of both numbers, or calculate their GCD.
3. Check the greatest common divisor.
4. If the GCD is 1, the numbers are relatively prime.
5. If the GCD is greater than 1, the numbers are not relatively prime.

For example, consider 8 and 15. The factors of 8 are 1, 2, 4, and 8, while the factors of 15 are 1, 3, 5, and 15. Their only common factor is 1, so $\gcd(8,15)=1$ and the pair is relatively prime.

Using GCD to Determine Relatively Prime Numbers

The GCD provides the simplest mathematical test for relatively prime numbers. The GCD is the largest positive integer that divides both numbers without leaving a remainder.

If the GCD is 2, 3, 5, or any other number greater than 1, the two integers have a common factor and therefore are not relatively prime.

Example: 18 and 25

The factors of 18 are 1, 2, 3, 6, 9, and 18. The factors of 25 are 1, 5, and 25. The only common factor is 1.

Therefore, 18 and 25 are relatively prime even though both numbers are composite.

Relatively Prime vs. Prime Numbers

The terms prime and relatively prime describe different properties. A prime number is an individual integer greater than 1 that has exactly two positive factors: 1 and itself. Relatively prime describes the relationship between two integers.

For example, 7 is a prime number. However, 8 and 15 are not prime numbers, but they are relatively prime because their GCD is 1.

Examples of Relatively Prime Numbers

Example 1: 9 and 10

The factors of 9 are 1, 3, and 9. The factors of 10 are 1, 2, 5, and 10. Their only common factor is 1.

Therefore, 9 and 10 are relatively prime.

Example 2: 21 and 22

The factors of 21 are 1, 3, 7, and 21. The factors of 22 are 1, 2, 11, and 22. Since they share only 1:

So, 21 and 22 are relatively prime.

Example 3: 12 and 18

The factors of 12 include 1, 2, 3, 4, 6, and 12. The factors of 18 include 1, 2, 3, 6, 9, and 18. They have several common factors, including 2, 3, and 6.

Because the GCD is 6 rather than 1, 12 and 18 are not relatively prime.

Relatively Prime Integers Less Than 20

When looking at positive integers less than 20, many pairs are relatively prime. Two consecutive positive integers are always relatively prime because any common divisor of consecutive integers must divide their difference, which is 1.

Examples include:

• 1 and 2
• 2 and 3
• 3 and 4
• 5 and 6
• 8 and 9
• 11 and 12
• 14 and 15
• 18 and 19

These pairs have a GCD of 1. However, numbers do not have to be consecutive to be relatively prime. For example, 8 and 15 are separated by 7 but are still relatively prime.

How the Relatively Prime Calculator Works

A Relatively Prime Calculator determines whether two integers have any common factor greater than 1. The key calculation is their GCD. If the GCD equals 1, the calculator identifies the numbers as relatively prime or coprime.

For example, suppose you enter 35 and 64. The calculator finds:

Since the result is 1, 35 and 64 are relatively prime. If you enter 36 and 48, the GCD is 12, so the numbers are not relatively prime.

Finding Relatively Prime Numbers with the Euclidean Algorithm

For large integers, listing every factor can take time. The Euclidean algorithm provides an efficient way to find the GCD. It repeatedly divides the larger number by the smaller number and continues with the remainder until the remainder becomes zero.

Example: 48 and 65

Start by dividing 65 by 48:

The last non-zero remainder is 1, so:

Therefore, 48 and 65 are relatively prime.

Can Two Composite Numbers Be Relatively Prime?

Yes. This is an important concept because being relatively prime does not mean that both numbers must be prime. It only means that the two numbers have no common factor greater than 1.

Consider 14 and 15. Both numbers are composite, but their GCD is 1. Similarly, 18 and 25 are both composite and are relatively prime.

This shows why the GCD test is more reliable than simply checking whether the individual numbers are prime.

Pairwise Relatively Prime Numbers

A group of integers is called pairwise relatively prime when every pair of distinct numbers in the group has a GCD of 1. For example, 5, 8, and 9 are pairwise relatively prime because:

Therefore, every pair in the group is relatively prime.

Important Properties of Relatively Prime Numbers

Relatively prime numbers have several useful properties that make them important in number theory and arithmetic.

• GCD is 1: This is the defining property of a relatively prime pair.
• They do not need to be prime: Composite numbers can also be relatively prime.
• Consecutive integers are relatively prime: Any two consecutive integers have a GCD of 1.
• They share no prime factor: If two integers had a common prime factor, their GCD would be greater than 1.
• 1 is relatively prime to every positive integer: The GCD of 1 and any positive integer is 1.

Why Are Relatively Prime Numbers Important?

Relatively prime numbers are used throughout mathematics. They are especially important when simplifying fractions, working with ratios, studying divisibility, and solving problems involving number theory. A fraction is in lowest terms when its numerator and denominator are relatively prime.

Example: Simplifying a Fraction

Consider the fraction $12/18$. Since:

the numerator and denominator are not relatively prime. Dividing both by 6 gives:

Now 2 and 3 are relatively prime because $\gcd(2,3)=1$. Therefore, $2/3$ is in simplest form.

Common Mistakes When Checking Relatively Prime Numbers

Some common misunderstandings can make it difficult to identify relatively prime numbers correctly.

• Thinking both numbers must be prime: Relatively prime describes a relationship, so composite numbers can also form a coprime pair.
• Checking only whether the numbers are consecutive: Consecutive numbers are always relatively prime, but many non-consecutive pairs are also relatively prime.
• Ignoring common factors: If the GCD is greater than 1, the numbers are not relatively prime.
• Confusing GCD with the larger number: The GCD is the greatest number that divides both values exactly.
• Assuming different numbers are automatically coprime: Two different numbers can have several common factors, such as 12 and 18.

Quick Examples of Relatively Prime and Non-Relatively Prime Pairs

Summary

Two integers are relatively prime, or coprime, when their Greatest Common Divisor is 1. They do not need to be prime numbers themselves. For example, 14 and 15 are both composite, yet they are relatively prime because they share no common factor other than 1.

The easiest general test is to calculate the GCD. If $\gcd(a,b)=1$, the numbers are relatively prime. If the GCD is greater than 1, they are not. Use the Relatively Prime Calculator to check a pair quickly and verify whether the two integers are coprime.