Results 1 to 7 of 7

Math Help - Two questions in class (mod 8)

  1. #1
    Member courteous's Avatar
    Joined
    Aug 2008
    From
    big slice of heaven
    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":

    • a_{even}=2k: a^2=(2k)^2=4(k^2)= \left\{ \begin{array}{ll}<br />
0\mod{8} & \mbox{; $k_{even}$}\\<br />
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
    Last edited by courteous; September 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 courteous's Avatar
    Joined
    Aug 2008
    From
    big slice of heaven
    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 courteous's Avatar
    Joined
    Aug 2008
    From
    big slice of heaven
    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 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.
    Last edited by TheCoffeeMachine; October 1st 2010 at 05:42 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member courteous's Avatar
    Joined
    Aug 2008
    From
    big slice of heaven
    Posts
    206
    Quote Originally Posted by TheCoffeeMachine View Post
    \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?
    Last edited by courteous; October 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: July 23rd 2010, 02:23 AM
  2. class help please!
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 12th 2010, 06:00 PM
  3. Replies: 6
    Last Post: December 5th 2009, 06:53 AM
  4. Replies: 2
    Last Post: October 5th 2009, 10:53 AM
  5. conjugacy class and class equation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 1st 2009, 06:52 PM

/mathhelpforum @mathhelpforum