The odds of two integers being relatively prime

In today's blog, I will use the zeta function to answer the question: what are the odds that two integers selected at random are relatively prime.

Lemma 1: The odds that p divides any positive integer selected at random is 1/p

Proof:

(1) Let us assume that we have n integers, that is, the integers 1..n = 1, 2, 3, ..., n. Let x be an integer randomly selected from this list.

(2) If n ≡ 0 (mod p), then it is clear that the odds are 1/p since:

(a) Since p divides n, there exists a value n' such that n = pn'.

(b) So we can divide up n integers in the following way into n' groups of p:

1, ... , p
p+1, ..., 2p
...
n'p-1, ... n'p

(c) We can see that regardless of group n falls in, 1 out of p of those integers in each group are divisible by p.

(3) if n ≡ a (mod p) where a ≠ 0, then we know that p divides n-a so that we have (n-a)=pn'

(4) In this case, we divide up the n integers into n' groups of p just as before but then we are also left with a group of a integers.

1, ..., p
p+1, .. , 2p
...
n'p-1, ..., n'p
n'p+1, ... n'p+a

(5) We can see that there are a total of n' ways to be divisible by p out of a total of n integers. This gives us odds = n'/(n'p+a)

(6) As we increase n toward infinity, we can use L'Hopital's Rule to give us:

lim (n' → ∞) [n'/(n'p + a)]

let f(x) = n'
let g(x) = n'p + a

f'(x) = 1
g'(x) = p

So lim(n' → ∞) [n'/(n'p+a)] = f'(x)/g'(x) = 1/p

QED

Corollary 1.1: The odds that p divides any 2 positive integers selected at random is 1/p²

Proof:

This follows directly from Lemma 1 above. If the odds of p dividing each positive integer is 1/p, the odds of it dividing both are (1/p)(1/p) = 1/p²

QED

Lemma 2: The odds that any 2 positive integers selected at random are relatively prime is 6/π²

Proof:

(1) Let x,y be two positive integers selected at random.

(2) The odds that a prime p divides both is 1/p² [From the Corollary 1.1 above]

(3) The odds that a prime p fails to divide both is (1 - 1/p²)

(4) Since each prime is distinct, the odds that no prime p divides both = ∏ (p = all primes)(1 - 1/p²)

(5) Now, let's consider the reciprocal of each factor (1 - 1/p²):

1/(1 - 1/p²) = 1/([p² - 1]/p²) = p²/(p² - 1)

(6) Now, consider what happens if we multiply to (p² - 1) to the following sequence S:

Let S = 1 + 1/p² + 1/p⁴ + 1/p⁶ + 1/p⁸ + ...

(p² - 1)S = p² + 1 + 1/p⁴ + ... - 1 - 1/p² -1/p⁴ = p²

So that:

S = p²/(p² - 1) = 1 + 1/p² + 1/p⁴ + ...

(7) Putting this together gives us:

∏ (p = all primes)1/(1 - 1/p²)=∏ (p = all primes)(p²/(p² - 1) = ∏ (p = all primes) ∑ (n=1,∞) 1/p^2(n-1) = (1 + 1/2² + 1/2⁴ + ... )(1 + 1/3² + 1/3⁴ + ...)(1 + 1/5² + 1/5⁴ + ...)*... =

= 1*1*1*1*...*1 + 1/2²*1*1*1*...*1 + 1/3²*1*1*1*...*1 + 1/5²*1*1*1*..*1 + .... + 1/2²*1/3²*1*..*1 + ...

We note that it equals all combinations of 1/p².

(8) Applying the Fundamental Theorem of Arithmetic (see here), this gives us:

1*1*1*1*...*1 + 1/2²*1*1*1*...*1 + 1/3²*1*1*1*...*1 + 1/5²*1*1*1*..*1 + .... + 1/2²*1/3²*1*..*1 + ...
=∑ (n=1,∞) 1/n²

(9) So putting it all together gives us:

∏ (p = all primes)1/(1 - 1/p²) = ∑ (n=1, ∞) 1/n²

(10) But, we know that:

∑ (n=1, ∞) 1/n² = π²/6 (see here)

(11) Now, taking the reciprocal of this gives us:

∏ (p = all primes)(1 - 1/p²) = 6/π².

QED

References

• The zeta function, odds that two numbers are coprime, MathReference.Com