Tuesday, January 3, 2012

Euler product formula

The Euler product formula can be used to calculate the asymptotic probability that s randomly selected integers are set-wise coprime. Intuitively, the probability that any single number is divisible by a prime (or any integer), p is 1/p.

Hence the probability that s numbers are all divisible by this prime is 1/p^s, and the probability that at least one of them is not is 1 − 1/p^s. Now, for distinct primes, these divisibility events are mutually independent because the candidate divisors are coprime (a number is divisible by coprime divisors n and m if and only if it is divisible by nm, an event which occurs with probability 1/(nm).)

Thus the asymptotic probability that s numbers are coprime is given by a product over all primes,