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.

Printable View

- Oct 4th 2017, 10:59 PMromsekfrom 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 AMSlipEternalRe: 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 AMSlipEternalRe: 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 AMjohngRe: 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 AMSlipEternalRe: from private message
- Oct 6th 2017, 04:18 PMjohngRe: 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 PMgaussrelatzRe: 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 PMromsekRe: from private message
- Oct 13th 2017, 09:14 PMgaussrelatzRe: from private message
- Oct 14th 2017, 04:32 AMIdeaRe: 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$