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 *p*th integer is a multiple of *p*); thus, the probability 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,

Now, recalling from here that , thus the probability is

,

and since we found here that , 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

,

and since (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 decreases asymptotically toward 1 for increasing real *s*>1).

### Like this:

Like Loading...

*Related*

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.

## Leave a Reply