I’ve been working on other posts, but they’ve been harder to write than expected. A quick recreational math post should help fill the gap.
I’m targeting this towards the high school math contest audience. That means I won’t assume anything past calculus, but I will assume many things up to calculus, and I also assume people reading this will look up unfamiliar terms on their own.
Relatively Prime Random Numbers
Let and be two uniformly random natural numbers. What is the probability and are relatively prime?
First off, this problem isn’t well formed. You can’t define a uniform distribution over the naturals, because such a distribution would break probability theory axioms. (See here if curious.) To make this formal, we should really be picking naturals uniformly from to , and ask what the probability converges to as approaches .
Let be the probability that two uniformly random natural numbers from to (inclusive) are relatively prime. What is ?
This was first solved by Dirichlet in 1849. For this proof, I’m handwaving the limit and assuming that random natural numbers act according to intuition.
Two numbers are relatively prime if they share no common factors. This is true if and only if for every prime , and are not both divisible by .
Since we pick uniformly at random, the probability divides a random natural number is . The probabillity both numbers are divisible by is , giving
Now, here’s where you apply a neat trick. Take the reciprocal of both sides.
For each fraction, substitute the infinite series .
I claim the right hand side is the same as
The argument follows from a clever factoring argument. Suppose we expanded out the product of the infinite series. We would get infinitely many terms, where each term is generated by choosing one term from every infinite series and multiplying them together. For example, take from the series, from the series, and from the rest. The term obtained is
Now, take from the series, from the series, from the series, and from the rest. That gives
We can pick terms such that they multiply to for any . For every prime , find the largest power that divides . ( could be .) Then, take from the series. By prime factorization, the product is
Every natural number has a unique prime factorization, so every is generated once and exactly once. Thus, the product expands to the sum of the reciprocal of the squares
(If you’re like me, you may want to spend a moment admiring this argument. It’s a contender for my favorite proof ever.)
The final expression is
gives that the probability is .
Riemann Zeta And More Handwaving
Now, unless you’ve seen it before, it should not be clear why
This was first proved by Euler in 1734. His proof was a bit sketchy, and it took another 7 years to make it rigorous. Nevertheless, I’m presenting the sketchy proof.
To prove this result, we’re going to start from something completely different: the Taylor series for . For all ,
Divide through by to get
(If you don’t know what Taylor series are, take this on faith. I don’t want to do calculus.)
The idea Euler used was to treat as an infinite degree polynomial. Any polynomial with roots can be written as
where is some constant. For this proof, we’re using a different form. Divide each term by to get
where is some other constant. Assuming this works for functions with infinitely many roots, at .
Equate this with the Taylor series. To make the constant term match up, we must have . (Try converting to the form and you’ll see why it’s sketchy to assume acts like an infinite degree polynomial.)
Group up the terms for roots and to get
Now, compare the coefficient of . To get an term, we have to choose exactly once, and choose from the rest. This gives
Which gives the final answer of
This sum of reciprocals is a special case of the Riemann zeta function, defined as
It turns out that analyzing this function for complex has deep connections to the primes. I can’t explain why because I don’t know analytic number theory, but if you consider that we started from relatively prime numbers and got to here, I don’t think a connection is too strange.
By Prime Products
I’ll close with a fun identity that relates the prime numbers to . This identity was also discovered by Euler.
Every odd prime is either or . Take the negative reciprocal if it’s and the positive reciprocal if it’s . Add , take the product over all odd primes, and you get the identity
The proof borrows from both previous sections. First, take the reciprocal.
Replace each term with an infinite series
And again, expand out the infinite product. Ignoring the signs, this is exactly the same as the product for relatively prime random numbers, except without an infinite series for . When expanded, we’ll get exactly one term for every odd number.
(I love this factoring trick so much. It’s great, even if it’s difficult to apply on other problems.)
Now, consider the signs of those terms. Term is positive if and only if is the product of an even number of (not necessarily distinct) primes. If you multiply an even number of primes, you get a number that’s . If you multiply an odd number of those primes, you’ll get a number.
So, the sign is negative at every other odd number, giving an expansion of
which - surprise - is Leibniz’s formula for . (It follows from the Taylor series for evaluated at .)
Oh My! That’s All, Folks!
That’s all I’ve got. See you next time, for something less mathy.