Number of points with integer co-ordinates inside $x^2+y^2=36$

Question

Question:

Find the number of points with integer co-ordinates that lie inside the circle: $$x^2+y^2=36$$

My Approach:

I drew the figure and counted!
I counted the number of points inside the $1^{st}$ quadrant and multiplied that by $4$.
After that I moved on to count the points on the axes.
Finally I was able to get the correct answer ($109$).

Is there a better way to solve these kind of questions?
Counting seems way too basic and time consuming.

Answer 1

Here is a an slightly advanced way how to solve this problem. For any $n\in \mathbb{N}$ one can consider $r(n):=|\{(x,y)\in \mathbb{Z}^2: x^2+y^2=n\}|$. One can show that $r(n)=4\rho(n)$, where $\rho(n)=\sum \limits_{d\mid n}\chi_4(d)$, where $\chi_4$ is a non-principal character $\text{mod}\ 4$, i.e. $\chi_4(d)=\sin \dfrac{\pi d}{2}$.

Easy to see that $$|\{(x,y)\in \mathbb{Z}^2: x^2+y^2\leq 36\}|=1+4\sum \limits_{n=1}^{36}\sum \limits_{d\mid n}\sin \dfrac{\pi d}{2}=$$ $$=1+4\sum \limits_{d=1}^{36}\sin \frac{\pi d}{2}\sum\limits_{1\leq n\leq 36, d\mid n}1=$$ $$=1+4\sum \limits_{d=1}^{36}\sin \frac{\pi d}{2}\left\lfloor \frac{36}{d}\right\rfloor=$$ $$=1+4\sum \limits_{k=0}^{17}(-1)^{k}\left\lfloor \frac{36}{2k+1}\right\rfloor=$$ $$=1+4\left(\left\lfloor \frac{36}{1}\right\rfloor+\left\lfloor \frac{36}{5}\right\rfloor+\dots+\left\lfloor \frac{36}{33}\right\rfloor\right)-$$ $$-4\left(\left\lfloor \frac{36}{3}\right\rfloor+\left\lfloor \frac{36}{7}\right\rfloor+\dots+\left\lfloor \frac{36}{35}\right\rfloor\right)=$$ $$=1+4(36+19)-4\cdot 27=113.$$

So the correct answer is actually $113$.

Answer 2

Hint:Well According to theorem of Pythagorean triplets, the only positive integer solution of the equation $$x^2+y^2=z^2$$ with $\gcd(x,y,z)=1$ is $$x=a^2-b^2, y=2ab$$ and $$z=a^2+b^2$$ where $\gcd(a,b)=1$ with the fact that we can interchage the role of $(x,y)$. So Positive integer and Negative integers will be found like this with some extension of $\gcd$. Others can be found trivillay by plugging $0$.

Remark:For Interior integer points you need to do find the solutions of $x^2+y^2=m^2$ for all integer $m<6$ to find it on circumference you nedd $m=6$ and all such solution can be found from above hint.

This is a Case Study Approach!!! Infact this tells you much more that is you can locate every coordinate inside the circle with integer coordinate value.

Answer 3

Sure...

To be "inside" is to have $x^2 + y^2 \le 36$. if $x$ an integer $-6 \le x \le 6$ then we have $|y| \le \sqrt {36 - x^2}$ and the number of such natural (strictly positive) numbers for which $y$ can be is $\lfloor\sqrt{36 -x^2}\rfloor$.

Let's figure than for $x = 0,.... 6$. then if $L_x = \lfloor\sqrt{36 -x^2}\rfloor =$ we have:

$L(0) = [\sqrt 36]=6; L(1) = [\sqrt 35] = 5; L(2) = [\sqrt 32]=5; L(3)= [\sqrt 27]=5; L(4)=[\sqrt{20}]=4; L(5)=\sqrt {11}=3; L(6)=\sqrt{0} = 0$.

If we allow that $y$ can be postive, or negative, or zero, then for $x$ the number of possible values we $|y| \le \sqrt{36 -x^2}$ would be $2L(x) + 1$.

So we have to do $\sum_{x=-6}^6 (2L(x) + 1)$.

And if $(x,y); x > 0$ is in the circle then $(-x,y)$ is in the circle as well so clearly $L(-x) = L(x)$. So

$\sum_{x=-6}^6 (2L(x) + 1)=$

$\sum_{x=-6}^{-1}(2L(x) + 1) + (2L(0) + 1) + \sum_{x=1}^6 (2L(x) + 1)=$

$(2L(0) + 1) + 2\times (\sum_{x=1}^6(2L(x) + 1)=$

$(2L(0) + 1) + 2\times( 2\sum_{x=1}^6 L(x) + \sum_{x=1}^6 1) =$

$(2L(0) + 1) + 4\times \sum_{x=1}^6 L(x) + 2\times 6 =$

$(2\times 6 + 1) + 4(5+5+5+4+3+0) + 12=$

$13 + 4(22) + 12 =$

$13 + 88 + 12 = 113$

Answer 4

Theorem 65, page 80, in Introduction to the Theory of Numbers by Leonard Eugene Dickson: the number of all representations of $2^k m$ (where $m$ is positive and odd) by $x^2 + y^2 $ is $4E,$ where $E$ (for excess) is the count of divisors of $m$ that are $1 \pmod 4$ minus the count of those $3 \pmod 4.$ Due to Jacobi...Evidently if $E$ comes out negative we just put zero.

I see, should add a column for cumulative sum..

Also, Jacobi's theorem does not say anything about $0$ which has just one representation, so we need to add $1$ to count all lattice points inside a circle.

$$ \begin{array}{c|c|c} 0&1&1 \\ 1&4&5 \\ 2&4&9\\ 3& 0&9\\ 4&4&13\\ 5&8&21\\ 6&0&21\\ 7&0&21\\ 8&4&25\\ 9&4&29\\ 10&8&37\\ 11&0&37\\ 12&0&37\\ 13&8&45\\ 14&0&45\\ 15&0&45\\ 16&4&49\\ 17&8&57\\ 18&4&61\\ 19&0&61\\ 20&8&69\\ 21&0&69\\ 22&0&69\\ 23&0&69\\ 24&0&69\\ 25&12&81\\ 26&8&89\\ 27&0&89\\ 28&0&89\\ 29&8&97\\ 30&0&97\\ 31&0&97\\ 32&4&101\\ 33&0&101\\ 34&8&109\\ 35&0&109\\ 36&4&113\\ \end{array} $$

For strictly inside 36 we get 109, but if we are including 36 it becomes 113.

Answer 5

Gauss circle problem: This link was provided by DietrichBurde in the comments below the question. The OP found it to be really helpful (realizing it a bit late).
Also note that the answer already provided by WillJagy and ZFR (kindly upvote their answer posts if you find this helpful) essentially employ the same ease of computation (and even the same expression is in play but in a different disguise) as one would do while solving the below expression but the below expression itself is more easier to understand/employ as it is a bit more "straight-forward". Citing the relevant parts from that link:

---

Consider a circle in $\Bbb R^2$ with center at the origin and radius $r\geq0$. Gauss's circle problem asks how many points there are inside this circle of the form $(m,n)$ where $m$ and $n$ are both integers. Since the equation of this circle is given in Cartesian coordinates by $x^2+y^2=r^2$ , the question is equivalently asking how many pairs of integers $m$ and $n$ there are such that $$m^2+n^2\leq r^2$$ If the answer for a given $r$ is denoted by $N(r)$ then the value of $N(r)$ can be given by several series. In terms of a sum involving the floor function it can be expressed as: $$N(r)=1+4\sum_{i=0}^{\infty}\left(\left\lfloor\frac{r^2}{4i+1}\right\rfloor-\left\lfloor\frac{r^2}{4i+3}\right\rfloor\right)$$

This is a consequence of Jacobi's two-square theorem, which follows almost immediately from the Jacobi triple product.