Finding Integer Points on a Circle

I got interested in the following problem: Given a positive integer $n$,

$$ x^2 + y^2 = n $$

defines a circle on the plane. The question is: are there integer points (i.e. points whose $x$-and-$y$ coordinates both are integers) lying on this circle?

This problem seems difficult to solve analytically, so I wrote the following R code to explore:

chk_sq <- function(x)
{floor(sqrt(x))^2 == x
}

find_integer_points <- function(n)
{r <- floor(sqrt(n))
 x <- 0:r
 y_sq <- n - x^2
 the_index <- which(chk_sq(y_sq))
 
 the_x <- x[the_index]
 if(length(the_x) == 0) {
   return(sprintf("There are no integer points on x^2+y^2=%d!", n))}
 
 the_y <- floor(sqrt(y_sq[the_index]))
 df <- data.frame(x = the_x,
                  y = the_y)
 return(df)
}

(re <- find_integer_points(2024))

## [1] "There are no integer points on x^2+y^2=2024!"

(re <- find_integer_points(2025))

##    x  y
## 1  0 45
## 2 27 36
## 3 36 27
## 4 45  0

(re <- find_integer_points(2026))

##    x  y
## 1  1 45
## 2 45  1

(re <- find_integer_points(2027))

## [1] "There are no integer points on x^2+y^2=2027!"

Afterward, I searched online and found two references:

• Ref 1 (https://faculty.etsu.edu/gardnerr/3120/notes-Dudley/Dudley-Section-18.pdf)

• Ref 2 (https://faculty.etsu.edu/gardnerr/3120/Beamer-Dudley/Proofs-Dudley-18-print.pdf)

The main result in both references is the following:

Theorem 18.1. Integer $n$ cannot be written as the sum of two squares if and only if the prime-power decomposition of $n$ contains a prime congruent to 3 (mod 4) to an odd power.