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.


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.

  • $\begingroup$ The brackets denote the floor function and what do you mean with $ O(1) $? Thanks a lot, Eric. $\endgroup$ – YoAsakura Mar 8 '12 at 15:05
  • $\begingroup$ @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$. $\endgroup$ – Eric Naslund Mar 8 '12 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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