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