# Thread: Two questions in class (mod 8)

1. ## Two questions in class (mod 8)

Warm-up exercise:
Show that any square leaves remainder 0, 1 or 4 on division by 8.
Which is better "proof":

• $a_{even}=2k$: $a^2=(2k)^2=4(k^2)= \left\{ \begin{array}{ll}
0\mod{8} & \mbox{; k_{even}}\\
4\mod{8} & \mbox{; k_{odd}}\end{array} \right.$

$a_{odd}=2k-1$: $a^2=(2k-1)^2=4(k^2-k)+1=1\mod{8}\text{ ; } k_{even} \text{ or } k_{odd} \square$

or to write all possible cases in (mod 8) class (as undefined helped me here)

• $0^2\equiv 0 \mod{8}$
$1^2\equiv 1 \mod{8}$
$\vdots$
$7^2\equiv 1 \mod{8}\square$

Deduce that a sum of 3 squares leaves remainder 0, 1, 2, 3, 4, 5, or 6 on division by 8.
"Obvious" from 1st exercise, but how to write a proof?

Let $n_0\equiv (2k_{even})^2\text{, } n_1\equiv (2k+1)^2\text{ , }n_2\equiv (2k_{odd})^2$ and $(n_x,n_x,n_x)$ be a sum of 3 squares.

Then just write all possible combinations?
$(n_0,n_0,n_0)\equiv 0 \mod{8}$
$(n_0,n_0,n_1)\equiv 1 \mod{8}$
$(n_0,n_1,n_1)\equiv 2 \mod{8}$
$\vdots$
$(n_1,n_2,n_2)\equiv 1 \mod{8}$
$(n_2,n_2,n_2)\equiv 4 \mod{8}\square$

2. I prefer your first proof. It gives the reason why the remainder is 0, 1 or 4, as opposed to listing all the squares, which gives you no real mathematical insight.

For the second question, note that you cannot possibly write 7 as a sum of three terms chosen (possibly with repetitions) from the set {0,1,4} (doing it mod 8). Thus the remainder must be 0, 1, 2, 3, 4, 5 or 6.

3. Originally Posted by HappyJoe
For the second question, note that you cannot possibly write 7 as a sum of three terms chosen (possibly with repetitions) from the set {0,1,4} (doing it mod 8). Thus the remainder must be 0, 1, 2, 3, 4, 5 or 6.
I would put this under the word "Obvious". How do you write a proof that would "hold water", say, for a math professor?

4. To see it can't be 7, I would argue like: If none of the chosen numbers are 4, then the sum will be at most 3 (occuring for 1, 1 and 1). If exactly one of the three chosen numbers were 4, then the sum would be at most 6 (4, 1 and 1). With two 4's, the remainder would be either 0 or 1 (0,4,4 and 1,4,4), and with three 4's, the remainder would be 4.

5. I agree, but is there more concise way to prove it? I mean, were you to publish this, how would you write it out as a proof? I'm really asking what are mathematicians' customs in writing out a proof?

6. Let the perfect square be $n$. Then $n = a^2$ for some $a \in\mathbb{Z}$ and $\frac{a}{8} = q+\frac{r}{8} \Rightarrow a = 8q+r$.
Thus $n = (8q+r)^2 = 64q^2+16qr+r^2$, $0\le r < 8$. If $r = 0$, then $n =8(8q^2)+0$,
if $r = 1$, then $n = 8(8q^2+2q)+1$, if $r = 2$, then $8(8q^2+4q)+4$, if $r = 3$, then
$n=8(8q^2+6q+1)+1$, if $r = 4$, then $n = 8(8q^2+16q+8)+0$, if $r = 5$, then
$n = 8(16q^2+10q+3)+1$, if $r = 6$, then $n = 8(8q^2+12q+4)+4$, if $r = 7$, then
$n = 8(8q^2+14q+6)+1$. Thus $n$ always leaves a remainder of $0$, $1$, or $4$ upon division by $8$.

7. Originally Posted by TheCoffeeMachine
$\frac{a}{8} = q+\frac{r}{8} \Rightarrow a = 8q+r$
Why you wrote it that way ... why not just $a = 8q+r$?

Anyway, as you took up 1st exercise, I assume that my two "proofs" in 1st post aren't of sufficient quality? How is this different from just writing all possible cases: $0^2\equiv 0 \mod{8} \text{ }\ldots\text{ } 7^2\equiv 1 \mod{8}$?

Can someone also help with the 2nd exercise?