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..

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. 
