# To what extent are divisibility by different primes independent?

Let's prove:

the probability that two randomly chosen integers are relatively prime is $\frac{6}{\pi^2}$.

and a "proof" by separating relative prime-ness into a product of indendent events

Let $p$ be a prime.
The probability of not dividing two random numbers $p \nmid m$ and $p \nmid n$ is $1 - \frac{1}{p^2}$

The probability of $m$ and $n$ having no common prime factor is the product over all prime divisors $\displaystyle \prod_p \left( 1 - \frac{1}{p^2} \right) = \left(\sum_{n \geq 1} \frac{1}{n^2}\right)^{-1} = \frac{6}{\pi^2}$.

I am committing all kinds of probability and number theory errors but the "idea" is correct.

How do I improve this statement and proof to make them more rigorous? I could say:

$\displaystyle \lim_{N \to \infty} \frac{\{ 0\leq m, n \leq N :(m,n) = 1 \}}{N^2} = \frac{6}{\pi^2}$

How do I justify that divisibility by $p$ and divisibility by $q$ are independent? For any number of primes:

$$\mathbb{P}\big( p_1 \dots p_n \big| \; m \big) = \prod_{i=1}^n \mathbb{P}\big(p_i\big| \; m \big)$$

Or can we build a counter example?

UPDATE: It seems to have to do with checking the $\displaystyle \lim_{N \to \infty}$ holds for arbitrary increasing sequences of integers $0< N_1 < N_2 < N_3 < \dots$

This question appears in Math.SE a bunch of times from different angles:

• Have you considered the union of the prime ideals generated by $p$ and $q$ as compared to $\mathbb Z$? – abiessu Sep 23 '13 at 15:09
• The probability is rather $6/\pi^2$ – user8268 Sep 23 '13 at 15:21
• @robjohn how did you get the minus-sign to be red? – cactus314 Sep 23 '13 at 15:49
• Related: math.stackexchange.com/questions/412065/… john, you can right-click equations then go to "show math as" and click "tex commands" and a small window will pop up tell you the latex markup code behind the equations you click. In particular here it will tell you \color{}{} was used. There are also all sorts of latex references and guides on the web. – anon Sep 23 '13 at 16:09
• The statement you set out to prove, «the probability of two randomly chosen integers is $6/pi^2$», does not make sense. What probability is it thatyou want to compute? – Mariano Suárez-Álvarez Sep 23 '13 at 21:24

## 1 Answer

If you consider any multiple of $pq$ consecutive integers, say $\mathcal{S}=\{1,2,3,\dots,kpq\}$, exactly $\frac1{pq}$ of them will be divisible by both $p$ and $q$; exactly $\frac1p$ will be divisible by $p$, and exactly $\frac1q$ will be divisible by $q$. Thus, exactly $\frac1{p^2q^2}$ of the pairs in $\mathcal{S}\times\mathcal{S}$ will be divisible by both $p$ and $q$, exactly $\frac1{p^2}$ will be divisible by $p^2$, and exactly $\frac1{q^2}$ will be divisible by $q^2$.

This can be extended for any set of primes; just take a set of $pqr\dots s$ consecutive integers, $\mathcal{S}=\{1,2,3,\dots,kpqr\dots s\}$, exactly $\frac1{p^2q^2r^2\dots s^2}$ of the pairs in $\mathcal{S}\times\mathcal{S}$ will be divisible by all $p,q,r,\dots s$. Thus, we don't need to appeal to probability, and what would be considered independence in a probabilistic setting, follows from the Chinese Remainder Theorem.

Chinese Remainder Theorem

If you want to know how many integers are relatively prime to $pqr\dots s$ in the set $\mathcal{S}=\{1,2,3,\dots,kpqr\dots s\}$, the Chinese Remainder Theorem says that there is one solution to \begin{align} x&\equiv a\pmod{p}\\ x&\equiv b\pmod{q}\\ x&\equiv c\pmod{r}\\ &\vdots\\ x&\equiv d\pmod{s} \end{align} mod $pqr\dots s$ for each choice of $a,b,c,\dots,d$. Thus, to be relatively prime to $pqr\dots s$, we can choose $a,b,c,\dots,d$ to be any non-zero residue modulo the corresponding prime. That is, there are $(p-1)(q-1)(s-1)\dots(s-1)$ numbers mod $pqr\dots s$ that are relatively prime to $pqr\dots s$. In other words, $\frac{(p-1)(q-1)(r-1)\dots(s-1)}{pqr\dots s}$ of the numbers in $\mathcal{S}$ are relatively prime to $pqr\dots s$.

Limits

Define $$\mathcal{S}_n=\left\{j\in\mathbb{Z}:1\le j\le n\right\}$$ Note that the number of pairs in $\mathcal{S}_n\times\mathcal{S}_n$ sharing any prime $p$ is at most $\frac{n^2}{p^2}$.

Choose an $\epsilon\gt0$ and then pick an $N$ so that $$\sum_{p\ge N}\frac1{p^2}\le\epsilon$$ and choose a $K$ so that $K\epsilon\ge1$. Set $P=\prod\limits_{p\lt N}p$.

We know that exactly $\prod\limits_{p\lt N}\left(1-\frac1{p^2}\right)$ of the pairs in $\mathcal{S}_{kP}\times\mathcal{S}_{kP}$ share no prime factor less than $N$.

Consider $\mathcal{S}_n$ where $kP\le n\le(k+1)P$ and $k\ge K$. Since the ratio of the sizes of these sets is no more than $\frac{k+1}{k}$, the fraction of pairs can only change by a ratio of $\left(\frac{k+1}{k}\right)^2\le(1+\epsilon)^2$.

Furthermore, the fraction of pairs of $\mathcal{S}_n\times\mathcal{S}_n$ sharing any prime greater than $N$ is at most $$\frac1{n^2}\sum_{p\ge N}\frac{n^2}{p^2}\le\epsilon$$ Therefore, because the variation in the fraction of pairs of $\mathcal{S}_n\times\mathcal{S}_n$ varies little and the fraction of pairs sharing primes unaccounted for is small, we get that the fraction of pairs of $\mathcal{S}_n\times\mathcal{S}_n$ that share no prime factors tends to $$\prod_{p\in\mathbb{P}}\left(1-\frac1{p^2}\right)=\left(\sum_{k=1}^\infty\frac1{k^2}\right)^{-1}=\frac6{\pi^2}$$

• OK. Our intuition tells us to test specific sequence of values of $N = 1, p_1, p_1 p_2, p_1 p_2 p_3, \dots$. There may be other values $N_1 < N_2 < N_3 < \dots$ where this limit doesn't hold. Got it. – cactus314 Sep 23 '13 at 15:52
• @johnmangual: I have added a section on the limits. Let me know if any concerns remain. – robjohn Sep 23 '13 at 21:17