Find all positive integers $x$ such that $13 \mid (x^2 + 1)$ I was able to solve this by hand to get $x = 5$ and $x =8$. I didn't know if there were more solutions, so I just verified it by WolframAlpha. I set up the congruence relation $x^2 \equiv -1 \mod13$ and just literally just multiplied out. This lead me to two questions:


*

*But I was wondering how would I do this if the $x$'s were really large? It doesn't seem like multiplying out by hand could be the only possible method.

*Further, what if there were 15 or 100 of these $x$'s? How do I know when to stop?

We can do this avoiding the congruence machinery,although it is essentially
the same idea. Let x = 13a + b, where 0<=b<=12.
Then x^2 +1 = 169a^2 + 26ab + b^2 +1.You only need to find values of b such
that b^2 + 1 is divisible by 13.This is a very small sample,as you found that
b = 5 or b =8.Then x =13a +5 or x = 13a +8,and you have infinitely many answers.
Edwin Gray
