# Integer solutions (lattice points) to arbitrary circles

Wolfram Alpha will provide integer solutions to arbitrary circle equations. I'm trying to understand how it's able to calculate them, but despite a fair bit of digging I haven't found any discussion of how to get either the number of, or which, integer solutions to a given circle. Plenty of discussion of lattice points inside a circle, related to the Gauss circle problem, and some discussion of circles centered on the origin, but nothing for the general case.

Wolfram Alpha can quickly determine there are 12 integer solutions to the circle x^2-10 (x+y)+y^2+50 = 50 - how?

-
Someone should read through this paper, and figure out the exact ${\cal O}(\cdot)$ time complexity: Felipe Cucker Pascal Koiran and Steve Smale, A Polynomial Time Algorithm for Diophantine Equations in One Variable PDF file – user2468 Mar 25 '12 at 6:05
How did you get Wolfram alpha to provide integer solutions? – LarsH Oct 29 '13 at 16:22
@LarsH I just dropped in the equation and it provided them, see the link in my question. – dimo414 Oct 29 '13 at 17:42

As long as the coefficients of $x^2, \; y^2$ are $1$ and the coefficients of $x,y$ are even, this is quite easy. What you get by completing two squares is $$(x-5)^2 + (y-5)^2 = 50.$$ Fine, so define new variables, $$u = x-5, \; \; \; v = y - 5,$$ and count the (integer pair) solutions to $$u^2 + v^2 = 50.$$ For each pair, return by $x = u + 5, \; \; y = v + 5.$ It is easy enough to plot these.
However, what if you had some very large target number $n$ and had to count the number of integer pair solutions to $$u^2 + v^2 = n?$$ Well, if you can factor $n,$ you can make a complete list of all numbers that divide it, including $1$ and $n$ itself. Ignore the even divisors. Count the number of divisors that leave a remainder of 1 when divided by 4, call that count $C_1.$ Put another way, this is the count of $d > 0, \; \; d | n, \; \; d \equiv 1 \pmod 4.$ Next, count the number of divisors that leave a remainder of 3 when divided by 4, call that count $C_3.$ This is the count of $d > 0, \; \; d | n, \; \; d \equiv 3 \pmod 4.$ The number of integer lattice points on the circle is $$4 (C_1 - C_3).$$ For $n = 50,$ the divisors are $1,2,5,10,25,50.$ So $C_1 = 3$ and $C_3 = 0,$ and the number of integer points is $4 (3-0) = 4 \cdot 3 = 12.$
@Jyrki, this description is Theorem 65 on page 80 of Introduction to the Theory of Numbers by Leonard Eugene Dickson, (1929). Proper representations are Theorems 61 and 62 on page 76. I probably have more recent books that give the "excess of divisors" method. Dickson does some other forms with class number one in exercises on pages 80-81. Rather cute, in a footnote he points to his own 1911 proof that there are no extra discriminants of class number one to $-1,500,000.$ – Will Jagy Mar 25 '12 at 20:40