Loading web-font TeX/Main/Regular

Thursday, 4 February 2016

Probability that two randomly selected integers are relatively prime

We make use of this result: \bigg(1+\dfrac{1}{2^2}+\dfrac{1}{3^2}+\cdots \bigg)\bigg(1-\dfrac{1}{2^2}\bigg)\bigg(1-\dfrac{1}{3^2}\bigg)\bigg(1-\dfrac{1}{5^2}\bigg)\bigg(1-\dfrac{1}{7^2}\bigg)\cdots \bigg(1-\dfrac{1}{\text{prime squares}}\bigg)=1.
Why is this true? Note that \bigg(1+\dfrac{1}{2^2}+\dfrac{1}{3^2}+\cdots \bigg)\bigg(1-\dfrac{1}{2^2}\bigg)=1+\dfrac{1}{3^2}+\dfrac{1}{5^2}+\cdots
In the equation, all the multiples of \dfrac{1}{2^2} in the first factor have been knocked out by \bigg(1-\dfrac{1}{2^2}\bigg). Similarly, multiplying by \bigg(1-\dfrac{1}{3^2}\bigg) cancels multiples of \dfrac{1}{3^2}. Recall that 1+\dfrac{1}{2^2}+\dfrac{1}{3^2}+\cdots=\dfrac{\pi^2}{6}.
We thus have \bigg(1-\dfrac{1}{2^2}\bigg)\bigg(1-\dfrac{1}{3^2}\bigg)\bigg(1-\dfrac{1}{5^2}\bigg)\bigg(1-\dfrac{1}{7^2}\bigg)\cdots \bigg(1-\dfrac{1}{\text{prime squares}}\bigg)=\dfrac{1}{\dfrac{\pi^2}{6}}=\dfrac{6}{\pi^2}.
We are now ready to proceed with the solution of the original problem. Let m, n be the given random numbers. Let a be any prime. Since a divides 1 only, 1/a  of all the integers are divisible by a. The probability of a dividing m is thus 1/a . Similarly, that of a dividing n is 1/a . We have the followings: P(a|m \wedge a|n) = 1/a \cdot 1/a=1/a^2\\ P(a\not\mid m \wedge a\not\mid n)=1-1/a^2\\ P((m,n)=1)=\bigg(1-\dfrac{1}{2^2}\bigg)\bigg(1-\dfrac{1}{3^2}\bigg)\bigg(1-\dfrac{1}{5^2}\bigg)\bigg(1-\dfrac{1}{7^2}\bigg)\cdots \bigg(1-\dfrac{1}{\text{prime squares}}\bigg)=\dfrac{6}{\pi^2}
[...]

No comments:

Post a Comment