# 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.$

• Why does this work? – user7530 Mar 25 '12 at 6:57
• @user7530: See the answers to this question for more discussion. – Jyrki Lahtonen Mar 25 '12 at 7:36
• @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
• @WillJagy, thanks for the reference. I really should get my hands on a copy of that book :-). I've seen, e.g. Carlitz refer to it on at least couple occasions. I recently spent some time on a cute but not deep problem. Found a reference from 70s, another from the late 50s. Then in a paper Carlitz says that the result is an exercise (!) in Dickson's book :-) – Jyrki Lahtonen Mar 25 '12 at 21:31
• @Jyrki, I sent you an email with a place to buy the Dickson book. – Will Jagy Mar 26 '12 at 0:06