3
$\begingroup$

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 Answers 1

4

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.

  • 0
    @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.2012-03-08