Mdthbs

Let a and b be random independent positive integers that follow the uniform distribution. What is the probability that the fraction:

$frac{a}{b}$

cannot be simplified?

Peter's answer gets to the heart of the matter relatively quickly, but I feel it would also be best to demonstrate where the $6/pi^2$ comes from, seemingly out of nowhere to the uninitiated.

So, it should be obvious that $a/b$ is in simplest form if and only if $a,b$ are coprime, i.e. $gcd(a,b) = 1$. Well, what does that mean? It means that $a,b$ share no common prime number factors.

In particular, it means $a,b$ do not share a factor of $2$. For (uniformly randomly chosen) nonzero integers $a,b$ (less than some other number $x$), there is a $1/2$ chance (in the limit $x to infty$) each will have a factor of $2$. Thus,

$$P(text{a,b do not have a mutual factor of 2}) = 1 - left(frac 1 2 right)^2$$

Similarly, it means that they do not share a factor of $3$. There's a $1/3$ chance each will have a factor of three, and thus,

$$P(text{a,b do not have a mutual factor of 3}) = 1 - left(frac 1 3 right)^2$$

This clearly generalizes. Consider a prime number $p$. There is a $1/p$ chance that $a,b$ each will have it, and in turn

$$P(text{a,b do not have a mutual factor of p}) = 1 - left(frac 1 p right)^2$$

For $a,b$ to be coprime this needs to be true of all primes $p$. The events are independent, and we accordingly can multiply the respective probabilities for each prime $p$, obtaining

$$P(text{a,b are coprime}) = prod_{text{p prime}} 1 - left(frac 1 p right)^2 = prod_{text{p prime}} 1 - frac 1 {p^2}$$

This now ties into something known as the Riemann zeta function. There are two formulas typically associated with it: a summation and a product formula. We often focus on the summation formula but can derive the latter; a proof of said derivation can be found here. In any event, we focus on the prime product formula below:

$$zeta(s) = prod_{text{p prime}} frac{1}{1-p^{-s}}$$

Bearing in mind this is a product, we can do a manipulation:

$$frac{1}{zeta(s)} = prod_{text{p prime}} 1-frac 1 {p^{s}}$$

This looks precisely like the formula for our probability of $a,b$ being coprime but with $s$ in lieu of $2$. Indeed, letting $s=2$,

$$P(text{a,b are coprime}) = prod_{text{p prime}} 1 - frac{1}{p^2} = frac{1}{zeta(2)}$$

$zeta(2)$ is a known value which Euler calculated to be $pi^2/6$; finding this value is often referred to as the Basel problem. Accordingly,

$$P(text{a,b are coprime}) = frac{1}{pi^2/6} = frac{6}{pi^2}$$

The idea also generalizes further. Say you have some group of $n$ integers ($n$ a positive integer). Then the probability that all $n$ are coprime is given by

$$P(text{all n numbers are coprime}) = frac{1}{zeta(n)}$$

This question is equivalent to ask for the probability that $a$ and $b$ are coprime. If $a$ and $b$ are random integers below $x$, then the probability $P(x)$ that $a$ and $b$ are coprime , satisfies $$lim_{xrightarrowinfty} P(x)=frac{6}{pi^2}approx0.6079$$