Saturday, September 02, 2006

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/p2

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/p2

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/p2 [From the Corollary 1.1 above]

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

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

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

1/(1 - 1/p2) = 1/([p2 - 1]/p2) = p2/(p2 - 1)

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

Let S = 1 + 1/p2 + 1/p4 + 1/p6 + 1/p8 + ...

(p2 - 1)S = p2 + 1 + 1/p4 + ... - 1 - 1/p2 -1/p4 = p2

So that:

S = p2/(p2 - 1) = 1 + 1/p2 + 1/p4 + ...

(7) Putting this together gives us:

∏ (p = all primes)1/(1 - 1/p2)=∏ (p = all primes)(p2/(p2 - 1) = ∏ (p = all primes) ∑ (n=1,∞) 1/p2(n-1) = (1 + 1/22 + 1/24 + ... )(1 + 1/32 + 1/34 + ...)(1 + 1/52 + 1/54 + ...)*... =

= 1*1*1*1*...*1 + 1/22*1*1*1*...*1 + 1/32*1*1*1*...*1 + 1/52*1*1*1*..*1 + .... + 1/22*1/32*1*..*1 + ...

We note that it equals all combinations of 1/p2.

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

1*1*1*1*...*1 + 1/22*1*1*1*...*1 + 1/32*1*1*1*...*1 + 1/52*1*1*1*..*1 + .... + 1/22*1/32*1*..*1 + ...
=∑ (n=1,∞) 1/n2

(9) So putting it all together gives us:

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

(10) But, we know that:

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

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

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

QED

References

No comments:

Post a Comment