4
$\begingroup$

Already did something like that to prove the square of an even number Always leaves remainder $1$ when divided by $8$, in which I used induction to arrive at the result.

However, I don't know how to use induction to suppose that it does not leave a remainder $3$, and then prove it.

Could somebody help me?

$\endgroup$
  • $\begingroup$ For what it's worth, I think it's much easier to prove just using the arithmetic of congruences. If $a$ and $b$ have the same parity, then $a^2 + b^2 \equiv 0 + 0$ or $1 + 1 \pmod 4$. If they have different parities, then you've got $1 + 0 \pmod 4$. $\endgroup$ – Robert Soupe May 30 '15 at 3:23
  • $\begingroup$ As I reread your question, I'm not sure if you understand what induction is, if maybe you're getting it kind of mixed up with proof by contradiction (in which you would start by assuming that it does produce such a reminder). $\endgroup$ – Robert Soupe May 30 '15 at 3:26
11
$\begingroup$

HINT:

As integer $c\equiv0,1,2,3\pmod 4;c^2\equiv0,1$

So what are possible values of $a^2+b^2\pmod4$ where $a,b$ are any integers?

$\endgroup$
4
$\begingroup$

Some simple problems are just too much fun to pass up!

Lauds to lab bhattacharee for presenting the more or less standard approach, which essentially stands on the homomorphism $\pi: \Bbb Z \to \Bbb Z/4 \Bbb Z$ mapping any $n \in \Bbb Z$ to the coset $\bar n = n + 4\Bbb Z$. Of course the technique works by virtue of the fact the $\pi$ preserves sums and products, and the fact that $c^2 = 0, 1$ for $c \in \Bbb Z/4\Bbb Z$.

Here's the way I used to solve these things back in junior high school, before I knew much about commutative rings, homomorphisms, $\Bbb Z / n\Bbb Z$ and the like:

Three cases:

$a, b \; \text{both even}; \tag{1}$

$a, \; \text{even}, \; b \; \text{odd}; \tag{2}$

$a, b \; \text{both odd}; \tag{3}$

of course (2) covers the case $a$ odd, $b$ even as well. Then for (1) we write

$a = 2n, b = 2m; \; m, n \in \Bbb Z, \tag{4}$

whence

$a^2 = 4n^2, b^2 = 4m^2, \tag{5}$

whence

$a^2 + b^2 = 4(n^2 + m^2); \tag{6}$

in case (2):

$a = 2n + 1, b = 2m, \tag{7}$

whence

$a^2 = 4n^2 + 4n + 1, b = 4m^2, \tag{8}$

whence

$a^2 + b^2 = 4(n^2 + m^2 + n) + 1; \tag{9}$

case (3):

$a = 2n + 1, b = 2m + 1, \tag{10}$

whence

$a^2 = 4n^2 + 4n + 1, b^2 = 4m^2 + 4m + 1, \tag{11}$

whence

$a^2 + b^2 = 4(n^2 + m^2 + n + m) + 2; \tag{12}$

we thus see that the remainders upon dividing $a^2 + b^2$ by $4$ must always lie in the set $\{0, 1, 2 \}$. QED!!!

Now that is what I call truly elementary number theory!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.