Find all integer solutions for $x^2+y^2<a$

Question

How do I find all integer solutions for the inequality $x^2+y^2<a$, where $a$ is a known integer? I can try pairs of numbers to find solutions one by one, but what's a generalised, systematic way to find all solutions?

Answer 1

x$^2$ + y$^2$ = $r^2$ is the equation for a circle centered at (0,0), so simply take $\sqrt{a}$ as the radius of the circle. All possible solutions (x,y) are then given by the locus of points inside the circle.

Answer 2

Going from $=$ t0 $<$ complicates things but here is one approach. A general "formula" is $\quad (A=0\implies B\le\lfloor\sqrt{a}\rfloor-1)$ $\qquad (B=0\implies A\le\lfloor\sqrt{a}\rfloor-1) $

For $A^2+B^2=C^2\quad A\space $ takes the form $\space (2n+1),\space $ B takes the form $\space 4n,\space $ and $\space C\space $ takes the form $\space 4n+1\space $ where $\space n\in\mathbb{N}\quad$ but we will not use this form.

We can derive functions from Euclid's formula that will help find our solutions. The formula is $$A=m^2-n^2\qquad B=2mn\qquad C=m^2+n^2$$

But our modified form will be $$A=m^2-n^2\qquad B=2mn\qquad \sqrt{a}=C>m^2+n^2$$ Solving for $\space n \space$ we get $\qquad n<\sqrt{C-m^2}\quad\text{for}\quad m\le\sqrt{C-1}$

We can now try values of $m$ within within the limits to find which, if any yield integers. For example $$C=65\implies m \le \sqrt {65-1}=8$$

If we now plug $(m,n)$ back into the AB fuctions of Euclid's formula, we get the largest combinations of AB with squares that sum up to $\space a=C^2\space$ and we can know that anything less of either A or B will satisfy the equation. Here is the combination of $(m,n,A,B)$ that shows the largest $A$-value that qualifies: $\quad (8,1,63,16)\quad$

$$\text{So, for}\quad a=65^2,\\ A\{63,62,61,\cdots\}\implies B\in\{15,14,13,\cdots\}\\ \land\quad\\ A\{16,15,14,\cdots\}\implies B\in\{62,61,60,\cdots\}$$

Note: $n=1$ always yields the largest $A$-value for a given $m$-value and $n=m-1$ yields the larges $B$-value. It is simply easier to reverse AB for the high-limits here.