Determine if a positive integer is a sum of two positive squares Given a positive integer $N$, what is the best/most efficient way to determine if $N=x^2+y^2$ for some positive integers $x<y$? Only the decision is needed, not explicitly $x,y$.
 A: As shown in this answer, $n$ is the sum of two non-negative squares if and only if for each prime $p\equiv3\pmod4$, $p$ appears with even exponent in the factorization of $n$.
If the factorization of $n$ contains at least one prime $p\equiv1\pmod4$ with positive exponent, or $p=2$ with odd exponent, then $n$ can be written as the sum of two positive squares.
If the factorization of $n$ contains at least one prime $p\equiv1\pmod4$ with positive exponent, then $n$ can be written as the sum of two distinct positive squares.
A: Fermat's theorem (not that one) states that a prime $p$ is a sum of two squares if and only if $p=2$ or $p \equiv 1 \pmod{4}$. This extends to the rest of the integers using the relation
$$ (x^2+y^2)(z^2+w^2) = (xz-yw)^2+(xw+yz)^2. $$
Therefore any product of primes of the form $4k+1$ is also expressible as the sum of two squares. If $N$ contains prime factors of the form $4k+3$, they must occur to even powers (it is clear that even powers just merge into both squares). The hard part is proving that any integer with an odd power of a $4k+3$ is not thus expressible, but you'll find the proof in any number theory book.
So: find the prime factorisation of $N$, and look at the prime factors that are $3 \pmod{4}$. $N$ is a sum of two squares if and only if all such prime factors occur to even powers.
A: Fermat's Theorem says,

If $p$ is an odd prime and $x,y$ are integers numbers. $p=x^2+y^2$ iff $p≡1 \pmod 4$. 

