Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 5 of 5
  1. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,815
    Thanks
    3,029 times
    Thanked
    995 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #1
    Hey!!

    We define the set $M:=\{x^2\mid x\in\mathbb{Z}\}$.

    1. Give 8 different elements of M.
    2. Give for each element of question 1, m, two numbers $q\in \mathbb{Z}, r\in \{0,1,\ldots , 7\}$ such that $m=8q+r$.
    3. Show that for all $x\in M$ one of the following holds:
      $x\overset{(8)}{\equiv}0$, $x\overset{(8)}{\equiv}1$, $x\overset{(8)}{\equiv}4$



    I have done the following:
    1. We have $1^2=1, 2^2=4, 3^2=9, 4^2=16, 5^2=25, 6^2=36, 7^2=49, 8^2=64$.
    2. $1=8\cdot 0+1, 4=8\cdot 0+4, 9=8\cdot 1+1, 16=8\cdot 2+0, 25=8\cdot 3+1, 36=8\cdot 4+4, 49=8\cdot 6+1, 64=8\cdot 8+0$
    3. How can we show that?

  2. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

  3. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Online
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,405
    Thanks
    5,437 times
    Thanked
    14,620 times
    Thank/Post
    1.739
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #2
    Quote Originally Posted by mathmari View Post
    We define the set $M:=\{x^2\mid x\in\mathbb{Z}\}$.

    3. Show that for all $x\in M$ one of the following holds: $x\overset{(8)}{\equiv}0$, $x\overset{(8)}{\equiv}1$, $x\overset{(8)}{\equiv}4$
    Hey mathmari!!

    If $x\in M$, then there must be a $y\in\mathbb Z$ such that $x=y^2$ yes?

    In question 2 we can see there seems to be a repeating pattern, don't we?
    The remainers modulo 8 for consecutive values of $y$ are 1,4,1,0,1,4,1,0 after all.
    That seem to be periodic with period 4, doesn't it?

    Suppose we write $y=4k+r$ for some integer $k$ and $r\in\{0,1,2,3\}$.
    What will be the possibilities for $y^2\pmod 8$?

  4. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,815
    Thanks
    3,029 times
    Thanked
    995 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #3 Thread Author
    Quote Originally Posted by Klaas van Aarsen View Post
    Suppose we write $y=4k+r$ for some integer $k$ and $r\in\{0,1,2,3\}$.
    What will be the possibilities for $y^2\pmod 8$?
    Why do we take the y in this form? Because it is periodic of period 4?

    The square is as follows:
    $$y^2\mod 8\equiv 16k^2+8kr+r^2\mod 8\equiv r^2$$

    The possible values of $r^2$ are $0,1,4,9=1$.
    Last edited by mathmari; February 6th, 2020 at 12:57.

  5. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Online
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,405
    Thanks
    5,437 times
    Thanked
    14,620 times
    Thank/Post
    1.739
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #4
    Quote Originally Posted by mathmari View Post
    Why do we take the y in this form? Because it is periodic of period 4?
    Yep.
    It seems to be periodic with period 4, so we try to prove that it is indeed the case. And additionally what the possible remainders are.

    Quote Originally Posted by mathmari View Post
    The square is as follows:
    $$y^2\mod 8\equiv 16k^2+8kr+r^2\mod 8\equiv r^2$$

    The possible values of $r^2$ are $0,1,4,9=1$.
    So?

  6. MHB Master
    MHB Math Helper

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    1,104
    Thanks
    319 times
    Thanked
    1,099 time
    #5
    Quote Originally Posted by mathmari View Post
    Hey!!

    We define the set $M:=\{x^2\mid x\in\mathbb{Z}\}$.

    1. Give 8 different elements of M.
    2. Give for each element of question 1, m, two numbers $q\in \mathbb{Z}, r\in \{0,1,\ldots , 7\}$ such that $m=8q+r$.
    3. Show that for all $x\in M$ one of the following holds:
      $x\overset{(8)}{\equiv}0$, $x\overset{(8)}{\equiv}1$, $x\overset{(8)}{\equiv}4$



    I have done the following:
    1. We have $1^2=1, 2^2=4, 3^2=9, 4^2=16, 5^2=25, 6^2=36, 7^2=49, 8^2=64$.
    2. $1=8\cdot 0+1, 4=8\cdot 0+4, 9=8\cdot 1+1, 16=8\cdot 2+0, 25=8\cdot 3+1, 36=8\cdot 4+4, 49=8\cdot 6+1, 64=8\cdot 8+0$
    3. How can we show that?
    Look at your answers to (2)! Each has 8 times some number plus 1, 4, 1, 0, 1, 4, 1, 0.

Similar Threads

  1. System of congruences, not relatively prime moduli
    By evinda in forum Number Theory
    Replies: 2
    Last Post: October 16th, 2018, 04:38
  2. Does this hold?
    By mathmari in forum Calculus
    Replies: 3
    Last Post: October 7th, 2015, 19:44
  3. Congruences - Rotman - Proposition 1.58
    By Peter in forum Linear and Abstract Algebra
    Replies: 2
    Last Post: July 13th, 2015, 21:29
  4. Congruences - Rotman - Proposition 1.58 - Second Question
    By Peter in forum Linear and Abstract Algebra
    Replies: 1
    Last Post: July 12th, 2015, 05:47
  5. system of congruences with no solution
    By vincentvance in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 4
    Last Post: May 23rd, 2015, 12:04

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards