Today, I'll translate the proof for a theorem by André Schinzel that gives a circle with integer coordinates (also known as Lattice Points) on its circumference, for any given . The theorem was published in L'Enseignement Mathématique in 1958 and can be found here.
Lemma. For any non-negative integer , has integer solutions.
Proof: When decomposing number into the sum of two squares, it helps to use Gaussian Integers because it is equivalent to factoring . For instance, . So, . Lastly, for any ,
and . Since there are choices for and, for each , there are integer solutions. There must be at least integer solutions to the equation .
It is easy to check that any factoring of is of the form for some . Therefore, we exhausted all solutions and the equation has precisely solutions.
Schinzel's Theorem. For any given positive integer , there is a circle in the plane which has lattice points on its circumference. Particularly, this circle is an example of one solution:
Proof: Suppose . According to the lemma, the circle has lattice points. Since is odd, then only one of and is even. Restricting to be even discards half of the points. Therefore has lattice points.
Otherwise, let . The lemma implies has lattice points. Note that . So only one of and is a multiple of . The restriction discards half the points. Since there is also a bijection between solutions and , namely, , then the restriction discards half of the remaining points. Therefore has lattice points.
Fig 1. A Few Examples