# from private message

• Oct 4th 2017, 10:59 PM
romsek
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.
• Oct 5th 2017, 02:41 AM
SlipEternal
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.
• Oct 5th 2017, 04:46 AM
SlipEternal
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)$.
• Oct 6th 2017, 06:13 AM
johng
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?
• Oct 6th 2017, 06:35 AM
SlipEternal
Re: from private message
Quote:

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.
• Oct 6th 2017, 04:18 PM
johng
Re: from private message
Finally, I'm happy. Here's my take on a solution, most of which is what slipeternal wrote.

http://i64.tinypic.com/2w6zzgp.png
• Oct 13th 2017, 07:49 PM
gaussrelatz
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??
• Oct 13th 2017, 07:53 PM
romsek
Re: from private message
Quote:

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.
• Oct 13th 2017, 09:14 PM
gaussrelatz
Re: from private message
Quote:

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.
• Oct 14th 2017, 04:32 AM
Idea
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$