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

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+b2=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?

• Perhaps it is because the only non-zero quadratic residue modulo $4$ is $1$. Another good candidate would be $8$, and $16$ as well. – Yiyuan Lee Oct 10 '14 at 10:20
• This is just a question of knowing the problem type, I think (sums of squares). My first thought on reading the title was "Try $4$ first, and if that doesn't work, try $8$." – TonyK Oct 10 '14 at 10:22

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

• did you choose mod 3 because the expression has 3 unknown terms and could you please direct me to some sites that show how to solve such problems? I've only started reading about modular arithmetic and have never come across such problems – mauna Oct 11 '14 at 3:40
• @mauna: No. If $x\equiv 0,1\pmod 3$, then the RHS$\equiv 2$, which is a contradiction. So, we have $x\equiv 2$, and so on. sorry, but I don't know such sites. How about using google? – mathlove Oct 11 '14 at 10:39

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

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.

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$

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