Coprime integers

In number theory, mathematicians study how integers relate to one another through division. Two integers, $a$ and $b$, are called coprime, relatively prime, or mutually prime if their only common positive divisor is 1. This relationship means that no prime number can divide both $a$ and $b$. Another way to state this is that their greatest common divisor (GCD) is exactly 1. You can express this mathematically using the notation $\text{gcd}(a, b) = 1$.

An interesting example is the pair 8 and 9. Individually, neither 8 nor 9 is a prime number. However, they are coprime because they share no factors other than 1. In contrast, 6 and 9 are not coprime because both are divisible by 3.

To determine if two numbers are coprime, mathematicians use specific algorithms. The Euclidean algorithm is a fast method for finding the greatest common divisor. There are even faster versions of this process, such as the binary GCD algorithm or Lehmer's GCD algorithm. Beyond just checking pairs, we can count how many integers are coprime to a specific positive integer $n$ within a certain range. This is calculated using Euler's totient function, often written as $\phi(n)$. This function is a vital tool for understanding the density and distribution of coprime numbers in the number system.

We can also apply the concept of coprimality to larger sets of integers. A set of numbers is considered coprime, or setwise coprime, if the greatest common divisor of all elements in the set is 1. For instance, the numbers 6, 10, and 15 are coprime because no single integer greater than 1 divides all three. However, a stronger condition exists called pairwise coprimality. In a pairwise coprime set, every possible pair of different integers in that set must be coprime. The set {4, 5, 6} is setwise coprime, but it is not pairwise coprime because 4 and 6 share a common factor of 2.

There are several mathematical properties that emerge from coprimality. If $a$ and $b$ are coprime, there exist integers $x$ and $y$ such that $ax + by = 1$. This is known as Bézout's identity. Additionally, if $a$ and $b$ are coprime, their least common multiple is simply their product, $ab$. This leads to a useful rule: if $a$ and $b$ are coprime to $n$, then their product $ab$ is also coprime to $n$. This property is a consequence of Euclid's lemma, which states that if a prime divides a product, it must divide at least one of the factors. Furthermore, any powers of these numbers, such as $a^n$ and $b^n$, will remain coprime to one another.

Coprimality can even be visualized geometrically. In a Cartesian coordinate system, the point $(a, b)$ is "visible" from the origin $(0, 0)$ if and only if $a$ and $b$ are coprime. This means there are no other points with integer coordinates lying directly on the line segment connecting the origin to $(a, b)$.

This concept of visibility connects abstract number theory to the physical arrangement of points in space. It provides a concrete way to see how the lack of common factors prevents a line from hitting other grid points.

If you were to choose two integers at random, there is a specific probability that they will be coprime. This probability is approximately 61%, or more precisely, $6/\pi^2$. This value is linked to the Riemann zeta function, specifically $\zeta(2)$, which Leonhard Euler solved in 1735 as the Basel problem. While you cannot truly pick a random integer from an infinite set with equal probability, mathematicians use the idea of natural density to formalize this. Ernesto Cesàro proved in 1881 that as the range of numbers increases, the probability approaches this $6/\pi^2$ limit.

These mathematical principles have important practical applications in engineering and security. In machine design, engineers choose tooth counts for meshing gears that are relatively prime. This ensures even, uniform wear across the gear teeth, which helps the machine last longer. In the history of cryptography, coprimality was essential for rotor machines and Vernam ciphers. Using pairwise coprime lengths for key loops or rotor teeth helped create complex, non-repeating patterns. This demonstrates how the simple absence of shared factors can create much greater complexity in mechanical and digital systems.