Choosing Numbers with No Common Factors
Date: 03/31/98 at 02:13:09 From: Hui Shen Subject: Probability A friend of mine asked me this question, and I have no idea what to do. Can you help? What is the probability of choosing 2 numbers that have no common factors?
Date: 03/31/98 at 11:48:51 From: Doctor Rob Subject: Re: Probability This is a classic problem. The short answer is 6/Pi^2, or about 0.607927. Here is a way of seeing this. Let P equal the probability of being relatively prime. Then it is clear that P = A(2) * A(3) * A(5) * A(7) * A(11) * ..., where A(p) is the probability that two randomly chosen numbers will *not* both be divisible by p. Clearly A(p) = 1 - 1/p^2. The above equation says that two integers are relatively prime if and only if they have no prime number as a common divisor. Thus P = Product (1-1/p^2) over all prime numbers p. The trick here is to consider 1/P: 1/P = Product 1/(1-1/p^2), and expand the fraction inside the product as a geometric series: 1/P = Product (1 + 1/p^2 + 1/p^4 + 1/p^6 + ...), over all primes p, = Product Sum 1/p^(2*i), over all i >= 0 and all primes p. Now if we exchange the product and sum, we find 1/P = Sum Product 1/p^(2*i), = Sum 1/(Product p^i)^2 = Sum 1/n^2, over all n >= 1 This is because for each integer n, we can give its prime power factorization as n = Product p^i for some set of i's. Then for the prime p, choose the term with i = e(p). Thus P = 1/[Sum 1/n^2] Now all I have to do is convince you that Sum 1/n^2 = Pi^2/6. Here is a slick proof of that fact due to Calabi, using calculus. Consider I = (4/3)*Integral Integral 1/(1-x^2*y^2)dx dy, 0 <= x <= 1, 0 <= y <= 1 On the one hand, it turns out that I = Sum 1/n^2, which we prove as follows. Expanding 1/(1-x^2*y^2) as a geometric series, we get I = (4/3)*Integral Integral Sum (x^2*y^2)^i dx dy = (4/3)*Integral Integral Sum x^(2*i)*y^(2*i) dx dy = (4/3)*Integral Sum [Integral x^(2*i) dx]*y^(2*i) dy = (4/3)*Integral Sum y^(2*i)/(2*i+1) dy = (4/3)*Sum Integral y^(2*i)/(2*i+1) dy = (4/3)*Sum 1/(2*i+1)^2, where the sum is over all i >= 0, and the integrals are from 0 to 1. Now Sum 1/n^2 = Sum 1/(2*i+1)^2 + Sum 1/(2*i)^2 = Sum 1/(2*i+1)^2 + (1/4)*Sum 1/i^2 = Sum 1/(2*i+1)^2 + (1/4)*Sum 1/n^2 So (3/4)*Sum 1/n^2 = Sum 1/(2*i+1)^2 Thus I = (4/3)*(3/4)*Sum 1/n^2, = Sum 1/n^2. On the other hand, it turns out that I = Pi^2/6, which we prove in this way. Make the substitution x = sin(u)/cos(v) and y = sin(v)/cos(u), so x^2*y^2 = tan^2(u)*tan^2(v), and dx dy = J du dv, where | cos(u)/cos(v) sin(u)*sin(v)/cos^2(v) | J = | |, | sin(u)*sin(v)/cos^2(u) cos(v)/cos(u) | = 1 - tan^2(u)*tan^2(v) Thus I = (4/3)*Integral Integral 1/(1-tan^2(u)*tan^2(v))* (1-tan^2(u)*tan^2(v)) du dv, = (4/3)*Integral Integral 1 du dv, over the region u >= 0, v >= 0, u + v <= Pi/2. Then the double integral is just the area of that region, which is a triangle of height and base Pi/2, whose area is Pi^2/8. Thus I = (4/3)*Pi^2/8, = Pi^2/6. Thus Sum 1/n^2 = Pi^2/6, P = 6/Pi^2. Another proof uses this Fourier series, x^2/2 = Pi*x - Pi^2/3 + 2*Sum cos(n*x)/n^2, over n >= 1, which is valid for 0 <= x <= 2*Pi. Set x = 0 and rearrange this equation to get Sum 1/n^2 = Pi^2/6. -Doctor Rob, The Math Forum Check out our web site http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum