>>14151402Say you want to figure out which primes cannot be written as a sum of two squares.
That would be the primes that are 3 mod 4. And the proof is simple:
Squares mod 4 are either 0 or 1. You sum any two of these, and you can only get 0, 1, or 2, but no 3.
So any prime (and any integer) that is 3 mod 4 cannot be written as a sum of two squares.
The converse is also true, but is much harder.
Th problem was about sums of squares, but modular arithmetic naturally came up.
