How to select the right modulus to prove that there do not exist integers $a$ and $b$ such that $a^2+b^2=1234567$? 
Example 19.2.6 Prove that there do not exist integers $a$ and $b$ such that $\left.a^{2}+b^{2}=1234567 \text { . [Problems IV, Question } 1\right]$
Solution The set of remainders modulo $4, R_{4},$ is $\{0,1,2,3\}$ and so working modulo 4 we have four possibilities to consider. From modular arithmetic,

\begin{array}{l}
a \equiv 0 \bmod 4 \Rightarrow a^{2} \equiv 0 \bmod 4 \\
a \equiv 1 \bmod 4 \Rightarrow a^{2} \equiv 1 \bmod 4 \\
a \equiv 2 \bmod 4 \Rightarrow a^{2} \equiv 4 \equiv 0 \bmod 4 \\
a \equiv 3 \bmod 4 \Rightarrow a^{2} \equiv 9 \equiv 1 \bmod 4
\end{array}

Thus for any $a \in \mathbb{Z}, a^{2} \equiv 0$ or 1 mod $4 .$ Therefore given two integers $a$ and $b$, $a^{2}+b^{2} \equiv 0$ or 1 or 2 mod $4,$ i.e. $a^{2}+b^{2} \neq 3$ mod 4
Suppose now for contradiction that $a$ and $b$ are integers such that $a^{2}+b^{2}=1234567 .$ Then, since $1234567 \equiv 3$ mod $4,$ we have $a^{2}+b^{2} \equiv$ 3 mod 4 giving the required contradiction. Hence such integers cannot exist.

I understand the solution but I don't know how the author decided to start with modulo 4 instead of something else? What is it about the expression $a^2+b^2=1234567$ that would trigger us to select modulo 4 instead of something else.
I tried to solve the question in a similar manner using modulo 2 but eventually got stuck. This leads me to believe that this question can only be solved using modulo 4. Is this true?
 A: 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$.
A: Try mod 2.  Doesn't work.  Try mod 3.  Doesn't work.  Try mod 4. It works.  Stop.
A: I would go along with others in the comments that $4$ is the obvious one to choose, since the basic theorems on sums of two squares depend on behaviour mod $4$. The only thing which using $8$ adds is that numbers of the form $8n+7$ cannot be written as the sum of fewer than four squares.
There is a theorem which tells us that $N$ can be written as a sum of two squares only if every prime factor of the form $4n+3$ appears to an even power in the factorisation. So if my first thought had been to try mod $4$, and this had failed, I would be looking to factorise the number into prime factors, or alternatively to spot an easy decomposition into two squares.
I can't see that trying another modulus would make any progress.
A: HINT:
$$1234567\equiv-1\pmod4\equiv3$$
and for any integer $a,a^2\equiv0,1\pmod4\implies a_1^2+a_2^2\equiv0,1,2\pmod4$
A: 
$\quad$ I don't know how the author decided to start with modulo $4$ instead of something else?

$\qquad\qquad\qquad\qquad$ 
$\qquad\qquad\qquad\qquad\quad$ Hope this picture will clarify all your questions...
