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

Question

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?

Answer 1

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

Answer 2

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$

Answer 3

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.

Answer 4

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

Answer 5

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