Results 1 to 7 of 7

Thread: Two questions in class (mod 8)

  1. #1
    Member
    Joined
    Aug 2008
    From
    nowhere
    Posts
    206

    Question 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":

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

    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$
    Last edited by courteous; Sep 30th 2010 at 11:07 PM. Reason: no need for variations, combinations suffice
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member HappyJoe's Avatar
    Joined
    Sep 2010
    From
    Denmark
    Posts
    234
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    From
    nowhere
    Posts
    206
    Quote Originally Posted by HappyJoe View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member HappyJoe's Avatar
    Joined
    Sep 2010
    From
    Denmark
    Posts
    234
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2008
    From
    nowhere
    Posts
    206
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2010
    Posts
    715
    Thanks
    2
    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$.
    Last edited by TheCoffeeMachine; Oct 1st 2010 at 05:42 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2008
    From
    nowhere
    Posts
    206
    Quote Originally Posted by TheCoffeeMachine View Post
    $\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?
    Last edited by courteous; Oct 3rd 2010 at 02:21 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Questions about Class
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Jul 23rd 2010, 02:23 AM
  2. class help please!
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jan 12th 2010, 06:00 PM
  3. Replies: 6
    Last Post: Dec 5th 2009, 06:53 AM
  4. Replies: 2
    Last Post: Oct 5th 2009, 10:53 AM
  5. conjugacy class and class equation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Mar 1st 2009, 06:52 PM

/mathhelpforum @mathhelpforum