Coprime Integers

What Are Coprime Numbers?

Two integers $ a $ and $ b $ are coprime (or relatively prime) if their greatest common divisor (GCD) is 1: $$ \gcd(a, b) = 1 $$

In other words, they share no common factors except 1.

By definition, the greatest common divisor (GCD) of coprime numbers is always 1.

Note: Coprime numbers don’t have to be prime numbers. Even non-prime numbers can be coprime. However, any two prime numbers are always coprime. That said, just because one of the numbers is prime doesn’t necessarily mean they are coprime.

To check whether two numbers $ a $ and $ b $ are coprime, try writing the fraction $ \frac{a}{b} $ in its simplest form. If it cannot be reduced, the numbers are coprime.

Example

The numbers 6 and 35 are coprime because they have no common factors:

$$ \gcd(6, 35) = 1 $$

However, 6 and 36 are not coprime because they share a common factor (6):

$$ \gcd(6, 36) = 6 $$

Similarly, 15 and 28 are coprime:

$$ \gcd(15, 28) = 1 $$

Additional Notes

Here are some key properties of coprime numbers:

Bézout’s Identity
If two numbers $ a $ and $ b $ are coprime, then there exist integers $ x $ and $ y $ such that: \[ ax + by = 1 \] This property is particularly useful in cryptography (e.g., the RSA algorithm) and in solving Diophantine equations.
Note: The RSA algorithm relies on coprime numbers for generating public and private keys. Specifically, $ e $ and $ \varphi(n) $ must be coprime for the algorithm to function correctly.
Multiplication and Coprime Numbers
If $ a $ and $ b $ are coprime, then any power of these numbers will also be coprime: \[ \gcd(a^n, b^m) = 1 \] for any $ n, m \geq 1 $.
Euler’s Totient Function
Euler’s totient function $ \varphi(n) $ counts how many integers between $ 1 $ and $ n $ are coprime with $ n $. For example:
\[ \varphi(10) = 4 \] because the numbers coprime to 10 between 1 and 10 are $ 1, 3, 7, 9 $.
Multiplicative Inverse in Modular Arithmetic
If $ a $ and $ m $ are coprime, then $ a $ has a modular multiplicative inverse, meaning there exists a number $ b $ such that: \[ a \cdot b \equiv 1 \pmod{m} \] This is a fundamental concept in modular arithmetic.
Chinese Remainder Theorem
This theorem takes advantage of coprime numbers to solve systems of modular congruences.

Note: The probability that two randomly chosen integers are coprime is approximately $ \frac{6}{\pi^2} \approx 0.607 $, which is surprisingly high.

And so on.