Monday Math 149

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 \frac1p (since every pth integer is a multiple of p); thus, the probability of two independent random integers are both divisible by p is \frac1{p^2}. Thus, the probability that they do not have p as a common factor is 1-\frac1{p^2}.
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,
\prod\limits_{p\;\text{prime}}\left(1-p^{-2}\right)=\left(1-2^{-2}\right)\left(1-3^{-2}\right)\left(1-5^{-2}\right)\cdots
Now, recalling from here that \zeta(s)=\prod\limits_{p\;\text{prime}}\frac1{1-p^{-s}}, thus the probability is
\prod\limits_{p\;\text{prime}}\left(1-p^{-2}\right)=\frac1{\zeta(2)},
and since we found here that \zeta(2)=\frac{\pi^2}{6} , we see that the probability that two random integers are mutually prime is \frac{6}{\pi^2}, which is approximately 60.8%.
Similarly, the probability of four integers being all divisible by a prime p is \frac1{p^4}, so the probability that they do not all have p as a common factor is 1-\frac1{p^4} . Analogous to the above, the probability that the greatest common factor of all four integers is one is
\prod\limits_{p\;\text{prime}}\left(1-p^{-4}\right)=\frac1{\zeta(4)},
and since \zeta(4)=\frac{\pi^4}{90} (see here); we see that the probability for four integers is \frac{90}{\pi^4}, 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 \frac1{\zeta(n)}, which increases toward unity as n gets larger
(since \zeta(s)=\sum\limits_{n=1}^{\infty}\frac1{n^s} decreases asymptotically toward 1 for increasing real s>1).

Advertisements

Tags: , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: