Unlikely

Let N N and M M be two randomly chosen positive integers.

What is the probability p = P ( ( N , M ) = 1 ) p = P((N,M) = 1) , that is, the probability that M M and N N are coprime, and thus have no common divisors greater than one?

Give your answer as 10000 p \lfloor 10000 p\rfloor .


The answer is 6079.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

M M and N N are coprime iff they have no common prime factors.

Thus M M and N N are not both divisible by 2; not both divisible by 3; not both divisible by 5; and so on. This gives p = ( 1 1 2 2 ) ( 1 1 3 2 ) ( 1 1 5 2 ) ( 1 1 p 2 ) p = \left(1-\frac 1{2^2}\right)\cdot\left(1-\frac 1{3^2}\right)\cdot\left(1-\frac 1{5^2}\right)\cdots\left(1-\frac 1{p^2}\right)\cdots

If we expand this fraction, we get p = 1 1 2 2 1 3 2 1 5 2 + 1 6 2 1 7 2 + 1 1 0 2 1 1 1 2 1 1 3 2 + 1 1 4 2 + 1 1 5 2 + = n = 1 μ ( n ) n 2 , p = 1 - \frac1{2^2}-\frac1{3^2}-\frac1{5^2}+\frac1{6^2}-\frac1{7^2}+\frac1{10^2}-\frac1{11^2}-\frac1{13^2}+\frac 1{14^2}+ \frac 1{15^2}+-\cdots \\ = \sum_{n=1}^\infty \frac{\mu(n)}{n^2}, where μ ( n ) \mu(n) is the Moebius function, which is 0 for any number divisible by a square, and ( 1 ) r (-1)^r for any number containing r r distinct prime factors.

To evaluate p p , let's try to find its multiplicative inverse. We will add multiples of p p to cancel the terms one by one, leaving only 1, as follows: p = 1 1 / 2 2 1 / 3 2 1 / 5 2 + 1 / 6 2 1 / 7 2 + 1 / 1 0 2 + p / 2 2 = + 1 / 2 2 1 / 4 2 1 / 6 2 1 / 1 0 2 + p / 3 2 = + 1 / 3 2 1 / 6 2 1 / 9 2 + p / 4 2 = + 1 / 4 2 1 / 8 2 + p / 5 2 = + 1 / 5 2 1 / 1 0 2 + p / 6 2 = + 1 / 6 2 + p / 7 2 = + 1 / 7 2 + p / 8 2 = + 1 / 8 2 + p / 9 2 = + 1 / 9 2 + p / 1 0 2 = + 1 / 1 0 2 + = + sum = 1 \begin{array}{rccccccccccc} p = & 1 & -1/2^2 & - 1/3^2 & & -1/5^2 & +1/6^2 & -1/7^2 & & & +1/10^2 & +\cdots \\ p/2^2 = & & +1/2^2 & & -1/4^2 & & -1/6^2 & & & & -1/10^2 & + \cdots \\ p/3^2 = & & & +1/3^2 & & & -1/6^2 & & & -1/9^2 & & + \cdots \\ p/4^2 = & & & & +1/4^2 & & & & -1/8^2 & & & +\cdots \\ p/5^2 = & & & & & +1/5^2 & & & & & -1/10^2 & +\cdots \\ p/6^2 = & & & & & & +1/6^2 & & & & & + \cdots \\ p/7^2 = & & & & & & & +1/7^2 & & & & + \cdots \\ p/8^2 = & & & & & & & & +1/8^2 & & & +\cdots \\ p/9^2 = & & & & & & & & & +1/9^2 & & + \cdots \\ p/10^2 = & & & & & & & & & & +1/10^2 & + \cdots \\ \vdots = & \vdots & & & & & & & & & \vdots & + \ddots \\ \hline \text{sum} = & 1 & & & & & & & & & & \end{array}

I leave it to the reader to convince him/herself that in this way all terms cancel, except the first. Thus we have p ( 1 + 1 2 2 + 1 3 2 + 1 4 2 + ) = 1. p\left(1 + \frac1{2^2} + \frac1{3^2} + \frac1{4^2} + \cdots\right) = 1. The series in brackets is well-known to converge to π 2 / 6 \pi^2/6 , so that p = 1 n = 1 n 2 = 1 π 2 / 6 = 6 π 2 0. 6079 27102. p = \frac 1 {\sum_{n=1}^\infty n^{-2}} = \frac 1{\pi^2/6} = \frac 6{\pi^2}\approx 0.\boxed{6079}27102.

Note : In general, n = 1 μ ( n ) n s = 1 ζ ( s ) , \sum_{n=1}^\infty \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}, with ζ ( n ) = p prime ( 1 p s ) \zeta(n) = \sum_{p\ \text{prime}} (1-p^{-s}) the Riemann zeta function. Here s = 2 s = 2 and ζ ( s ) = π 2 / 6 \zeta(s) = \pi^2/6 .

Wow! This is extremely well written! Thank You!

Pi Han Goh - 5 years, 6 months ago

Do you have a hint on "how to prove that all the terms cancel, except the first"?

Pi Han Goh - 5 years, 5 months ago

Extremely interesting! The answer is a marvelous surprise!

James Wilson - 3 years, 7 months ago

Log in to reply

By unlikely, I think he meant unlikely that you would get the answer.

James Wilson - 3 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...