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.

Results 1 to 10 of 10

- Oct 4th 2017, 10:59 PM #1

- Joined
- Nov 2013
- From
- California
- Posts
- 5,774
- Thanks
- 2417

- Oct 5th 2017, 02:41 AM #2

- Joined
- Nov 2010
- Posts
- 2,834
- Thanks
- 1087

## 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 #3

- Joined
- Nov 2010
- Posts
- 2,834
- Thanks
- 1087

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

- Joined
- Dec 2012
- From
- Athens, OH, USA
- Posts
- 1,116
- Thanks
- 465

- Oct 6th 2017, 06:35 AM #5

- Joined
- Nov 2010
- Posts
- 2,834
- Thanks
- 1087

## Re: from private message

- Oct 6th 2017, 04:18 PM #6

- Joined
- Dec 2012
- From
- Athens, OH, USA
- Posts
- 1,116
- Thanks
- 465

- Oct 13th 2017, 07:49 PM #7

- Joined
- Nov 2013
- From
- Hong Kong
- Posts
- 22

- Oct 13th 2017, 07:53 PM #8

- Joined
- Nov 2013
- From
- California
- Posts
- 5,774
- Thanks
- 2417

- Oct 13th 2017, 09:14 PM #9

- Joined
- Nov 2013
- From
- Hong Kong
- Posts
- 22

- Oct 14th 2017, 04:32 AM #10

- Joined
- Jun 2013
- From
- Lebanon
- Posts
- 718
- Thanks
- 329