Why π knows whether a fraction cancels
Tonight's idea
Choose two whole numbers \(a\) and \(b\), each from 1 to \(N\), every choice equally likely. The fraction \(\tfrac{a}{b}\) cancels exactly when \(a\) and \(b\) share a prime factor. Otherwise \(\gcd(a, b) = 1\) and the pair is called coprime. How likely is that?
Start with \(N = 6\). The 36 ordered pairs make a grid. Shade a cell when \(a\) and \(b\) share a factor.
Both even: \(3 \times 3 = 9\) cells. Both multiples of 3: \(2 \times 2 = 4\). Both multiples of 5: just \((5, 5)\). But \((6, 6)\) is both even and a multiple of 3, so it was shaded twice. Add it back once:
\(36 - 9 - 4 - 1 + 1 = 23\) coprime pairs, a proportion of \(\tfrac{23}{36} \approx 0.639\). Subtract, then add back what was subtracted twice: inclusion–exclusion, the same bookkeeping as in probability.
For a prime \(p\), about \(\tfrac1p\) of the numbers up to \(N\) are multiples of \(p\), so about \(\tfrac{1}{p^2}\) of the pairs share \(p\) and a share \(1 - \tfrac{1}{p^2}\) avoids it. On a big grid the primes act almost independently, which is where the stretch begins.
Watch one: bigger grids
Counting \(\gcd(a, b) = 1\) over every cell of an \(N \times N\) grid gives these exact totals:
| \(N\) | 6 | 10 | 20 | 100 |
|---|---|---|---|---|
| coprime ordered pairs | 23 | 63 | 255 | 6087 |
| proportion | 0.6389 | 0.6300 | 0.6375 | 0.6087 |
Guess where the proportion is heading before you read on. It wobbles, since each new \(N\) adds a row and a column, but the wobbles shrink. As \(N\) grows without bound the proportion tends to a limit, and the limit is
\(\dfrac{6}{\pi^2} \approx 0.6079\). This is a claim about the limit of finite grids. For any particular \(N\) the proportion is an ordinary fraction, and there is no such thing as a uniformly random positive integer. The \(N = 1000\) grid gives 608 383 coprime pairs out of a million.
Your turn
- For \(N = 10\), count the pairs that share 2, share 3, share 5 and share 7. Then count the pairs that share 6 and the pairs that share 10. Use inclusion–exclusion to confirm the total of 63 coprime pairs.
- Explain why exactly \(\tfrac14\) of the 36 cells have both \(a\) and \(b\) even, but for \(N = 7\) the fraction of both-even cells is not exactly \(\tfrac14\). What does that fraction approach as \(N\) grows?
- The cell \((a, a)\) is coprime only when \(a = 1\), and the grid is symmetric about that diagonal. Show that the number of coprime ordered pairs is odd for every \(N\). Check against the table.
- Simulate it. With a spreadsheet, draw 200 pairs from 1 to 1000 and count those with \(\mathrm{GCD}(a, b) = 1\). Record \(N\), the sample size and the proportion. How far from 0.608 would be surprising?
Stretch: the product over primes
Multiply \(1 - \tfrac{1}{p^2}\) over the primes 2, 3, 5, 7. Then write each \(\big(1 - \tfrac{1}{p^2}\big)^{-1}\) as a geometric series \(1 + \tfrac{1}{p^2} + \tfrac{1}{p^4} + \cdots\) and multiply those out. Using unique factorisation, which sum from Corner 12 appears, and why is the limit \(6/\pi^2\)?
Answers
- Share 2: \(5 \times 5 = 25\). Share 3: \(3 \times 3 = 9\). Share 5: \(2 \times 2 = 4\). Share 7: 1. Share 6: only \((6, 6)\), 1 cell. Share 10: only \((10, 10)\), 1 cell. No pair shares 14 or 15. Total \(100 - 25 - 9 - 4 - 1 + 1 + 1 = 63\).
- Up to 6 there are exactly 3 even numbers, so \(3 \times 3 = 9 = \tfrac14 \times 36\). Up to 7 there are still 3 evens, giving \(\tfrac{9}{49}\), not \(\tfrac14\). The fraction approaches \(\tfrac14\) as \(N\) grows, since the number of evens is always within one of \(N/2\).
- Off the diagonal, coprime cells come in mirror pairs, \((a, b)\) with \((b, a)\): an even count. The diagonal contributes exactly one coprime cell, \((1, 1)\). Even plus one is odd. The table shows 23, 63, 255 and 6087, all odd.
- Answers vary. Each draw is coprime with probability about 0.608, so the count out of 200 has standard deviation \(\sqrt{200 \times 0.608 \times 0.392} \approx 6.9\), about 0.035 as a proportion. A result outside roughly 0.54 to 0.68 would be surprising.
Stretch. \(\tfrac34 \cdot \tfrac89 \cdot \tfrac{24}{25} \cdot \tfrac{48}{49} \approx 0.627\); taking primes up to 50 brings it to 0.610. Multiplying the series out, every product \(\tfrac{1}{p^{2k} q^{2m} \cdots}\) is \(\tfrac{1}{n^2}\) for exactly one \(n\), because each \(n\) factorises in exactly one way. So the product of all the \(\dfrac{1}{1 - 1/p^2}\) is \(1 + \tfrac14 + \tfrac19 + \cdots = \tfrac{\pi^2}{6}\), and the product of the \(1 - \tfrac{1}{p^2}\), the limiting coprime proportion, is its reciprocal \(\tfrac{6}{\pi^2}\). A rigorous version handles finitely many primes at a time and bounds what the rest can change.