Sales Toll Free No: 1-855-666-7446

Coprime

Top

Numbers are found everywhere in mathematics. In fact, this subject is all about numbers. When we progress in mathematics, we study about different types of numbers; starting from the simplest ones such as - natural numbers, whole numbers, real numbers, rational numbers, irrational numbers, odd numbers, even numbers, integers ; up to little complicated number; for example - prime, composite, coprime etc.

Each kind of number has its own importance in the field of mathematics. In this article, we are going to discuss about coprime numbers. Coprime numbers are actually a type of prime numbers. We can say that if two numbers are prime for each other, i.e. if two numbers possess no common factors except for 1, then these two numbers are known as coprime numbers. Let us go ahead and learn more about coprime numbers below.

Definition

Back to Top
Let us first define prime numbers. A number that has no divisor other than one and itself, is called a prime number. For example - 5, 3, 17, 13 etc. Two numbers are said to be coprime if they contain no common factor other than one. In other words, if there exists no common number that divides two given numbers, then the two numbers are called coprime (co-prime) numbers. These numbers are also termed as mutually prime or relatively prime, since two coprime numbers are specifically prime for each other.

Let us suppose that there are two integers (say x and y). If x and y do not have any positive common factor other than 1 or if the highest common factor (HCF) of x and y is one, then x and y are known as coprime numbers or simply coprimes. Symbolically, we write this in the following way -
x $\perp$ y

Sometimes, for HCF, the notation (x , y) is used. Therefore, for coprime numbers, we write as -
(x , y) = 1

For Example : 52 and 27 are coprime numbers, as they have no common factor except for 1. Similarly, 15 and 16 are coprime.

Coprime Numbers Between 1 and 100

Back to Top
All the coprime numbers between 1 and 100 cannot be listed, since there are infinite number of coprime numbers. There are few properties based on which coprime numbers become easier to be classified.
The points to remember and the coprime numbers based on those points are listed below :

1) One is always coprime with any other number. (1, 2), (1, 3), (1, 4), (1, 5), ... , (2, 99), (1, 100).
2) Every odd number is coprime with 2. Such as (2 , 3), (2 , 5), (2 , 7), (2 , 9), ..., (2, 97), (2, 99).
3) Two consecutive numbers will also be coprime. i.e. (3, 4), (4, 5), (5, 6), (6, 7), ..., (98, 99), (99, 100).
4) Two prime numbers are always co-prime, i.e. (3, 5), (7, 9), (9, 11), (11, 13), ..., (89, 91), (91, 97).
5) A prime number will always be coprime with other numbers except for its multiples. (3, 5), (3, 7), (3, 11), ..., (3, 97) and (5, 7), (5, 9), (5, 11), (5, 13), ... ,(5, 97) etc.
There are several more coprime numbers between 1 and 100, each of which cannot be mentioned here.

Factorization

Back to Top
Every number can be written the form of prime factors. The process of representing a number in its prime factors is known as factorization. The coprime numbers can also be factorized and represented in the form -
$x^{a}\ y^{b}\ ...$
Here, x are y are prime numbers.
When we factorize two coprime numbers, we get no factors in common.
For example -
Two coprime numbers 18 and 49 can be factorized in the following way -
18 = 2 x 3 x 3 = 2 x 3$^{2}$
49 = 7 x 7 = 7$^{2}$

How to Find

Back to Top
In order to find whether two numbers are coprime, one needs to follow the steps illustrated below:
Step 1 : Using prime factorization technique, find the prime factors of each of the two coprime numbers. Lets say x and y be two numbers then
x = a x b x c ...
y = p x q x r ...

Step 2 (Optional) : Write the prime factors in exponential form.

Step 3 : Compare the two set of prime factors. If both the sets do not contain any common prime factor except for 1, then the numbers are coprime otherwise not. i.e.
x = a x b x c ...
y = p x q x r ...
If any one of a, b, c is equal to any of the p, q, r, then x and y are not coprime and if not, x and y are coprime.

There is one more method of finding whether two numbers are coprime. It is given below:
Step 1 : Find the greatest common factor of both the numbers.

Step 2 : If GCF is equal to 1, then the numbers are coprime; otherwise they are not coprime.

Examples

Back to Top
Few examples based on coprime numbers are as follows:
Example 1 : Find if 45 and 44 are coprime ?

Solution : The prime factors of both numbers are -
45 = 5 x 3 x 3 = 5 x 3$^{2}$
44 = 2 x 2 x 11 = 2$^{2}$ x 11
We find no common factors other than 1 among the prime factors of 45 and 44. Therefore, both numbers are mutually prime or coprime.

Example 2 : Find whether 2662 and 1000 are coprime ?

Solution : The prime factorization of 2662 and 1000 -
2662 = 2 x 11 x 11 x 11 = 2 x 11$^{3}$
1000 = 2 x 2 x 2 x 5 x 5 x 5 = 2$^{3}$ x 5$^{3}$
We find a common factor 2. Therefore, the numbers 2662 and 1000 are not coprime.

Example 3 : Check if the numbers 64 and 9 are coprime or not ?

Solution : The prime factorizations of 64 and 91 are given below -
64 = 2 x 2 x 2 x 2 x 2 x 2 = 2$^{6}$
93 = 3 x 31
There is no common factor. So, the numbers 64 and 91 are coprime.

Example 4 : List the number from 1 to 30 that are coprime to 3.
Solution : The numbers (from 1 to 30) that have no common factor with 3 would be coprime with 3. Remember that a number is coprime with all the numbers that are not multiple of that number. The pairs of coprime numbers with 3 are listed below :

(3 , 1), (3 , 2), (3 , 4), (3 , 5), (3 , 7), (3 , 8), (3 , 10), (3 , 11), (3 , 13), (3 , 14), (3 , 16), (3 , 17), (3 , 19), (3 , 20), (3 , 22), (3 , 23), (3 , 25), (3 , 26), (3 , 28), (3 , 29).