What is the probability that two integers, chosen at random, are coprime or relatively prime. In other words, they don't have any factors in common. Let's designate the random integers as \(m\) and \(n\). Let's consider a random prime \(p\). The probability that \(p\) divides \(m\) is \(1/p\) and the probability that \(p\) divides \(n\) is also \(1/p\). Therefore the probability that \(p\) will NOT divide \(m\) or \(n\) is \(1-1/p^2\). We have only considered one prime however, and need to take them all into account. So the probability that \(m\) and \(n\) have no prime factors in common is given by the following formula where \(p_i\) represents the \(p\)-th prime:$$\prod_{i=2}^{\infty} \Big (1-\frac{1}{p_i^2} \Big )= \Big (1-\frac{1}{2^2} \Big ) \Big (1-\frac{1}{3^2} \Big ) \Big ( 1-\frac{1}{5^2} \Big )\dots $$We can evaluate this using the sum of the reciprocals of all the integers squared:$$\sum_{n=1}^{\infty} \frac{1}{n^2} = 1 +\frac{1}{2^2}+\frac{1}{3^2} +\frac{1}{4^2} + \dots$$where \(n\) represents the \(n\)-th integer and where we have:$$\sum_{n=1}^{\infty} \frac{1}{n^2} \times \prod_{i=2}^{\infty} \frac{1}{p_i^2} =1$$The derivation of the above relationship is explained well in this video. However, we know that:$$\sum_{n=1}^{\infty} \frac{1}{n^2} =\zeta(2)=\frac{\pi^2}{6}$$and so$$ \begin{align} \prod_{i=2}^{\infty} \Big (1- \frac{1}{p_i^2} \Big ) &= \frac{6}{\pi^2}\\ &\approx 0.6079271 \dots \end{align}$$Thus the probability that two positive integers chosen at random are coprime is about 61%. It's easy to simulate this on a computer to test out its validity (permalink). See Figure 1.
 |
Figure 1 |
No comments:
Post a Comment