Two numbers with no common factor
Two integers are drawn independently and uniformly from . Find the limit, as , of the probability that they have no common factor larger than 1.
You may use .
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
For a prime , the chance that both numbers are divisible by tends to , and these events behave independently for different primes.
Write and relate to .
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. In the limit, the greatest common divisor equals with probability , where is the probability of being coprime: both numbers must be multiples of , and after dividing by they must be coprime. These probabilities add up to 1.
Step 1: scaling. Both numbers are multiples of with probability tending to . Given that, the quotients are (in the limit) again two uniform random integers, coprime with probability . So
Step 2: add up. The events for cover everything, so (Passing to the limit inside the sum is justified because the tail is small uniformly in .)
Step 3.
The product view. Two numbers are coprime when no prime divides both, so by Euler's product formula. The question needs the limit: there is no uniform distribution on all positive integers.