Results 1 to 6 of 6

Math Help - congruent to modulo; the fundamentals

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    32

    congruent to modulo; the fundamentals

    Show that if n is an odd positive integer, then
    _
    n^2 is congruent to 1 modulo 8, i.e., n^2 = 1(mod 8)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    The odd residue classes modulo 8 are 1,3,5,7. Now you just need to check that 1^2\equiv 3^2\equiv 5^2 \equiv 7^2 \equiv 1 \mod 8.

    (Because every odd integer can be written as 8k+1,8k+3,8k+5, or 8k+7.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kashifzaidi View Post
    Show that if n is an odd positive integer, then
    _
    n^2 is congruent to 1 modulo 8, i.e., n^2 = 1(mod 8)
    Alternatively, we know n=2k+1 for some k\in\mathbb{N} then \left(2k+1\right)^2-1=4k^2+4k+1-1=4k(k+1). And since either k or k+1 is even we see that 8|4k(k+1)=(2k+1)^2-1=n^2-1. Therefore n^2\equiv 1\text{ mod }8
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    This is good; it has the advantage of not relying on (general) principles of modular arithmetic. However, you would have a bit more trouble generalizing this type of argument; for instance proving that the square of every integer relatively prime to 12 is congruent to 1 modulo 12 might make the argument quite a lot less elegant.
    Last edited by Bruno J.; November 4th 2009 at 06:06 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    This is good; it has the advantage of not relying on (general) principles of modular arithmetic. However, you would have a bit more trouble generalizing this type of argument; for instance proving that the square of every odd integer is congruent to 1 modulo 12 might make the argument quite a lot less elegant.
    I agree this method lacks generality. But when questions are posed in such a way that the numbers "work out nice" I assume that is how it should be done.

    Also, this question lends itself to induction.

    Problem: Prove that if n is an odd natural number then n^2\equiv 1\text{ mod }8

    Proof: We do this by weak induction.

    Base case- Trivially 1^2=1\equiv 1\text{ mod }8

    Inductive hypothesis- Assume that n^2\equiv 1\text{ mod }8

    Inductive step- Using the hypothesis we see that 8|n^2-1, but the next odd integer is given by n+2 and (n+2)^2-1=n^2+4n+4-1=\left(n^2-1\right)+4(n+1). Since n is odd we know that n+1 is even therefore 8|4(n+1). So we may conclude that 8|n^2-1+4(n+1)=(n+2)^2-1\quad\blacksquare.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Good!

    Fixed a mistake in my post. "Odd" is not what I meant!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] congruent modulo n
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 8th 2009, 11:53 AM
  2. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 10:04 AM
  3. Replies: 1
    Last Post: October 6th 2009, 12:11 AM
  4. Fundamentals of Calc
    Posted in the Calculus Forum
    Replies: 2
    Last Post: August 31st 2009, 02:57 PM
  5. [SOLVED] Congruent Modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 27th 2006, 07:25 PM

Search Tags


/mathhelpforum @mathhelpforum