$(x,y)$ pairs in lattice $Z^2$ that are co-prime with euclidean-norm at most $k$

35 Views Asked by At

Let $B(k) = \{(x,y)\in Z^2 ~|~ x^2+y^2\leq k^2\}$, where $Z$ is the set of integers.

It is quite straight forward to show that $|B(k)|$ is $\Theta(k^2)$.

My question is whether the number of co-prime pairs $(x,y)$ in $B(k)$ also $\Theta(k^2)$, or whether it is asymptotically smaller than $k^2$?

1

There are 1 best solutions below

4
On BEST ANSWER

This is the Primitive Circle Problem, the asymptotics are still $\Theta(k^2)$ (and the constant is known to be $6/\pi$).