An interesting (and famous) probability

Let P N {P}_{N} be the probability that two randomly selected integers on the interval [ 1 , N ] \left[ 1,N \right] are coprime. Evaluate lim N P N \lim_{N \to \infty}{P}_{N}

Notes:

Two integers a a and b b are coprime if and only if g c d ( a , b ) = 1 gcd\left( a,b \right) =1

Round your answer to 3 3 decimal places, and express as a decimal instead of a percent (Not 92.4 92.4 %, instead enter 0.924 0.924 ).


The answer is 0.608.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Austin Antonacci
Oct 29, 2015

A randomly chosen natural nonzero number n n evenly divides every n n th integer. The probability, then, that a natural nonzero number divides a random integer is 1 n \frac {1}{n} .

Every integer can be written as a product of prime numbers, so two coprime integers can be considered as numbers which share no prime numbers in their factorization.

Now we combine these two realizations together!

The probability of two integers being divisible by the same integer a a is simply 1 a 2 \frac {1}{a^2} . So the sum of this probability for each prime number will give us our desired result, the probability that two random positive integers are coprime.

This can be written as n = 1 ( 1 1 P n ) \prod _{ n=1 }^{ \infty }{ \left( 1-\frac { 1 }{ { P }_{ n } } \right) } where P n {P}_{n} is the n n th prime starting at 2 2 . This is rewritten as n = 1 ( P n 1 P n ) \prod _{ n=1 }^{ \infty }{ \left( \frac { { P }_{ n }-1 }{ { P }_{ n } } \right) } which is the inverse of one of our given products.

It follows that the probability (chaining into the given sum of 1 n 2 \frac {1}{n^2} ) is 6 π 2 \frac{6}{\pi^2} , which, when rounded to 3 decimal places, is 0.608 \boxed{0.608}

Bonus: What is the probability that four randomly chosen positive integers are coprime?

Pi Han Goh - 5 years, 7 months ago

Log in to reply

That's probably 90 π 4 \frac{90}{\pi^4} , I would think, or about 0.924 \boxed{0.924} . It's very interesting how this all works out!

Austin Antonacci - 5 years, 7 months ago

Log in to reply

Pi Han Goh - 5 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...