Probability the two numbers are relatively prime?!
The question is blatantly easy to phrase, “What’s the probability that two random numbers are co-prime?”
Just to make sure we are all on the same page, co-prime or relatively prime means that the only common divisor that both the numbers have is 1.
Since dealing with infinite sets directly is difficult, we instead choose 2 numbers at random from 1 to n and take the limit as n approaches infinity.
Each number is divisible by p with probability approaching to 1/p as the number grows. Hence two numbers have a common divisor of p with probability (1/p)². This probability might not be exact, due to the remainder of n mod p, but as n grows large the probability approaches that value.
Taking the complement, our two numbers fail to have a common factor p with probability 1–1/p². Thus the probability of being relatively prime is the product of 1–1/p², as p runs through all the primes <=n. With a bit of algebra, you realise this value comes out to be 6/pi² (using the series sum of inverse squares to be pi²/6)
It’s extremely beautiful how pi emerges out of seemingly nowhere in the problem and I was fascinated the first time I saw it.
Feel free to check out a quick simulation of this in R below where I try to instead approximate pi using this method! We use the numbers library in R for using the coprime function.
https://gist.github.com/Ananyapam7/ce15f4aebdcc3fd0f530a507d67d532f
