Results 1 to 10 of 10
Like Tree2Thanks
  • 1 Post By SlipEternal
  • 1 Post By johng

Thread: from private message

  1. #1
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,928
    Thanks
    2491

    from private message

    Show that the sequence 1^1, 2^2, 3^3 ,... considered mod p is periodic with the least period p(p-1). This was on my midterms, and I couldnt solve it.... Could you please help me.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,020
    Thanks
    1155

    Re: from private message

    You are trying to show $n^n=(n+k)^{n+k} \pmod{p} $. Then show that $k=p(p-1) $ is a value that makes it true, then show it is the minimum value. I'll think about it more, but I have a feeling it is gonna be fairly straightforward.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,020
    Thanks
    1155

    Re: from private message

    Since $p$ is prime, we know that $\mathbb{Z}_p^*$ has elements with order $p-1$. So, the period cannot be smaller than $p$, and $p$ must divide the length of the smallest period.

    Next, $(n+kp)^{n+kp} = (n+kp)^n(n+kp)^{kp} \equiv (n+kp)^n\left[(n+kp)^p\right]^k \pmod p \equiv (n+kp)^n(n+kp)^k \pmod p \equiv n^{n+k} \pmod p$

    In order for $n^{n+k} \equiv n^n \pmod p$, it must be that $n^k \equiv 1 \pmod p$, and by Fermat's Little Theorem, $k = p-1$ is the smallest such $k$ that this is true for all $n$.

    Therefore, the smallest period is $p(p-1)$.
    Last edited by SlipEternal; Oct 5th 2017 at 06:14 AM.
    Thanks from HallsofIvy
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,124
    Thanks
    467

    Re: from private message

    I understand your argument after your first statement that p must divide the period. I just don't understand why this is the case. Could you explain this more fully?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,020
    Thanks
    1155

    Re: from private message

    Quote Originally Posted by johng View Post
    I understand your argument after your first statement that p must divide the period. I just don't understand why this is the case. Could you explain this more fully?
    I am thinking about it, but I am not sure how to explain it. It makes sense in my head, but I realized after I posted that what I am thinking is not what I wrote. I will try to come up with something later, unless you have a better explanation.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,124
    Thanks
    467

    Re: from private message

    Finally, I'm happy. Here's my take on a solution, most of which is what slipeternal wrote.

    Thanks from SlipEternal
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2013
    From
    Hong Kong
    Posts
    38

    Re: from private message

    To romsek, ok so I get your solution up til the point where it says:

    x^x = (x+pq)^(x+pq) = x^x*x^q, why is it x^q not x^pq??
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,928
    Thanks
    2491

    Re: from private message

    Quote Originally Posted by gaussrelatz View Post
    To romsek, ok so I get your solution up til the point where it says:

    x^x = (x+pq)^(x+pq) = x^x*x^q, why is it x^q not x^pq??
    it's not my solution, I believe you mean what JohnG has posted.

    Hopefully he'll see this and respond.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Nov 2013
    From
    Hong Kong
    Posts
    38

    Re: from private message

    Quote Originally Posted by gaussrelatz View Post
    To romsek, ok so I get your solution up til the point where it says:

    x^x = (x+pq)^(x+pq) = x^x*x^q, why is it x^q not x^pq??
    Oh yes my apologies, to johng the message it was.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    759
    Thanks
    343

    Re: from private message

    x^p\equiv x (Fermat's Little Theorem)

    so x^{p q }\equiv  \left(x^p\right)^q\equiv x^q
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum