If you see Andrew Holmes today, wish him a happy Pi Day! (He’s a fan of (and pie)).
Those of you who were at Dr. Pitale’s Math Club talk learned many cool things. We thought we’d share one in honor of Pi Day.
Question: If you choose two positive integers at random, what is the probability that they will be relatively prime (i.e. only 1 will divide them both evenly)?
Answer: . So around 60%.
The good question is how does show up in a question about relatively prime numbers? Well, when you took Calc III and learned about series, you learned about the series
You probably even learned that this is a p-series with p=2, and that using the integral test it’s easy to see that it converges.
You might have even learned that it converges to (this was first shown by Euler, but Dr. Pitale told us that Euler only gets partial credit as his answer was right, but his proof was wrong!). Notice that this number is the reciprocal of the probability from above. How strange!
We won’t give the full explanation (ask Dr. Pitale for the details, or take his number theory class in the fall!), but let’s at least sketch how it goes:
Say you pick two positive integers at random: call them A and B. We want to know the probability that they are relatively prime.
Well, they’re relatively prime if they have no common factors. That is, if for each prime p, p does not divide both A and B. What’s the probability of that? It’s easier to compute the probability that p does divide both A and B first.
For example, if p=2, then both A and B have to be even numbers if 2 divides both of them. The possibilities are: A is even/B is even, A is even/B is odd, A is odd/B is even, A is odd/B is even. Only 1/4 of the possible outcomes gives both A and B divisible by p=2.
Similarily, if p=3, then 1/9 of the possible outcomes gives both A and B divisible by p=3. In general, it’s not too hard to see that is the fraction of possible outcomes where both A and B are divisible by p.
Therefore, is the probability that A and B are not both divisible by p.
But the odds that A and B are both divisible by one prime is independent of whether they are both divisible by another prime. The probability of independent events is the product of the probabilities of each individual event. So the probability that A and B are relatively prime is equal to
Let’s consider the reciprocal of this number:
Now let , so if we think about the geometric series
we see we can substitute this geometric series into the above product to get
Now, when you FOIL out this product, you should keep in mind that all but finitely many of the terms should be the 1 (That’s how infinite products are defined). So what do you get when you multiple out?
By the Fundamental Theorem of Arithmetic every natural number can uniquely be written in this as a product of prime powers! So on the one hand,
for some natural number n, and on the other hand, each natural number n appears exactly once as one of these products.
If you look carefully what happens when you FOIL it out, you see using the Fundamental Theorem of Arithmetic that you get exactly
That is, you get exactly
Therefore, the reciprocal of the probability is exactly the p-series we started with!
It’s absolutely amazing that this well know series computes such a natural probability/number theory question. And it has the bonus of having showing up, too!
On the other hand, you could just enjoy this video suggested by our own Dr. McCullough: