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 and . Let's consider a random prime . The probability that divides is and the probability that divides is also . Therefore the probability that will NOT divide or is . We have only considered one prime however, and need to take them all into account. So the probability that and have no prime factors in common is given by the following formula where represents the -th prime:We can evaluate this using the sum of the reciprocals of all the integers squared:where represents the -th integer and where we have:The derivation of the above relationship is explained well in this video. However, we know that:and soThus 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