# $kN^{2}$ relatively prime pairs in $\mathbf{Z}^{2}$

If $k= 1- \sum _{p\in \mathbf{P}} \frac{1}{p^{2}}$, then there are at least $kN^{2}$ pairs $(n_{1},n_{2})$ in $\mathbf{Z}^{2}$, with $1\le n_{1}, n_{2} \le N$ and $gcd(n_{1},n_{2})=1$. Also since $k>0$ it follows that $gcd = 1$ exists with a probability greater than 0.

I don't understand a couple of things with this problem: why is k set to $1- \sum _{p\in \mathbf{P}} \frac{1}{p^{2}}$? F.e. if we plug in p=2 , we had $k=1-\sum_{2}\frac{1}{4} = \frac{3}{4}$. So that would mean if N was 6 we would have $36*\frac{3}{4} = 27$ relatively prime pairs ? I just don't see how to continue.

## 1 Answer

Lets look at the $x\times x$ square in the first quadrant. For a given prime $p$, there are exactly $$\left[\frac{x}{p}\right]^2$$ pairs with both $m,n$ divisible by $p$, where $[x]$ is the floor of $x$. This means that in this square, there are at least $$[x]^2 -\left[\frac{x}{2}\right]^2-\left[\frac{x}{3}\right]^2-\cdots =[x]^2-\sum_p \left[\frac{x}{p}\right]^2$$ relatively prime pairs. Since $[t]-t=+O(1)$, and the sum of squares converges, we see that in $\mathbb{Z}^2$ the density of relatively prime pairs is at least $$1-\sum_p \frac{1}{p^2}.$$

Note: The actual number of pairs is more then this, as we are double counting. For example, we remove the pair $(6,6)$ twice, once for the prime $2$, and once for $3$.

If we account for this double counting, we can show that the density of relatively prime pairs is $$\frac{1}{\zeta(2)}.$$ See this question and answer for some more details.

• The brackets denote the floor function and what do you mean with $O(1)$? Thanks a lot, Eric. – YoAsakura Mar 8 '12 at 15:05
• @YoAsakura: Exactly, $[x]$ refers to the floor. By $O(1)$ I just mean something which is bounded by some constant. We can be more precise and write $[t]=t+\delta$ where $|\delta |<1$. – Eric Naslund Mar 8 '12 at 15:10