# Coprime integers

Enter positive integers separated by spaces. Example: 125 35 15 45

## Coprime numbers definition

Two integers are coprime if their GCD (Greatest Common Divisor) is 1.

Equivalent definition: 2 numbers are coprime if they have no common prime divisor.

Coprime numbers are also said relatively prime or mutually prime.

Example: 15 and 63 are coprime since,

15 = 3 x 5, the prime factors are 3 and 5

63 = 7 x 9, the prime factors are 7 and 9

To factor a number, you can use this calculator Factoring a number.

15 and 63 do not have a common prime factor so they are coprime numbers.

In contrast, 15 and 50 are not coprime numbers because they have a common prime factor which is 5!

## Generalization to a list of multiple integers

The above definition, can be generalized to 3, 4, 5... N integers. So, integers are said to be coprime if their GCD is equal to 1. Equivalently, they have no common prime factor.

For example, 6, 35 and 20 are coprime numbers because,

6 = 3 x 2, the factors are 2 and 3

35 = 5 x 7, factors are 5 and 7

20 = 5 x 2 x 2, the factors are 2 and 5

These 3 integers have no common factor so they are coprime numbers.

Note that 2 is a common factor between 6 and 20 but it is not a factor of 35. So, 2 is not a factor common to the 3 integers.

But 6, 20 and 100 are not coprime because they have a common prime factor which is 2.

## How to check if 2 numbers are coprime numbers ?

There are several methods to find out whether two or more integers are coprime numbers.

**GCD Method**

In method, you proceed by calculating the GCD of the integers. If it is equal to 1 then the numbers are coprime numberw.

Example 1

GCD (16,56,85) = 1, so integers 16, 56 and 85 are coprime numbers.

Example 2

GCD (22,143,55) = 8, so integers 22, 143 and 55 are not coprime numbers.

**Factoring method**

In this method, we factorize the integers and statue they are coprime if they have no common prime factor.

Let's reconsider the same examples as above.

Example 1

16 = 2 x 2 x 2 x 2

56 = 2 x 2 x 2 x 7

85 = 5 x 17

We notice that there is no common prime factor between the 3 numbers, therefore 16, 56 and 85 are coprime numbers.

Example 2

22 = 11 x 2

143 = 11 x 13

55 = 11 x 5

We notice that 11 is a common prime factor between the 3 numbers, so 22, 143 and 55 are not coprime numbers.

## Extended Euclid algorithm or Bezout Theorem

Using, the Bezout theorem (or Extended Euclidean algorithm), we can state another definition of two coprime numbers.

Two numbers a and b are coprime numbers if and only if there exist two relative integers u and v such as,

`a*u + b*v = 1`

This definition is important because widely used in number theory.

## Programming

### Python

This python program checks whether two integers a and b are coprime numbers. The 'coprime' function returns a boolean variable: True (if a and b are coprime) or False otherwise.

- We use the function gcd in python and the used coprime denition is : two numbers are coprime numbers if and only if their GCD (Greatest Common Divisor) is equal to 1.

- The operator % refers to the remainder of the Euclidean division.

```
def coprime(a, b):
if (gcd (a, b) == 1):
return True
return False
def gcd (a, b):
while b:
a, b = b, a % b
return a
```

## See also

Factoring a number

GCD

Find a number divisors

Bezout theorem (or Extended Euclidean algorithm)