# Two questions in class (mod 8)

• Sep 30th 2010, 10:50 PM
courteous
Two questions in class (mod 8)
Warm-up exercise:
Quote:

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

• $\displaystyle a_{even}=2k$: $\displaystyle 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.$
$\displaystyle a_{odd}=2k-1$: $\displaystyle 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)

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

Quote:

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 $\displaystyle n_0\equiv (2k_{even})^2\text{, } n_1\equiv (2k+1)^2\text{ , }n_2\equiv (2k_{odd})^2$ and $\displaystyle (n_x,n_x,n_x)$ be a sum of 3 squares.

Then just write all possible combinations?
$\displaystyle (n_0,n_0,n_0)\equiv 0 \mod{8}$
$\displaystyle (n_0,n_0,n_1)\equiv 1 \mod{8}$
$\displaystyle (n_0,n_1,n_1)\equiv 2 \mod{8}$
$\displaystyle \vdots$
$\displaystyle (n_1,n_2,n_2)\equiv 1 \mod{8}$
$\displaystyle (n_2,n_2,n_2)\equiv 4 \mod{8}\square$
• Oct 1st 2010, 01:13 AM
HappyJoe
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.
• Oct 1st 2010, 02:47 AM
courteous
Quote:

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?
• Oct 1st 2010, 03:04 AM
HappyJoe
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.
• Oct 1st 2010, 03:15 AM
courteous
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?
• Oct 1st 2010, 04:45 AM
TheCoffeeMachine
Let the perfect square be $\displaystyle n$. Then $\displaystyle n = a^2$ for some $\displaystyle a \in\mathbb{Z}$ and $\displaystyle \frac{a}{8} = q+\frac{r}{8} \Rightarrow a = 8q+r$.
Thus $\displaystyle n = (8q+r)^2 = 64q^2+16qr+r^2$, $\displaystyle 0\le r < 8$. If $\displaystyle r = 0$, then $\displaystyle n =8(8q^2)+0$,
if $\displaystyle r = 1$, then $\displaystyle n = 8(8q^2+2q)+1$, if $\displaystyle r = 2$, then $\displaystyle 8(8q^2+4q)+4$, if $\displaystyle r = 3$, then
$\displaystyle n=8(8q^2+6q+1)+1$, if $\displaystyle r = 4$, then $\displaystyle n = 8(8q^2+16q+8)+0$, if $\displaystyle r = 5$, then
$\displaystyle n = 8(16q^2+10q+3)+1$, if $\displaystyle r = 6$, then $\displaystyle n = 8(8q^2+12q+4)+4$, if $\displaystyle r = 7$, then
$\displaystyle n = 8(8q^2+14q+6)+1$. Thus $\displaystyle n$ always leaves a remainder of $\displaystyle 0$, $\displaystyle 1$, or $\displaystyle 4$ upon division by $\displaystyle 8$.
• Oct 1st 2010, 05:39 AM
courteous
Quote:

Originally Posted by TheCoffeeMachine
$\displaystyle \frac{a}{8} = q+\frac{r}{8} \Rightarrow a = 8q+r$

Why you wrote it that way ... why not just $\displaystyle 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: $\displaystyle 0^2\equiv 0 \mod{8} \text{ }\ldots\text{ } 7^2\equiv 1 \mod{8}$?

Can someone also help with the 2nd exercise? (Smirk)