What is the probability that gcd(n,m)=1? 
(from the Prime Pages' list of frequently asked questions)
 Our book "Prime Curios! The Dictionary of Prime Number Trivia" is now available on CreateSpace, Amazon, ....


Home
Search Site

Largest
The 5000
Top 20
Finding
How Many?
Mersenne

Glossary
Prime Curios!
Prime Lists

FAQ
e-mail list
Titans

Submit primes

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/pi2 roughly as follows. 

Suppose you pick two random numbers less than n, then 
  • [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. 
  • ... 
(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): 
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(mu(k)[n/k]2)     (sum over positive integers k
so the desired constant is the limit as n goes to infinity of this sum divided by n2, or 
sum(mu(k)/k2)     (sum 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/pi2. This number is approximately 
60.7927101854026628663276779258365833426152648033479 
percent.  ;-)
The Prime Pages
Another prime page by Chris K. Caldwell <caldwell@utm.edu>