Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

share|improve this question
    
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
2  
The probability is rather $6/\pi^2$ –  user8268 Sep 23 '13 at 15:21
1  
@robjohn how did you get the minus-sign to be red? –  john mangual Sep 23 '13 at 15:49
1  
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
1  
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-Alvarez Sep 23 '13 at 21:24

1 Answer 1

up vote 5 down vote accepted

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} $$

share|improve this answer
1  
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. –  john mangual 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.