Answering a flawed Mathletes question (finding $x^2 + y^2 = p$ given $p$ for large $p$) There was a mathletes meet today (high school) and this was one of the questions:
"-Some background on Fermat's 4k+1 sum of square theorem- One such prime is $367369$. What integers $x, y$ satisfy $x^2 + y^2 = 367369$?"
Is there any way to have done this problem otherwise without just massive guess and check (and luck)? (Note that the time constraint is $10$ minutes for $2$ problems). If you're wondering, the correct answer was $\{420, 437\}$.
So, any ideas? Personally I think the guy just forgot to give us some information..
 A: You can reduce the amount of casework by working modulo small powers of primes and seeing what constraints that puts on $x, y$ (then combining them using the chinese remainder theorem). For example, 


*

*$367369 \equiv 1 \bmod 8$, and using the fact that $x^2 \equiv 0, 1, 4 \bmod 8$ it follows that exactly one of $x$ or $y$ must be divisible by $4$ and the other one must be odd. 

*$367369 \equiv 1 \bmod 3$, and using the fact that $x^2 \equiv 0, 1 \bmod 3$ it follows that exactly one of $x$ or $y$ must be divisible by $3$. 

*$367369 \equiv 4 \bmod 5$, and using the fact that $x^2 \equiv 0, 1, 4 \bmod 5$ it follows that exactly one of $x$ or $y$ must be divisible by $5$ and the other one must be congruent to $2, 3 \bmod 5$. 


This gets you some information $\bmod 4 \cdot 3 \cdot 5 = 60$, although unfortunately you don't know which of $x$ or $y$ satisfy the conditions above so you do still need to break into several cases. The easiest case to handle is the case where, say, $x$ satisfies all of the divisibility constraints, so if you assume $x$ is divisible by $60$ then you would only need to check the cases $x = 0, 60, 120, ..., 480$ as nayrb explained in the comments. Moreover, since $367369$ is fairly large it's a good idea to check the largest possibilities first, so checking $x = 480$ and then $x = 420$ would've finished the problem. 
