Home » Math Theory » Numbers » Co-prime Numbers

# Co-prime Numbers

Before we dive into the actual definition of Co-prime Numbers, let’s have a recap first of what a Prime Number is.

A prime number is a positive integer or number that has factors of 1 and the number itself. This means if a number has more than two factors, it is not prime but rather a composite number. And yes, we do not consider the negative integers because they have more than two factors. Let’s take a look at the illustration below to see the difference.

Now, let us list the factors of each number.

2 = {1, 2}

-2 = {-2, -1, 1, 2}

By looking at the factor tree and the listed form of the factors above, we can easily conclude that positive 2 is a prime number because it has only two factors, which are 1 and itself. On the other hand, negative 2 is not a prime number, because it can also have -1 and 2 as factors. For this reason, we can expect that Co-prime numbers are pairs of positive numbers with unique properties, properties that we will see later.

Using the definition of Prime Numbers, we notice that each number must have 1 as its “primary” factor. But now, we are going to talk about pairs of numbers that must have a “common primary” factor of 1. This gives us now the definition of Co-prime numbers.

## Definition

Co-prime numbers (also known as Relatively Prime Numbers) are a pair of numbers that have the Greatest Common Factor (GCF) as 1. In other words, these are numbers that have no common or same factors other than 1. To check whether the pair are co-prime to each other, we can list their factors and find their Greatest Common Factor or GCF.

## Notation in Number Theory

In Number Theory, co-prime numbers have the notation of GCD (a, b) = 1, or the Greatest Common Divisor of the pair of numbers (i.e. a and b) must be 1 to consider as co-prime numbers. For instance, let’s find the GCD of 37 and 13 with the Modular Arithmetic method to check if they are relatively prime or co-prime numbers.

GCD (37, 13); where a = 37, b = 13

GCD (a, b) = GCD (b, a mod b)

GCD (37, 13) = GCD (13, 37 mod 13)

= GCD (13, 11)

GCD (13, 11) = GCD (11, 13 mod 11)

= GCD (11, 2)

GCD (11, 2) = GCD (2, 11 mod 2)

= GCD (2, 1)

GCD (2, 1) = GCD (1, 2 mod 1)

= GCD (1, 0)

Since GCD (37, 13) = GCD (1, 0), we can declare that GCD (37, 13) = 1. It means that 37 and 13’s Greatest Common Divisor is 1, and they are co-prime numbers.

## “Divisors” VS “Factors”

But you may ask, “From the definition, the term ‘factor’ is used rather than ‘divisor’, are there any differences?” From what we did a while ago, we can divide 37 to any number (also known as the divisor), but the problem is, there would be a remainder. For instance, we divided 37 (dividend) by 13 (divisor), but we still have a remainder of 11.

On the other hand, factors are divisors that can divide a number exactly or cannot result in any remainder. For that reason, the Greatest Common Factor (GCF) of the pair of numbers is commonly used to verify whether they are relatively prime to each other. Furthermore, you may notice that we can more quickly check if they are co-primes or not using only the factors rather than with divisors.

However, this does not mean that idea of GCD is not useful. As a matter of fact, this notation is widely used in real-life applications such as network security.

In a nutshell, for this topic, you can expect that there will be no negative numbers involved. Also, the term Greatest Common Factor will be used to verify if a pair of numbers are relatively prime or not.

## Examples of Co-prime Numbers

Example 1

7 and 11

For this situation, it is easier to visualize the factors by making a factor tree for each one of them so that we can list them later.

With these visualizations, we can now list their factors.

7 = {1, 7}

11 = {1, 11}

Looking at the list, we can notice that they have 1 as their Greatest Common Factor or GCF.

7 = {1, 7}

11 = {1, 11}

Therefore, 7 and 11 are relatively prime or co-prime numbers. Also, 7 and 11 are both prime numbers, how about a pair composite and prime numbers? Let’s see in the next example.

Example 2

6 and 13

Here, we have a composite (6) and a prime (13) number. Again, let’s create a factor tree to list their factors later.

Now, we can list out the factors.

6 = {1, 2, 3, 6}

13 = {1, 13}

Here, we can notice that both of the numbers have the GCF of 1.

6 = {1, 2, 3}

13 = {1, 13}

Hence 6, even though a composite number, is relatively prime to 13 which is a prime number. How about if we have a pair of composite numbers? Let’s try it in the next example.

Example 3

(15, 20)

For this case, let’s try it without using a factor tree, and just list the factors.

15 = {1, 3, 5, 15}

20 = {1, 2, 4, 5, 10, 20}

By looking at the list, we can see that they have 1 as a common factor, but they have 5 as well.

15 = {1, 3, 5, 15}

20 = {1, 2, 4, 5, 10, 20}

This means that 5 and 20’s Greatest Common Factor is 5 and not 1. Therefore, 15 and 20 are NOT co-prime numbers. However, this does not actually mean that all pairs of composite numbers are not co-prime. Let’s prove it in the next example.

Example 4

(8, 9)

8 = {1, 2, 4, 8}

9 = {1, 3, 9}

Here, we can see that even though they are both composite numbers, they have 1 as their GCF.

8 = {1, 2, 4, 8}

9 = {1, 3, 9}

Therefore, 8 and 9 are co-prime numbers.

## Properties of Co-prime Numbers

From the examples we discussed, we realized the properties of co-prime numbers.

Property 1:

Any pair of prime numbers are relatively prime to each other.

Since prime numbers only have 1 and themselves as the factors, it is automatic that their Greatest Common Factor (GCF) is 1.

Examples: (7, 11), (2, 5), and (3, 7)

Property 2:

Numbers that are consecutive are considered as co-prime.

Since these numbers are just next to each other, their GCF would also be 1 by default.

Examples: (3, 4), (19, 20), and (99, 100)

Property 3:

A pair of composite numbers can also be relatively prime, except even numbers (because they have a common factor of 2 which is greater than 1). Furthermore, with this idea, numbers that are multiples of the same number are not considered as co-prime.

Examples: (4, 15) 🗸 (both composite, but GCF is 1)

(6, 12) ✕ (since they are even numbers)

(15, 20) ✕ (since they are both multiples of 5)

Property 4:

The Least Common Multiple or LCM of co-prime numbers is their product.

Example 1: (4, 15)

4 15 = 60

To prove this, we can list out each of their multiples.

4   = {4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, …}

15 = {15, 30, 45, 60, 75, 90, 105, …}

Therefore, (4, 15) are relatively prime or co-prime numbers.

Example 2: (6, 12)

6 × 12 = 72

Again, let us list their multiples.

6 = {6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72,…}

12 = {12, 24, 36, 48, 60, 72, …}

Here, we can notice that they share the same multiples of 72. However, the least among them is 12.

6 = {6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72,…}

12 = {12, 24, 36, 48, 60, 72, …}

Hence, (6, 12) are not co-prime numbers.

For this reason, if the numbers are not consecutive, getting the product of the pair of numbers and checking if it is their LCM would also be a good trick to verify quickly whether they are co-prime numbers.

## Co-prime Numbers from 1-100

For you to be familiar with Co-prime Numbers, let us explore the pairs of them from 1-100. There are several co-prime numbers within this range, including the pairs that are consecutive or next to each other. Here are some of them.

## Co-prime NumbersActivity

Now, let’s have some exercises for you to identify whether the pair in the first column is co-prime or not.

Directions: List in the second column the factors of each pair of the numbers from the first column. Then, write the Greatest Common Factor or GCF of each pair in the third column. In the fourth column, write Yes if the pair is co-prime and No if it is not. Lastly, write the reason (referencing the Properties of Co-prime Numbers) for your answers from the fourth column to the fifth column. The first row serves as an example.

Solution for the Activity:

## Where are Co-prime numbers used for?

So, we mastered the knowledge of co-prime numbers. But, what are their purposes? In reality, there are many uses of relatively prime numbers, but here are common applications.

1. Cryptography and Cybersecurity

1. Mechanical Engineering

The concept of relatively prime numbers is well used by engineers especially in contacting gears. Keep in mind that gears must function without any damage. And to do that, the number of teeth of the two gears should be relatively prime so that they will not be rubbing in each other which can result in dismantling. For instance, a pair of gears with teeth of 30 and 35 is considered poor, because the second gear may hit some teeth of the first gear. While having co-prime numbers of teeth such as 31 and 35 is considered excellent.

## Key Facts & Summary

• Co-prime or relatively prime numbers are a pair of numbers that has only 1 as the Greatest Common Factor or GCF.
• In number theory, co-prime numbers are notated as GCD (a, b) = 1.
• The term divisors is pertaining to all numbers that can divide a number but can have a remainder. On the other hand, factors are referring to the divisors that can divide a number exactly.
• Relatively prime or co-prime numbers have unique properties:
• All pairs of prime numbers are relatively prime.
• Consecutive numbers are co-prime by default.
• Pair of even numbers and numbers that are multiples of the same number are not co-prime.
• The product of co-prime numbers must also be their Least Common Multiple or LCM.
• There is infinite list of co-prime numbers within the range of 1-100.
• There are many ways co-prime numbers can be applied to our daily lives.