Probability of Random Numbers Being CoprimeDate: 08/12/97 at 12:10:22 From: Jonah Knobler Subject: Probability of random numbers being coprime I have heard from numerous sources that the probability of two randomly selected integers being coprime is 6/(pi^2). I have seen fragments of proofs to this effect but nothing conclusive as of yet. I have had no calculus but have a basic understanding of Taylor series, etc. How do you show this is true? What an incredible number to pop up out of nowhere! Would this have anything to do with the fact that sigma x = 1 to infinity (x^2) is (pi^2)/6? Could you explain how to show this latter fact as well, and any relation between these two seemingly random quantities? Thanks! - Jonah Knobler Date: 08/15/97 at 16:56:24 From: Doctor Rob Subject: Re: Probability of random numbers being coprime Indeed, you have made the correct connection here. The idea is to separate the pairs of numbers according to their GCD's. Start with a finite part of the plane, and then take the limit as its dimensions approach infinity. Consider the set of pairs (a,b) with 1 <= a <= N, and 1 <= b <= N. There are N^2 altogether. Of these, [N/p]^2 share the prime divisor p, where [.] is the greatest integer function. Then the numbers which are relatively prime are N^2 - SUM [N/p]^2 + SUM SUM [N/(p*q)]^2 - ... The fractions which are relatively prime are, then, using inclusion- exclusion, f(N) = 1 - SUM ([N/p]/N)^2 + SUM SUM ([N/(p*q)]/N)^2 - ... Now let f = lim f(N) as N -> infinity. It is clear that [N/a]/N -> 1/a, so f = 1 - SUM 1/p^2 + SUM SUM 1/(p^2*q^2) - ... = PROD (1 - 1/p^2) = PROD {1/(1 + 1/p^2 + 1/p^4 + 1/p^6 + ...)} = 1/PROD (1 + 1/p^2 + 1/p^4 + 1/p^6 + ...) = 1/(SUM 1/n^2) = 1/(Pi^2/6) = 6/Pi^2 The proof that SUM 1/n^2 = Pi^2/6 is perhaps most easily seen using the following double integral: I = INT INT dy dx/(1 - x^2*y^2), where the integrals both go from 0 to 1. It turns out that the value of I is 3/4 of the sum you are looking for. A clever change of variables makes it clear that this double integral is just Pi^2/8. Another proof of the formula is available using Fourier series, that is, series of the form f(x) = a(0) + SUM a(n) cos(nx) + b(n) sin(nx), where the sum runs over all n > 0. If you choose the correct function, and find the coefficients a(n) and b(n) that make this work, then when the function is evaluated at x = 0, you get f(0) = a(0) + SUM a(n), which gives you the value you want. I don't remember the function, but it is moot, since the determination of the coefficients a(n) and b(n) requires calculus. If you are willing to accept the coefficients of a particular Fourier Series, then here is a solution. I take from Robert K. Ritt, _Fourier Series_, McGraw-Hill (1970), pp. 16-17: f(t) = t*(2*Pi - t)/Pi^2 = 2/3 - (4/Pi^2)*SUM cos(n*t)/n^2, 0 <= t <= 2*Pi, and f(t) = f(t - 2*Pi*k) outside that range, where the sum runs from n=1 to infinity, and k is any integer. I actually checked that this is correct. Using this, substitute t = 0, and you get 0 = 2/3 - (4/Pi^2)*SUM 1/n^2 SUM 1/n^2 = Pi^2/6. Q.E.D. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/