Results 1 to 7 of 7

Math Help - Modulus question

  1. #1
    Member
    Joined
    Sep 2011
    Posts
    114

    Modulus question

    I am currently stuck on a practice problem.

    it goes....

    Show that if n is an odd integer then...

    n^2=1 or 9(mod16)
    n^4=1(mod 16)

    Show that if n is any integer that is not divisible by 2 or 3, then n^2=1(mod12)

    This stuff is so confusing to me :S
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    10,969
    Thanks
    1011

    Re: Modulus question

    Quote Originally Posted by ehpoc View Post
    I am currently stuck on a practice problem.

    it goes....

    Show that if n is an odd integer then...

    n^2=1 or 9(mod16)
    n^4=1(mod 16)

    Show that if n is any integer that is not divisible by 2 or 3, then n^2=1(mod12)

    This stuff is so confusing to me :S
    If \displaystyle n is an odd integer, then \displaystyle n = 2n - 1.

    So \displaystyle n^2 = (2n - 1)^2 = 4n^2 - 4n + 1 = 4n(n - 1) + 1.

    Notice that \displaystyle n(n - 1) is even, so that means \displaystyle 4n(n -1 ) = 4(2m) = 8m

    Therefore \displaystyle n^2 = 8m + 1 = 1\textrm{ or }9 \textrm{ mod }16.


    Also \displaystyle n^4 = (2n - 1)^4 = 16n^4 - 32n^3 + 24n^2 - 8n + 1 = 8(2n^4 - 4n^3 + 3n^2 - n) + 1 = 8n(n - 1)(2n^2 - 2n + 1) + 1 = 16m(2n^2 - 2n + 1) + 1 = 1 \textrm{ mod }16
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2011
    Posts
    114

    Re: Modulus question

    Thanks so much for the reply!

    I don't understand two point of the solution...

    n(n-1)....why is this even? is it just by rule?

    secondly

    I can not readily see how this is true overtly true

    8m + 1 = 1 or 9 { mod }16.
    EDIT: oh lol I can see why that is true now
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    10,969
    Thanks
    1011

    Re: Modulus question

    Quote Originally Posted by ehpoc View Post
    Thanks so much for the reply!

    I don't understand two point of the solution...

    n(n-1)....why is this even? is it just by rule?

    secondly

    I can not readily see how this is true overtly true

    8m + 1 = 1 or 9 { mod }16.
    EDIT: oh lol I can see why that is true now
    If n is even, then n - 1 is odd. The product of an even and an odd is even.

    If n is odd, then n - 1 is even. The product of an odd and an even is even.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2011
    Posts
    114

    Re: Modulus question

    I have some upon another problem that is similar so I am just piggybacking it on this thread.

    Show that if n is any integer that is not divisible by 2 or 3, then n^2= 1 (mod 12).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Modulus question

    Quote Originally Posted by ehpoc View Post
    I have some upon another problem that is similar so I am just piggybacking it on this thread.

    Show that if n is any integer that is not divisible by 2 or 3, then n^2= 1 (mod 12).
    Hint: n^2-1=(n-1)(n+1)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Modulus question

    hint #2: n-1 and n+1 are both even (why?) one of these is divisible by 3 (again, why?)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Complex Analysis: Maximal Modulus Principle question
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: September 15th 2011, 03:35 PM
  2. Minimum-modulus principle question
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: April 23rd 2010, 02:51 PM
  3. question involving modulus (congrency)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 27th 2009, 04:19 AM
  4. Modulus (Brainteaser question)
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 1st 2009, 01:20 AM
  5. Replies: 6
    Last Post: June 20th 2009, 07:40 AM

Search Tags


/mathhelpforum @mathhelpforum