If you pick any two integers at random, what is that probability that they will be relatively prime? ("relatively prime" means that the two numbers share no divisors except 1)

Tell how you end up with the answer.

First a caveat: The method by which you randomize the numbers is going to affect the probability. If each of the two random numbers is drawn from a uniform distribution of integers from 1 to 10, then the probability would be 63% as 63 out of the 100 equally possible pairings would be relatively prime. If drawn from a uniform distribution from 1 to 100, the probability would be 60.87% as 6087 of the possible 10000 pairings would be relatively prime. If the two numbers were each the result of a toss of two dice, 784 of the 1296 ways of the dice falling would result in relative primeness, or 60.49...%.

But if we assume that what is meant is to find what the probability approaches if the two numbers are drawn from a uniform distribution from 1 to n, as n increases without limit, then the following logic applies:

The probability that the two numbers would both be even (divisible by 2) is (1/2)^2 so the probability that they are not both divisible by 2 is 1- (1/2)^2. This is independent of the probability that they are divisible by 3. The probability that they are not divisible by 3 is 1 - (1/3)^2. This is repeated for each prime divisor, as the probability of divisibility by different primes is independent, and divisibility by primes is all that counts. So we need (1-(1/2)^2)*(1-(1/3)^2)*(1-(1/5)^2)*(1-(1/7)^2)*(1-(1/11)^2)*....

By the time the 10th prime, 29, is considered, the probability is down to .612344.... By the hundredth prime, 541, it is down to .6080819.... By the thousandth prime, 7919, .607929.... By the 10,000th prime, 104,729, it's .6079275.... By the 100,000th prime, 1,299,709, it's .6079271....

By the millionth prime, 15,485,863, it is still characterized by .6079271..., so I'll leave it at that.

By the way the program for the above:
list
5 T=1
6 P=1
10 for I=1 to 1000000
15 P=nxtprm(P)
20 T=T*(1-1/(P*P))
30 if I/10000=int(I/10000) or I<11 then print I,P,T
40 next
OK

Posted by Charlie on 2003-07-10 08:24:24