1. ## 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.

2. ## 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.

3. ## 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)$.

4. ## 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?

5. ## Re: from private message

Originally Posted by johng
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.

6. ## Re: from private message

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

7. ## 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??

8. ## Re: from private message

Originally Posted by gaussrelatz
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.

9. ## Re: from private message

Originally Posted by gaussrelatz
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.

10. ## Re: from private message

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

so $\displaystyle x^{p q }\equiv \left(x^p\right)^q\equiv x^q$