Mfcttrf

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

$fracab$

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(texta,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(texta,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(texta,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(texta,b are coprime) = prod_textp prime 1 - left(frac 1 p right)^2 = prod_textp 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_textp prime frac11-p^-s$$

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

$$frac1zeta(s) = prod_textp 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(texta,b are coprime) = prod_textp prime 1 - frac1p^2 = frac1zeta(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(texta,b are coprime) = frac1pi^2/6 = frac6pi^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(textall n numbers are coprime) = frac1zeta(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)=frac6pi^2approx0.6079$$