Kodeclik Blog
What are coprime numbers?
Coprime numbers are pairs of integers that share no common factors except for 1. This means their greatest common divisor (GCD) or highest common factor (HCF) equals 1. Coprimes are basically a generalization of the idea of primes.
Recall that a prime number is one that has only two factors, namely 1 and itself. 5 is a prime number because it has only two factors: 1 and 5. 48 is not a prime number because it has other factors besides 1 and 48. For instance, 2, 3, etc are factors of 48.
Being coprime is a property of two numbers, not one number. We find if two numbers are coprime by first enumerating their factors and seeing if they have any common factors. Here are some examples!
2 and 3 are coprime
The factors of 2 are 1 and 2. The factors of 3 are 1 and 3. Note that the only common factor is 1. Thus 2 and 3 are coprime.
4 and 9 are coprime
The factors of 4 are 1, 2, and 4. The factors of 9 are 1, 3, and 9. The only common factor is 1. So 4 and 9 are coprime.
13 and 15 are coprime
You can verify that although 13 is prime and 15 is composite the only common factor they share is 1 and thus they are coprime.
18 and 24 are not coprime
If we do the prime factorization of 18, we get 18=2*3*3. Similarly, 24 = 2*2*3. You can see that they have two common factors besides 1, namely 2 and 3. Thus 18 and 24 are not coprime. (Of course you can conclude that two even numbers can never be coprime because they will both have a factor of 2.)
Either or both numbers in a coprime pair can be prime
From the above three examples, it should be clear that both can be prime (e.g., 2 and 3), both can be composite (4 and 9), or they can be a prime-composite pair (such as 13 and 15).
Coprime numbers are also called as relatively prime or mutually prime numbers.
Two consecutive numbers are always coprime
Two consecutive numbers are always coprime due to a fundamental mathematical property that can be proven through a simple yet elegant argument.
When two numbers are consecutive, like n and n+1, they cannot share any common factors except 1. This happens because:
Another way to convince yourself of this fact is:
In summary, the greatest common divisor (GCD) of any two consecutive integers is always 1. This fundamental property of consecutive numbers plays a crucial role in various mathematical proofs and number theory applications.
Using Euclid’s algorithm to prove that consecutive numbers are coprime
Remember that Euclid’s algorithm is a step by step process to find the GCD of two numbers. Given two numbers x and y, we keep repeatedly dividing the larger number by the smaller one and then using the remainder for the next division, until the remainder becomes zero. The last non-zero remainder is the GCD.
For instance, let us try to find the GCD of 48 and 18:
Because we get a remainder of 0, the GCD (12,6) is 6 and thus the GCD of (48,18) is 6.
For any consecutive numbers n and n+1, applying the Euclidean Algorithm to find GCD(n,n+1):
The algorithm terminates immediately with remainder 0, so the GCD is the smaller number, i.e., 1. Because the GCD of n and n+1 is 1, they are relatively prime!
Python program to check if two numbers are coprime
Here is a simple Python program to implement the above ideas and then sweep through a range of numbers to find coprime pairs:
def are_coprime(a, b):
def gcd(x, y):
while y != 0:
x, y = y, x % y
return x
return gcd(a, b) == 1
coprime_pairs = []
for i in range(1, 11):
for j in range(i + 1, 11):
if are_coprime(i, j):
print(f"({i},{j})")The code defines a function called are_coprime that determines whether two numbers share any common factors other than 1. This function uses a nested helper function gcd that implements Euclid's algorithm to find the greatest common divisor of two numbers. When the GCD equals 1, the numbers are coprime. The gcd function works by repeatedly taking the remainder of division between two numbers until reaching zero, with the last non-zero remainder being the GCD.
The main part of the code uses nested loops to systematically check all possible pairs of numbers from 1 to 10, where the second number is always larger than the first to avoid duplicate pairs. For each pair of numbers, it calls the are_coprime function, and if the numbers are determined to be coprime, it immediately prints the pair using an f-string format.
The one-pair-per-line output clearly shows all coprime relationships between numbers from 1 to 10:
(1,2)
(1,3)
(1,4)
(1,5)
(1,6)
(1,7)
(1,8)
(1,9)
(1,10)
(2,3)
(2,5)
(2,7)
(2,9)
(3,4)
(3,5)
(3,7)
(3,8)
(3,10)
(4,5)
(4,7)
(4,9)
(5,6)
(5,7)
(5,8)
(5,9)
(6,7)
(7,8)
(7,9)
(7,10)
(8,9)
(9,10)As you can see some pairs are both composite numbers (like 9, 10), some are both prime (like 5, 7) and some are mixed (like 6, 7).
Python program to find coprime triplets
Here's the above code updated to check for coprime triplets:
def are_coprime_three(a, b, c):
def gcd(x, y):
while y != 0:
x, y = y, x % y
return x
# Check if the GCD of all three pairs is 1
return gcd(a, gcd(b, c)) == 1
for i in range(1, 11):
for j in range(i + 1, 11):
for k in range(j + 1, 11):
if are_coprime_three(i, j, k):
print(f"({i},{j},{k})")This code extends our previous coprime checker to work with three numbers. The are_coprime_three function uses nested GCD calculations to verify that all three numbers share no common factors. It first finds the GCD of b and c, then finds the GCD of that result with a. The numbers are coprime if the final GCD equals 1. The main loop structure now uses three nested loops to generate all possible triplets of numbers from 1 to 10, where each number is larger than the previous one to avoid duplicates. When run, this code will print all triplets of numbers between 1 and 10 that are mutually coprime, such as (1,2,3), (2,3,5), and (3,4,5).
The output will be (wow - scroll all the way to see continued discussion):
(1,2,3)
(1,2,4)
(1,2,5)
(1,2,6)
(1,2,7)
(1,2,8)
(1,2,9)
(1,2,10)
(1,3,4)
(1,3,5)
(1,3,6)
(1,3,7)
(1,3,8)
(1,3,9)
(1,3,10)
(1,4,5)
(1,4,6)
(1,4,7)
(1,4,8)
(1,4,9)
(1,4,10)
(1,5,6)
(1,5,7)
(1,5,8)
(1,5,9)
(1,5,10)
(1,6,7)
(1,6,8)
(1,6,9)
(1,6,10)
(1,7,8)
(1,7,9)
(1,7,10)
(1,8,9)
(1,8,10)
(1,9,10)
(2,3,4)
(2,3,5)
(2,3,6)
(2,3,7)
(2,3,8)
(2,3,9)
(2,3,10)
(2,4,5)
(2,4,7)
(2,4,9)
(2,5,6)
(2,5,7)
(2,5,8)
(2,5,9)
(2,5,10)
(2,6,7)
(2,6,9)
(2,7,8)
(2,7,9)
(2,7,10)
(2,8,9)
(2,9,10)
(3,4,5)
(3,4,6)
(3,4,7)
(3,4,8)
(3,4,9)
(3,4,10)
(3,5,6)
(3,5,7)
(3,5,8)
(3,5,9)
(3,5,10)
(3,6,7)
(3,6,8)
(3,6,10)
(3,7,8)
(3,7,9)
(3,7,10)
(3,8,9)
(3,8,10)
(3,9,10)
(4,5,6)
(4,5,7)
(4,5,8)
(4,5,9)
(4,5,10)
(4,6,7)
(4,6,9)
(4,7,8)
(4,7,9)
(4,7,10)
(4,8,9)
(4,9,10)
(5,6,7)
(5,6,8)
(5,6,9)
(5,6,10)
(5,7,8)
(5,7,9)
(5,7,10)
(5,8,9)
(5,8,10)
(5,9,10)
(6,7,8)
(6,7,9)
(6,7,10)
(6,8,9)
(6,9,10)
(7,8,9)
(7,8,10)
(7,9,10)
(8,9,10)You might be surprised that the number of coprime triplets is quite larger than the number of coprime pairs. Thus coprime numbers are more common than numbers sharing factors.
Why More Coprime Triplets Exist
First recall that numbers can be coprime even if they aren't prime themselves. For example, 8 and 9 are coprime despite both being composite numbers, as they have no common factors.This creates many more possible combinations than just using prime numbers.
Second, a number can be coprime with many other numbers simultaneously because you are looking for a lack of (rather than a presence of) common factors. For instance, 9 is 3^2, 25 is 5^2, and 49 is 7^2. 9 and 25 have no common factors, 25 and 49 have no common factors, and 9 and 49 have no common factors. The reason 9 and 25 have no common factors is different from the reason 25 and 49 have no common factors, for instance. This pattern repeats frequently across different number combinations, leading to more triplets than one might initially expect.
Significance of the number (a-1)(b-1) for two coprime numbers
For any coprime numbers a and b, the value (a-1)(b-1) represents a significant threshold in number theory. Any natural number greater than or equal to (a-1)(b-1) can be expressed as a linear combination of a and b using integer coefficients.
If we take coprime numbers 4 and 5:
This threshold value (a-1)(b-1) comes up prominently in the Frobenius coin problem or coin problem, as it relates to the largest amount that cannot be represented using given coin denominations when those denominations are coprime.
Enjoy this blogpost? Want to learn Python with us? Sign up for 1:1 or small group classes.
