Coprime Integers - Probabilities

Probabilities

Given two randomly chosen integers a and b, it is reasonable to ask how likely it is that a and b are coprime. In this determination, it is convenient to use the characterization that a and b are coprime if and only if no prime number divides both of them (see Fundamental theorem of arithmetic).

Informally, the probability that any number is divisible by a prime (or in fact any integer) is ; for example, every 7th integer is divisible by 7. Hence the probability that two numbers are both divisible by this prime is, and the probability that at least one of them is not is . For distinct primes, these divisibility events are mutually independent. For example, in the case of two events, a number is divisible by p and q if and only if it is divisible by pq; the latter event has probability 1/pq. (Independence is not be true in general, that is, if we consider composite numbers.) Thus the probability that two numbers are coprime is given by a product over all primes,

Here ζ refers to the Riemann zeta function, the identity relating the product over primes to ζ(2) is an example of an Euler product, and the evaluation of ζ(2) as π2/6 is the Basel problem, solved by Leonhard Euler in 1735. In general, the probability of k randomly chosen integers being coprime is 1/ζ(k).

The notion of a "randomly chosen integer" in the preceding paragraphs is not rigorous. One rigorous formalization is the notion of natural density: choose the integers a and b randomly between 1 and an integer N. Then, for each upper bound N, there is a probability P_N that two randomly chosen numbers are coprime. This will never be exactly, but in the limit as, the probability approaches .