The zeta Function, Odds That Two Numbers Are Coprime

Odds That Two Numbers Are Coprime

Here is a beautiful and unexpected application of the zeta function. What are the odds that two numbers, chosen at random, are relatively prime?

Actually we can't choose a number at random from the set of integers, so let's rephrase the question. Find the probability that two numbers, drawn from 1 to n, are relatively prime, and take the limit as n approaches infinity.

Two numbers have a common divisor of p with probability (1/p)2. In other words, each number is divisible by p with probability 1/p. This probability may not be exact, due to the remainder of n mod p, but as n grows large the probability approaches 1/p2. Taking the complement, our two numbers fail to have a common factor p with probability 1-1/p2. By the chinese remainder theorem, all primes can be treated as independent events. Thus the probability of being relatively prime is the product of 1-1/p2, as p runs through all the primes ≤ n. As n increases we keep bringing in more factors of p, and the probability decreases monotonically. We only need find the limit.

Consider the reciprocal of this product. Each factor now looks like p2/(p2-1). Rewrite this as the convergent series:

1 + 1/p2 + 1/p4 + 1/p6 + 1/p8 + …

As a check, multiply this series by p2-1, and get p2/(p2-1) back again.

We must take the product of these infinite series, one series per prime. Expand this into a sum of products, just as (a+b)×(x+y) becomes ax+ay+bx+by. Of course this is a bit more complicated, since we have an infinite product of infinite sums. Still, the distributive law holds, and fortunately, we only need consider finite products in our expansion. Each finite product produces 1/n2 for some integer n. For instance, 1 × 1/4 × 1/9 = 1/36. By the fundamental theorem of arithmetic, each inverse square is produced exactly once. The expanded product is now the sum of 1/n2, or ζ(2). By the previous theorem, ζ(2) = π2/6. Take the reciprocal, and two numbers are coprime with probability 6/π2, roughly 60%.

This generalizes to more than two numbers. Select k numbers at random, and they will have a greatest common divisor of 1 with probability 1/ζ(k). The proof is just like the above, but uses kth powers instead of squares.

Square Free

A random integer n is square free with probability 6/π2, or 60%. The math is virtually the same as the coprime problem. Note that n is divisible by p2 with probability 1/p2, and if n is square free, this test fails for all primes. Manipulate the reciprocal of the product of 1-1/p2, and get ζ(2) as before.

Mathematics of French Toast Recipes and Breakfast Meal Planning:
How to Make French Toast | Breakfast Mathematics | French Toast