Chebyshev's problem. Find the probability that a randomly…
Chebyshev's problem. Find the probability that a randomly written fraction cannot be reduced.
Explanation of Method
A fraction $\frac mn$ cannot be reduced iff $m$ and $n$ have no common prime divisor. There is no uniform distribution on all natural numbers, so we take $m$ and $n$ uniformly from $\{1,\dots,N\}$ and let $N\to\infty$. For a prime $p$, the probability that $p$ divides both numbers tends to $\frac1{p^2}$, and divisibility by different primes behaves independently (see Problem 57). So the probability that no prime divides both is $\prod_p\left(1-\frac1{p^2}\right)$, which by Euler's formula equals $\frac{1}{\zeta(2)}=\frac6{\pi^2}$.
Step 1: What "random fraction" means
Write the fraction as $\frac mn$ with natural numbers $m,n$. Choose $m$ and $n$ independently and uniformly from $\{1,2,\dots,N\}$ and let $p_N$ be the probability that $\gcd(m,n)=1$. The answer to the problem is
\[ p = \lim_{N\to\infty}p_N. \]
Step 2: One prime
For a prime $q$, about $\frac1q$ of the numbers in $\{1,\dots,N\}$ are multiples of $q$. Since $m$ and $n$ are independent,
\[ P(q\mid m \text{ and } q\mid n)\to\frac1{q^2}, \qquad P(q \text{ does not divide both})\to1-\frac1{q^2}. \]
Step 3: All primes together
As in Problem 57, divisibility by different primes behaves like independent events: a number is divisible by $q_1q_2\cdots q_s$ exactly when it is divisible by each $q_i$, and the probability of this is $\frac1{q_1\cdots q_s}=\frac1{q_1}\cdots\frac1{q_s}$. Hence
\[ p = \prod_{q \text{ prime}}\left(1-\frac1{q^2}\right) = \left(1-\frac14\right)\left(1-\frac19\right)\left(1-\frac1{25}\right)\left(1-\frac1{49}\right)\cdots \]
(Making the limit over infinitely many primes rigorous uses inclusion–exclusion; the terms for large primes are tiny, because $\sum_q\frac1{q^2}$ converges.)
Step 4: Euler's product formula
Expanding $\left(1-\frac1{q^2}\right)^{-1} = 1+\frac1{q^2}+\frac1{q^4}+\cdots$ and multiplying over all primes, every number $k^2$ appears exactly once (by unique prime factorisation):
\[ \prod_q\left(1-\frac1{q^2}\right)^{-1} = \sum_{k=1}^\infty\frac1{k^2} = \frac{\pi^2}6 \quad(\text{Euler}). \]
Step 5: The answer
\[ \boxed{p = \frac6{\pi^2}\approx0.6079.} \]
Step 6: Check by counting
| $N$ | pairs $(m,n)\le N$ with $\gcd=1$ | $p_N$ |
|---|---|---|
| $10$ | $63$ | $0.6300$ |
| $100$ | $6087$ | $0.6087$ |
| $1000$ | $608\,383$ | $0.6084$ |
| $\infty$ | $6/\pi^2\approx0.6079$ |
So roughly $61\%$ of fractions written "at random" are already in lowest terms.
Result
| Answer | |
|---|---|
| Model | $m,n$ uniform on $\{1,\dots,N\}$, $N\to\infty$ |
| Probability | $\prod_q(1-1/q^2)=6/\pi^2\approx0.608$ |