Results 1 to 6 of 6

Thread: Modular math

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    Modular math

    This is a quick question on Modular Math:

    How can I prove that n = 1 (mod 4) IFF n = 1 (mod 8) or n = 5 (mod 8) ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by 1337h4x View Post
    This is a quick question on Modular Math:

    How can I prove that n = 1 (mod 4) IFF n = 1 (mod 8) or n = 5 (mod 8) ?

    $\displaystyle n=1\!\!\!\pmod 4\Longrightarrow n$ is odd, so it must be $\displaystyle n=1,3,5\,\,or\,\,7\!\!\!\pmod 8$, but $\displaystyle n=3\!\!\!\pmod 8\Longrightarrow n=3\!\!\!\pmod 4$...with 7 is similar.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by tonio View Post
    $\displaystyle n=1\!\!\!\pmod 4\Longrightarrow n$ is odd, so it must be $\displaystyle n=1,3,5\,\,or\,\,7\!\!\!\pmod 8$, but $\displaystyle n=3\!\!\!\pmod 8\Longrightarrow n=3\!\!\!\pmod 4$...with 7 is similar.

    Tonio

    Can you explain this part:

    $\displaystyle n=1,3,5\,\,or\,\,7\!\!\!\pmod 8$, but $\displaystyle n=3\!\!\!\pmod 8\Longrightarrow n=3\!\!\!\pmod 4$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by 1337h4x View Post
    Can you explain this part:

    $\displaystyle n=1,3,5\,\,or\,\,7\!\!\!\pmod 8$, but $\displaystyle n=3\!\!\!\pmod 8\Longrightarrow n=3\!\!\!\pmod 4$

    $\displaystyle n=3\!\!\!\pmod 8\Longrightarrow n=3+8k=3+(2k)4\Longrightarrow n=3\!\!\!\pmod 4$

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    Posts
    1,036
    Thanks
    272
    Quote Originally Posted by 1337h4x View Post
    This is a quick question on Modular Math:

    How can I prove that n = 1 (mod 4) IFF n = 1 (mod 8) or n = 5 (mod 8) ?
    By the definition of congruence, $\displaystyle n\equiv{1}\ (\text{mod }4)$ means 4 divides n-1. Since $\displaystyle \frac{n-1}{4}$ is an integer, it must be odd or even. So $\displaystyle \frac{n-1}{4}=2m\text{ or }2m+1$, where m is an integer. Solving both for m gives $\displaystyle m=\frac{n-1}{8}\text{ or }\frac{n-5}{8}$ so $\displaystyle n\equiv{1}\text{ or }5\ (\text{mod }8)$. And, of course, you can reverse the argument.

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    It's the same reason that an odd number is either congruent to 1 or 3 (mod 4). Of course numbers congruent to 0 or 2 (mod 4) are even.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: Dec 10th 2010, 06:35 AM
  2. Modular Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 11th 2010, 03:40 PM
  3. Modular
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 1st 2009, 11:16 AM
  4. proof using modular math
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 12th 2009, 05:04 AM
  5. Modular help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 5th 2007, 11:53 AM

Search Tags


/mathhelpforum @mathhelpforum