Let and be two randomly chosen positive integers.
What is the probability , that is, the probability that and are coprime, and thus have no common divisors greater than one?
Give your answer as .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
M and N are coprime iff they have no common prime factors.
Thus M and N are not both divisible by 2; not both divisible by 3; not both divisible by 5; and so on. This gives p = ( 1 − 2 2 1 ) ⋅ ( 1 − 3 2 1 ) ⋅ ( 1 − 5 2 1 ) ⋯ ( 1 − p 2 1 ) ⋯
If we expand this fraction, we get p = 1 − 2 2 1 − 3 2 1 − 5 2 1 + 6 2 1 − 7 2 1 + 1 0 2 1 − 1 1 2 1 − 1 3 2 1 + 1 4 2 1 + 1 5 2 1 + − ⋯ = n = 1 ∑ ∞ n 2 μ ( n ) , where μ ( n ) is the Moebius function, which is 0 for any number divisible by a square, and ( − 1 ) r for any number containing r distinct prime factors.
To evaluate p , let's try to find its multiplicative inverse. We will add multiples of p to cancel the terms one by one, leaving only 1, as follows: p = p / 2 2 = p / 3 2 = p / 4 2 = p / 5 2 = p / 6 2 = p / 7 2 = p / 8 2 = p / 9 2 = p / 1 0 2 = ⋮ = sum = 1 ⋮ 1 − 1 / 2 2 + 1 / 2 2 − 1 / 3 2 + 1 / 3 2 − 1 / 4 2 + 1 / 4 2 − 1 / 5 2 + 1 / 5 2 + 1 / 6 2 − 1 / 6 2 − 1 / 6 2 + 1 / 6 2 − 1 / 7 2 + 1 / 7 2 − 1 / 8 2 + 1 / 8 2 − 1 / 9 2 + 1 / 9 2 + 1 / 1 0 2 − 1 / 1 0 2 − 1 / 1 0 2 + 1 / 1 0 2 ⋮ + ⋯ + ⋯ + ⋯ + ⋯ + ⋯ + ⋯ + ⋯ + ⋯ + ⋯ + ⋯ + ⋱
I leave it to the reader to convince him/herself that in this way all terms cancel, except the first. Thus we have p ( 1 + 2 2 1 + 3 2 1 + 4 2 1 + ⋯ ) = 1 . The series in brackets is well-known to converge to π 2 / 6 , so that p = ∑ n = 1 ∞ n − 2 1 = π 2 / 6 1 = π 2 6 ≈ 0 . 6 0 7 9 2 7 1 0 2 .
Note : In general, n = 1 ∑ ∞ n s μ ( n ) = ζ ( s ) 1 , with ζ ( n ) = ∑ p prime ( 1 − p − s ) the Riemann zeta function. Here s = 2 and ζ ( s ) = π 2 / 6 .