Why two random integers are surprisingly likely to share no common factors

Why two random integers are surprisingly likely to share no common factors
Image: Intellect (generated)

In short: Pick two random integers. The odds they share no common divisor other than one are roughly 61 percent. This result, rooted in the distribution of prime numbers, connects the simple concept of coprimality to the famous Basel problem and the geometry of an unobstructed line of sight.

Two integers are considered coprime if their greatest common divisor is one. This means they share no prime factors. While numbers like 8 and 9 are coprime despite neither being prime, 6 and 9 are not, as both are divisible by 3. This relationship is foundational to number theory, appearing in the Chinese remainder theorem and the Euclidean algorithm, which provides a fast method to verify if two numbers are relatively prime.

The probability that two randomly selected integers are coprime is expressed as 6 divided by pi squared, approximately 61 percent. This value emerges from an Euler product over all prime numbers. The calculation relies on the Riemann zeta function at the value of 2, a result famously derived by Leonhard Euler in 1735 to solve the Basel problem. While picking a truly random integer is mathematically impossible, this density can be formalized using natural density limits.

Beyond probability, coprimality has a striking geometric interpretation. If you plot two integers as coordinates on a Cartesian grid, they are coprime if and only if the point is visible from the origin. If a point is blocked by another integer coordinate, the two numbers share a common factor. Furthermore, all coprime pairs can be mapped into two complete ternary trees, providing an exhaustive way to organize these relationships without redundancy.

It is important to distinguish between setwise and pairwise coprimality. A set is setwise coprime if the greatest common divisor of all its elements is one. Pairwise coprimality is a stricter condition, requiring every possible pair within the set to be coprime. While every pairwise coprime set is also setwise coprime, the reverse does not hold; for instance, the set {4, 5, 6} is setwise coprime but fails the pairwise test because 4 and 6 share a factor of 2.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-coprime-integers.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…