Results 1 to 10 of 10

Math Help - Multiplicative order

  1. #1
    Newbie
    Joined
    Aug 2011
    Posts
    11

    Multiplicative order

    Hi, need a some help with this proof.

    Prove the multiplicative order of (1+n) \ mod \ n^2 is n for odd prime n.

    How do I go about this?

    Thank You for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: Multiplicative order

    You have to try first. What is the definition of the multiplicative order?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,277
    Thanks
    669

    Re: Multiplicative order

    step one: what is (1 + p)^p \ (mod \ p^2)? justify your answer.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2011
    Posts
    11

    Re: Multiplicative order

    Quote Originally Posted by Deveno View Post
    step one: what is (1 + p)^p \ (mod \ p^2)? justify your answer.
    I am sorry, I don't know.

    I can see that n^2 does not divide (1+n)^n.

    \frac{(1+n)^n}{n^2}=0

    (1+n)^n=0

    which is false for positive n.

    I need a little more help if you can.

    But thanks for your reply.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,277
    Thanks
    669

    Re: Multiplicative order

    try expanding (1+p)^p using the binomial theorem. which terms don't have p^2 in them?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Aug 2011
    Posts
    11

    Re: Multiplicative order

    Quote Originally Posted by Deveno View Post
    try expanding (1+p)^p using the binomial theorem. which terms don't have p^2 in them?
    (p+1)^p= \sum_{k=0}^p \tbinom pk p^k \cdot 1^{p-k} = \sum_{k=0}^p \tbinom pk p^k

    So in the expansion of (1+p)^p the only terms than don't have p^2 in them are 1 and p.

    So where to from here then?

    Thanks for your help Dev
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,277
    Thanks
    669

    Re: Multiplicative order

    um, no....

    the coefficent of p in the expansion is p:

    (p+1)^p = 1 + p^2 + \frac{p(p-1)}{2}p^2 + \dots where all the remaining terms involve higher powers of p.

    thus (p+1)^p = 1 (mod\ p^2).

    so the multiplicative order of p+1 (mod p^2) has to divide p. what are our choices, given that p is an odd prime?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Aug 2011
    Posts
    11

    Re: Multiplicative order

    Quote Originally Posted by Deveno View Post
    um, no....

    the coefficent of p in the expansion is p:

    (p+1)^p = 1 + p^2 + \frac{p(p-1)}{2}p^2 + \dots where all the remaining terms involve higher powers of p.

    thus (p+1)^p = 1 (mod\ p^2).

    so the multiplicative order of p+1 (mod p^2) has to divide p. what are our choices, given that p is an odd prime?
    Oh yeah, slight error on my part. So if the order of p+1 mod p^2 has to divide p and p is an odd prime, then by the definition of a prime, the order of p+1 mod p^2 has to be p.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,277
    Thanks
    669

    Re: Multiplicative order

    almost...why isn't the order of p+1, 1 (after all, 1 divides p)?

    it's a small detail, and easily answered, but it never hurts to dot the "i's" and cross the "t's".
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Aug 2011
    Posts
    11

    Re: Multiplicative order

    Quote Originally Posted by Deveno View Post
    almost...why isn't the order of p+1, 1 (after all, 1 divides p)?

    it's a small detail, and easily answered, but it never hurts to dot the "i's" and cross the "t's".
    Yes, of course! That makes perfect sense. Thanks again for your fantastic help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Multiplicative Order
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 18th 2010, 02:42 PM
  2. [SOLVED] order of elements in multiplicative group
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 28th 2009, 10:04 AM
  3. multiplicative
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 18th 2008, 06:22 PM
  4. is phi multiplicative
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 14th 2008, 07:22 AM
  5. Multiplicative Set
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 29th 2008, 02:36 PM

Search Tags


/mathhelpforum @mathhelpforum