How to select the right modulus to prove that there do not exist integers $a$ and $b$ such that $a^2+b^2=1234567$?

Considering in mod $4$ is a good 'tool' in such a question just because we have for any integer $a$ $$a^2\equiv 0,1\pmod 4$$ as the author says. This fact is useful in this case just because $$a^2+b^2\not\equiv 3\pmod 4$$ $$1234567\equiv 3\pmod4.$$ Note that this works just because $1234567\equiv 3\pmod 4$.

P.S. Considering in mod $3,8,16$ is also useful.

I'll give you an example. In the following question, considering in mod $3$ may be the first choice (try, and you'll see why) :

Question : Find all positive integers $(n,x,y)$ such that $$y^2=x^n-x+2.$$ The answer is $(n,x,y)=(2m,2,2^m)$ for all positive integers $m$.

Considering in mod $3$ works because $y^2\equiv 0,1\pmod 3$.

Try mod 2. Doesn't work. Try mod 3. Doesn't work. Try mod 4. It works. Stop.