Probability of Two Integers Being Coprime
Introduction
What is the probability of two random integers being coprime?
A short proof of this statement by Aaron Abrams and Matteo Paris in the College Mathematics Journal was introduced by a letter from Henry L. Adler where he tells the story of the proof. He found the question "natural to ask" so it was no surprise when students in his introductory number theory class had indeed raised the question. He answered it with a "traditional proof" that required "considerable prior knowledge of number theory," but then the two authors (16- and 17-year olds at the time) came up with a short and intuitively clear proof. He then encouraged the boys to share their proof with the readers of the College Mathematics Journal "who might be asked the same question in their classes."
A few lines proof made a reference to [Yaglom & Yaglom, pp 202-204] for the justification of the concepts involved (the formalism of selecting a random integer.) Yagloms' book also poses the question at hand and provides a more or less elementary but very detailed solution. Yagloms refer to the question as "Chebyshev's problem" and outline the contribution of Pafnuty L. Chebyshev in a short footnote, although there is no indication that the solution in the book has originated with the famous Russian mathematician. It is rather straightforward and does not require "considerable prior knowledge of number theory."
One that does can be found in the classic An Introduction to the Theory of Numbers by Hardy and Wright. Without doubt, Chebyshev could have authored either of the two proofs, but Hardy and Wright do not mention his name neither as the question poser nor solver.
In any event, I find this amusing that this "natural to ask question" might have been first asked by a mathematician of Chebyshev's stature.
Below I give all three proofs in this order: Yagloms', Abrams and Paris, and then Hardy and Wright's; the later will be extended shortly with relevant information from number theory.
Aaron Abrams and Matteo Paris' proof could be found in Charming Proofs (pp. 230-233) where the authors also refer to Yagloms' book but do not mention Chebyshev's name, the boys' ages, or relate Adler's story.
References
- A. D. Abrams, M. J. Paris, The Probability that $(a,b)=1,$ College Mathematics Journal, 23 (1992), p. 47
- C. Alsina, R. B. Nelsen, Charming Proofs, MAA, 2010
- G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, Fifth Edition, 1996
- A. M. Yaglom, I. M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, Vol I, Dover, 1987
Straightforward solution
If two numbers are coprime, then, in particular, no prime is their common factor. So we start with a simpler problem:
What is the probability that $2$ is not a common factor of two random integers?
Given two random numbers $a$ and $b,$ for each the probability of being divisible by $2$ is $\displaystyle\frac{1}{2}$ such that the probability of them both being divisible by $2$ is $\displaystyle\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}.$ Therefore, the probability that $2$ is not their common factor is $\displaystyle 1-\frac{1}{4}.$
Similarly, for any prime $p,$ the probability that $p$ does not divide both selected numbers is $\displaystyle 1-\frac{1}{p^2}.$
There is no basis to assume that divisibility by one prime number is anyhow related to the divisibility by any other prime number. We, therefore, assume that events of divisibility by prime numbers (or their complements) are independent such that the probability that two numbers are not simultaneously divisible by any prime should be the product:
$\displaystyle(1-\frac{1}{2^2})(1-\frac{1}{3^2})(1-\frac{1}{5^2})\cdot\ldots =\prod_{p}(1-\frac{1}{p^2}),$
where the product is taken over the whole sequence of prime numbers. This needs to be understood as the limit of finite products:
$\displaystyle\prod_{p}(1-\frac{1}{p^2}) = \lim_{n\to\infty}\prod_{k=1}^{n}(1-\frac{1}{p_{k}^2}),$
where $\{p_k\}$ is the sequence of prime numbers: $p_{1}=2,$ $p_{2}=3,$ $p_{3}=5,$ and so on.
We have to check that the limit exists:
$\begin{align}\displaystyle \bigg[\prod_{k=1}^{n}(1-\frac{1}{p_{k}^2})\bigg]^{-1} &= \prod_{k=1}^{n}\frac{1}{1-\frac{1}{p_{k}^2}}\\ &= \prod_{k=1}^{n}\bigg(1+\frac{1}{p_{k}^{2}}+\frac{1}{p_{k}^{4}}+\frac{1}{p_{k}^{6}}+\ldots\bigg) \end{align}$
because each fraction $\displaystyle\frac{1}{1-\frac{1}{p_{k}^2}}$ is the sum of the geometric series $\displaystyle 1+\frac{1}{p_{k}^{2}}+\frac{1}{p_{k}^{4}}+\frac{1}{p_{k}^{6}}+\ldots$
But, if we multiply out, we get a surprising result
$\displaystyle \prod_{k=1}^{n}\bigg(1+\frac{1}{p_{k}^{2}}+\frac{1}{p_{k}^{4}}+\frac{1}{p_{k}^{6}}+\ldots\bigg)= 1+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\frac{1}{5^2}\ldots $
where the sum is over all integers whose prime factors do not exceed $p_k.$ As $k$ grows, the gaps in the series are filled in so that at the limit
$\displaystyle \prod_{p}\bigg(1+\frac{1}{p_{k}^{2}}+\frac{1}{p_{k}^{4}}+\frac{1}{p_{k}^{6}}+\ldots\bigg)= 1+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\frac{1}{5^2}\ldots $
where on the right each integer appears exactly once due to the Fundamental Theorem of Arithmetic, i.e., the fact that every integer has a unique (up to the order of the factors) representation as the product of powers of distinct prime numbers. The sum on the right is known to converge and its sum, as was first found by L. Euler, equals
$\displaystyle 1+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\frac{1}{5^2}\ldots = \frac{\pi ^2}{6}, $
from which is follows that the probability of two random integers to be coprime is $\displaystyle\frac{6}{\pi ^2}.$
Shortest solution
Let $q$ denote the sought probability of two random integers being coprime. Pick an integer $k$ and two random numbers $a$ and $b.$ The probability that $k$ divides $a$ is $\displaystyle\frac{1}{k},$ and the same holds for $b$. Therefore, the probability that both $a$ and $b$ are divisible by $k$ equals $\displaystyle\frac{1}{k^2}.$ The probability that $a$ and $b$ have no other factors, i.e., that $\displaystyle\mbox{gcd}\bigg(\frac{a}{k},\frac{b}{k}\bigg)=1$ equals $q,$ by our initial assumption. But $\displaystyle\mbox{gcd}\bigg(\frac{a}{k},\frac{b}{k}\bigg)=1$ is equivalent to $\displaystyle\mbox{gcd}(a,b)=k.$ Assuming independence of the events, it follows that the probability that $\mbox{gcd}(a,b)=k$ equals $\displaystyle\frac{1}{k^2}\cdot q=\frac{q}{k^2}.$
Now, $k$ was just one possibility for the greatest common divisor of two random numbers. Any number could be the $\mbox{gcd}(a,b).$ Furthermore, since the events $\mbox{gcd}(a,b)$ are mutually exclusive (the $\mbox{gcd}$ of two numbers is unique) and the total probability of having a $\mbox{gcd}$ at all is $1$ leads to:
$\displaystyle 1=\sum_{k=1}^{\infty}\frac{q}{k^2}, $
implying that
$\displaystyle q=\bigg[\sum_{k=1}^{\infty}\frac{1}{k^2}\bigg]^{-1}=\frac{6}{\pi ^2}. $
Number theoretic solution
Notations first: $\phi (n)$ - Euler's totient function, the number of integers not greater than $n$ and coprime to $n.$ $\Phi (n)=\sum_{k=1}^{n}\phi(n).$ $\mu (n)$ - the Möbius function:
$\begin{cases} \mu (1)=1; & \\ \mu (n)=0, & \mbox{if}\space n\space\mbox{has a squared factor}; \\ \mu (p_{1}p_{2}\cdots p_{k}) = (-1)^k, & \mbox{if all primes}\space p_{k}\space\mbox{are different}. \end{cases}$
Both functions $\phi$ and $\mu$ are multiplicative, meaning that for coprime $a$ and $b,$ $\phi (ab)=\phi (a)\phi (b)$ and $\mu (ab)=\mu (a)\mu (b).$
The two functions are related in the following manner:
$\displaystyle\phi (n)=n\sum_{d|n}\mu (d)=\sum_{d|n}\frac{n}{d}\mu (d)=\sum_{d|n}d\mu (\frac{n}{d})=\sum_{dd'=n}d'\mu (d).$
$\mu$ has an important property:
$\displaystyle\sum_{d|n}\mu (d)= \begin{cases} 1, & \mbox{if}\space n = 1;\\ 0, & \mbox{otherwise.} \end{cases}$
Finally, remember the "Big $O$" notation: to say that $f=O(g)$ is equivalent to saying that $|f|\le C|g|,$ for $C$ not dependent on $g.$
$\displaystyle \begin{align} \Phi (n) &= \sum_{m=1}^{n}m\sum_{d|m}\frac{\mu (d)}{d}=\sum_{dd'\le n}d'\mu (d)\\ &=\sum_{d=1}^{n}\mu (d)\sum_{d'=1}^{[n/d]}d'=\frac{1}{2}\sum_{d=1}^{n}\mu (d)\bigg(\bigg[\frac{n}{d}\bigg]^{2}+\bigg[\frac{n}{d}\bigg]\bigg)\\ &=\frac{1}{2}\sum_{d=1}\mu (d)\bigg\{\frac{n^2}{d^2}+O\bigg(\frac{n}{d}\bigg)\bigg\}\\ &=\frac{1}{2}n^{2}\sum_{d=1}^{n}\frac{\mu (d)}{d^2}+O\bigg(n\sum_{d=1}^{n}\frac{1}{d}\bigg)\\ &=\frac{1}{2}n^{2}\sum_{d=1}^{\infty}\frac{\mu (d)}{d^2}+O\bigg(n^{2}\sum_{n+1}^{\infty}\frac{1}{d^2}\bigg)+O(n\log n)\\ &=\frac{n^2}{2\zeta (2)}+O(n)+O(n\log n)=\frac{3n^{2}}{\pi ^{2}}+O(n\log n), \end{align}$
where $\zeta (s)$ is the famous $\zeta$ function: $\displaystyle\zeta (s)=\sum_{n=1}^{\infty}n^{-s}.$ As was mentioned above, it was established by L. Euler that $\displaystyle\zeta(2)=\frac{\pi ^2}{6}.$
Noteworthy is the fact that $\Phi (n)+1$ is the number of terms in the $n\mbox{th}$ Farey series which consists of an ordered list of irreducible fractions from the interval $[0,1]$ whose denominators do not exceed $n.$
Now, assume $n$ is given and consider fractions $\displaystyle\frac{q}{p}$ that satisfy
$q\gt 0\space$ and $1\le q\le p\le 1.$
If, say, $\xi_{n}$ is the number of those fractions in lowest terms out of the total $\displaystyle\psi_{n}=\frac{n(n+1)}{2}\sim\frac{n^2}{2}$ fractions. Thus the probability that $q$ and $p$ are coprime is given by
$\displaystyle\lim_{n\to\infty}\frac{\xi_{n}}{\psi_{n}}=\frac{6}{\pi ^2}.$
- What Is Probability?
- Intuitive Probability
- Probability Problems
- Sample Spaces and Random Variables
- Probabilities
- Conditional Probability
- Dependent and Independent Events
- Algebra of Random Variables
- Expectation
- Probability Generating Functions
- Probability of Two Integers Being Coprime
- Random Walks
- Probabilistic Method
- Probability Paradoxes
- Symmetry Principle in Probability
- Non-transitive Dice
|Contact| |Front page| |Contents| |Algebra| |Probability| |Store|
Copyright © 1996-2018 Alexander Bogomolny71925298