Editing Coprime integers (section)

==Probability of coprimality ==

Given two randomly chosen integers {{mvar|a}} and {{mvar|b}}, it is reasonable to ask how likely it is that {{mvar|a}} and {{mvar|b}} are coprime. In this determination, it is convenient to use the characterization that {{mvar|a}} and {{mvar|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) {{mvar|p}} is {{tmath|\tfrac{1}{p};}} for example, every 7th integer is divisible by 7. Hence the probability that two numbers are both divisible by {{mvar|p}} is {{tmath|\tfrac{1}{p^2},}} and the probability that at least one of them is not is {{tmath|1-\tfrac{1}{p^2}.}}  Any finite collection of divisibility events associated to distinct primes is mutually independent.  For example, in the case of two events, a number is divisible by primes {{mvar|p}} and {{mvar|q}} if and only if it is divisible by {{mvar|pq}}; the latter event has probability {{tmath|\tfrac{1}{pq}.}}  If one makes the heuristic assumption that such reasoning can be extended to infinitely many divisibility events, one is led to guess that the probability that two numbers are coprime is given by a product over all primes,

: <math>\prod_{\text{prime } p} \left(1-\frac{1}{p^2}\right) = \left( \prod_{\text{prime } p} \frac{1}{1-p^{-2}} \right)^{-1} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2} \approx 0.607927102 \approx 61\%.</math>

Here {{mvar|&zeta;}} refers to the [[Riemann zeta function]], the identity relating the product over primes to {{math|''&zeta;''(2)}} is an example of an [[Euler product]], and the evaluation of {{math|''&zeta;''(2)}} as {{math|''π''<sup>2</sup>/6}} is the [[Basel problem]], solved by [[Leonhard Euler]] in 1735.

There is no way to choose a positive integer at random so that each positive integer occurs with equal probability, but statements about "randomly chosen integers" such as the ones above can be formalized by using the notion of ''[[natural density]]''.  For each positive integer {{mvar|N}}, let {{mvar|P{{sub|N}}}} be the probability that two randomly chosen numbers in <math>\{1,2,\ldots,N\}</math> are coprime.   Although {{mvar|P{{sub|N}}}} will never equal {{math|6/''π''<sup>2</sup>}} exactly, with work<ref>This theorem was proved by [[Ernesto Cesàro]] in 1881. For a proof, see {{harvnb|Hardy|Wright|2008|loc=Theorem 332}}</ref> one can show that in the limit as <math>N \to \infty,</math> the probability {{mvar|P{{sub|N}}}} approaches {{math|6/''π''<sup>2</sup>}}.

More generally, the probability of {{mvar|k}} randomly chosen integers being setwise coprime is {{tmath|\tfrac{1}{\zeta(k)}.}}