Results 1 to 6 of 6

Math Help - 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
    2
    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) ?

    n=1\!\!\!\pmod 4\Longrightarrow n is odd, so it must be n=1,3,5\,\,or\,\,7\!\!\!\pmod 8, but 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
    n=1\!\!\!\pmod 4\Longrightarrow n is odd, so it must be n=1,3,5\,\,or\,\,7\!\!\!\pmod 8, but n=3\!\!\!\pmod 8\Longrightarrow n=3\!\!\!\pmod 4...with 7 is similar.

    Tonio

    Can you explain this part:

    n=1,3,5\,\,or\,\,7\!\!\!\pmod 8, but 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
    2
    Quote Originally Posted by 1337h4x View Post
    Can you explain this part:

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

    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
    Super Member
    Joined
    Mar 2010
    Posts
    980
    Thanks
    236
    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, n\equiv{1}\ (\text{mod }4) means 4 divides n-1. Since \frac{n-1}{4} is an integer, it must be odd or even. So \frac{n-1}{4}=2m\text{ or }2m+1, where m is an integer. Solving both for m gives m=\frac{n-1}{8}\text{ or }\frac{n-5}{8} so 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: December 10th 2010, 06:35 AM
  2. Modular Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2010, 03:40 PM
  3. Modular
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 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: March 5th 2007, 11:53 AM

Search Tags


/mathhelpforum @mathhelpforum