Coprime Numbers

Two integers numbers, a and b, are said to be coprime numbers, if their greatest common divisor is equal to one.

For example, the greatest common divisor of 2 and 4 is 2 \(\neq\) 1. Therefore 2 and 4 are not coprime, while 2 and 9 are coprime because the greatest common divisor of 2 and 9 is 1.

Alternate names for coprime are relatively prime or mutually prime. It should be noted that coprime numbers are not the same as prime numbers. It requires two numbers to be called coprimes but only a single number to be called as prime.

History

The property of being coprime numbers are based on the knowledge of the greatest common divisor. Euclid developed an efficient method to find the greatest common divisor (gcd). This method is called the Euclidean Algorithm. Euclid first explained this algorithm in his book ‘Elements‘ in somewhere around 300 B.C.

An algorithm to find gcd for non-negative integers was developed by Joseph Stein in 1967.  Derrick Henry Lehmer found another fast algorithm around 1930.

Methods to find Coprime Numbers

Two numbers are Coprimes if their greatest common divisor is 1.

\(gcd(a, b) = 1  \mbox{ then $a$ and $b$ coprimes}; a, b \in \mathbb{Z}\).

Another name for GCD is HCF(Highest Common Factor).

There are three powerful algorithms to find gcd of two numbers: Euclidean Algorithm, Stein’s Binary GCD Algorithm, and Lehmer GCD Algorithm. Among these, the simplest one is Euclidean Algorithm.

A straightforward way to find gcd is by comparing the prime factors of the two numbers. Prime factorize the two numbers. Collect common prime factors from both(if the same factor appears two times for each number, then collect the factor two times). Multiply the collected factors to get the GCD. If there are no common prime factors, then GCD = 1.

Example 1. Let the two numbers be 10 and 90. We have,
45 = 3×3×5
90 = 2×3×3×5
Common factors = 3,3 and 5

Therefore, \(gcd (45,90) = 3×3×5 = 45 \neq 1\)
\(\Rightarrow 45 \mbox{ and $90$ are not coprime numbers}.\)

Example 2. Let the two numbers be 66 and 49. We have,
66= 2×3×11
49= 7×7
Here, we have no common factors. 

Therefore, \(gcd(66,49) = 1\)
\(\Rightarrow \mbox{ $66$ and $49$ are coprime numbers}.\)

Euclid’s Algorithm 

Euclid’s Method is used to find GCD for two non-negative integers. It utilizes the property that even after subtracting the given two numbers, gcd remains the same. That is if the numbers are a and b, 

\(gcd (a, b) = gcd(a-b, a) = gcd(a-b, b)\)

We continuously find the difference between the lower number and the resultant number of subtraction until we reach a point where the lower number and the subtracted number become the same. Then that number is the GCD.

Example 1. Let’s find if 66 and 24 are coprime numbers.

 gcd(66,24) = ?
We have, 66 – 24 = 42

gcd(42,24) = ?
Again, 42 – 24 = 18

gcd(24,18) = ?
24 – 18 = 6

gcd(18,6) = ?
18 – 6 = 12

gcd(12,6) = ?
12 – 6 = 6

gcd(6,6) = 6

Hence, gcd(66,24) = 6
Therefore, 66 and 24 are not coprimes.

Example 2. Now let’s find if 66 and 25 are coprime numbers.

gcd(66,25) = ?
66 – 25 = 41

gcd(41,25) = ?
41 – 25 = 16

gcd(25,16) = ?
25 – 16 = 9

gcd(16,9) = ?
16 – 9 = 7

gcd(9,7) = ?
9 – 7 = 2

gcd(7,2) = ?
7 – 2 = 5

gcd(5,2) = ?
5 – 2 = 3

gcd(3,2) = ?
3 – 2 = 1

gcd(2,1) = ?
2 – 1 = 1

gcd(1,1) = 1

Hence, gcd(66,25) = 1
Therefore, 66 and 25 are coprime numbers.

An improved and faster version of Euclid’s Algorithm uses division instead of subtraction.

In this method, we divide the two numbers and leave the quotient. Then we use the remainder as the divisor and the original divisor as the dividend. We perform this repeatedly until we get remainder zero. At this point, the final divisor is the gcd of the actual two numbers.

Example 1. What is gcd of 66 and 24?

We have, 66÷24 has a remainder of 18
Again, 24÷18 has a remainder of 6
18÷6 has remainder 0.

The final divisor is 6. Therefore, gcd(66,24) =6.

Example 2. What is the gcd of 66 and 25?

We have, 66÷25 has a remainder of 16
Again, 25÷16 has a remainder 9
16÷9 has remainder 7
9÷7 has remainder 2
7÷2 has remainder 1 
2÷1 has remainder 0 

Here, the last divisor was 1. Therefore, gcd(66,25) = 1.

Properties of Coprime Numbers

Let a and b coprime numbers.

1. No prime number divides both a and b.
2. Any pair of prime numbers is always coprime.
   Example. 5 and 7 are prime and coprime both.
3. Any two successive integers are coprime because gcd =1 for them.
   Example. 6 and 7 are coprime numbers.
4. a and b are coprime, then ab and a+b are also coprime.
   Example. 6 and 7 are coprime, and 42 and 13 are also coprime.
5. 1 and -1 are coprime with every integer.
6. Bézout’s Identity: If a and b are coprime then \(\exists x, y \in \mathbb{Z} \mbox{ such that } ax +by =1\)

Coprime Numbers Between 0 and 100

1 is coprime with every integer between 0 to 100.

2 is coprime with all the odd numbers.

3 is coprime with all the numbers which are not multiples of 3.

Also, we have any possible pair of prime numbers that is also coprime.
Prime numbers between 1 to 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Therefore, any combination of two numbers from these is a coprime pair.

Also, we know that any consecutive number pair is also coprime.

A complete list of coprime pairs would be a long list. Such a list is provided here (coprime numbers from 1 to 100).

Applications of Coprime Numbers

1. In geometry: For example, a rectangular area with sides as coprime numbers cannot be covered by any 2 by 2 (or any integer \(\neq\) 1) square tile. A unit square tile or tiles could only cover it with non-integer length sides.

2. Using a relatively prime number of teeth in two mechanical gears reduces wear and tear. If one of the gears has multiple numbers of teeth relative to other gear, then, after some cycles, the same teeth rub with each other. This results in non-uniform wear. If the number of teeth is coprime, then the same pair of teeth rub only after several cycles. This results in uniform wear and results in longevity of useful period.

FAQs