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/p2. 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 pi represents the p-th prime:∞∏i=2(1−1p2i)=(1−122)(1−132)(1−152)…
![]() |
Figure 1 |
No comments:
Post a Comment