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

^{2}

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

^{2}

QED

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

^{2}

Proof:

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

(2) The odds that a prime p divides both is 1/p

^{2}[From the Corollary 1.1 above]

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

^{2})

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

^{2})

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

^{2}):

1/(1 - 1/p

^{2}) = 1/([p

^{2}- 1]/p

^{2}) = p

^{2}/(p

^{2}- 1)

(6) Now, consider what happens if we multiply to (p

^{2}- 1) to the following sequence S:

Let S = 1 + 1/p

^{2}+ 1/p

^{4}+ 1/p

^{6}+ 1/p

^{8}+ ...

(p

^{2}- 1)S = p

^{2}+ 1 + 1/p

^{4}+ ... - 1 - 1/p

^{2}-1/p

^{4}= p

^{2}

So that:

S = p

^{2}/(p

^{2}- 1) = 1 + 1/p

^{2}+ 1/p

^{4}+ ...

(7) Putting this together gives us:

∏ (p = all primes)1/(1 - 1/p

^{2})=∏ (p = all primes)(p

^{2}/(p

^{2}- 1) = ∏ (p = all primes) ∑ (n=1,∞) 1/p

^{2(n-1)}= (1 + 1/2

^{2}+ 1/2

^{4}+ ... )(1 + 1/3

^{2}+ 1/3

^{4}+ ...)(1 + 1/5

^{2}+ 1/5

^{4}+ ...)*... =

= 1*1*1*1*...*1 + 1/2

^{2}*1*1*1*...*1 + 1/3

^{2}*1*1*1*...*1 + 1/5

^{2}*1*1*1*..*1 + .... + 1/2

^{2}*1/3

^{2}*1*..*1 + ...

We note that it equals all combinations of 1/p

^{2}.

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

1*1*1*1*...*1 + 1/2

^{2}*1*1*1*...*1 + 1/3

^{2}*1*1*1*...*1 + 1/5

^{2}*1*1*1*..*1 + .... + 1/2

^{2}*1/3

^{2}*1*..*1 + ...

=∑ (n=1,∞) 1/n

^{2}

(9) So putting it all together gives us:

∏ (p = all primes)1/(1 - 1/p

^{2}) = ∑ (n=1, ∞) 1/n

^{2}

(10) But, we know that:

∑ (n=1, ∞) 1/n

^{2}= π

^{2}/6 (see here)

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

∏ (p = all primes)(1 - 1/p

^{2}) = 6/π

^{2}.

QED

References