What is the probability that two independently randomly chosen integers are mutually prime (have no common factor greater than 1)? The probability for four random integers? For n integers in general?
The probability that a random integer is divisible by a given prime p is 
(since every pth integer is a multiple of p); thus, the problem of two independent random integers are both divisible by p is 
. Thus, the probability that they do not have p as a common factor is 
.
Thus, for the two random integers to be mutually prime, they must have no primes as a common factor; thus, the probability is the product of the above for all primes,
=\left(1-2^{-2}\right)\left(1-3^{-2}\right)\left(1-5^{-2}\right)\cdots)
Now, recalling from here that =\prod_{p\;\text{prime}}\frac1{1-p^{-s}})
, thus the probability is
=\frac1{\zeta(2)})
,
and since we found here that =\frac{\pi^2}{6})
, we see that the probability that two random integers are mutually prime is 
, which is approximately 60.8%.
Similarly, the probability of four integers being all divisible by a prime p is 
, so the probability that they do not all have p as a common factor is 
. Analogous to the above, the probability that the greatest common factor of all four integers is one is
=\frac1{\zeta(4)})
,
and since =\frac{\pi^4}{90})
(see here); we see that the probability for four integers is 
, which is approximately 92.4%.
Generalizing, we see that for n≥2 independent random integers, the probability that the greatest common factor of all n integers is 1 is given by })
, which increases toward unity as n gets larger
(since =\sum_{n=1}^{\infty}\frac1{n^s})
decreases asymptotically toward 1 for increasing real s>1).
Advertisement
Like this:
Be the first to like this post.
Tags: Infinite Product, Math, Monday Math, Prime Factors, Probability, Riemann Zeta Function
This entry was posted on January 3, 2011 at 4:06 am and is filed under Math/Science. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
