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)