|What is the probability that gcd(n,m)=1?
Here is a frequently asked question:
While playing with programs to determine primes and relative
primes, I stumbled over an interesting (at least to me) fact. While the
probability of a random number being prime decreases as the range of possible
random numbers increases (Prime Number Theorem), the probability of two
random numbers being relatively prime is 60.8% Is this something that
is either well known by or trivially obvious to prime number gurus?
That there should be such a constant is "obvious", finding its value takes
more work. In 1849 Dirichlet showed that the probability is 6/2
roughly as follows.
Suppose you pick two random numbers less than n, then
(Here [x] is the greatest integer less than or equal to x,
usually called the floor function.) So the number of relatively prime
pairs less than or equal to n is (by the inclusion/exclusion principle):
- [n/2]2 pairs are both divisible by 2.
- [n/3]2 pairs are both divisible by 3.
- [n/5]2 pairs are both divisible by 5.
n2 - sum([n/p]2) + sum([n/pq]2)
- sum([n/pqr]2) + ...
where the sums are taken over the primes p,q,r,... less than n.
Letting mu(x) be the möbius function this is
(sum over positive integers k)
so the desired constant is the limit as n goes to infinity of this
sum divided by n2, or
over positive integers k).
But this series times the sum of the reciprocals of the squares is one,
so the sum of this series, the desired limit, is 6/2.
This number is approximately