Exercise 2.8.29* (Least period of $1^1,2^2,3^3,\ldots$)

Question

Show that the sequence $1^1,2^2,3^3,\ldots$, considered $\pmod p$ is periodic with least period $p(p-1)$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

\begin{proof} 
Let $f : \N^*  	o \N^* $ defined by $f(k) = k^k$.

We show first that $p(p-1)$ is a period of $f$ modulo $p$.
\begin{align*}
f(k + p(p-1)) &= (k + p(p-1))^{k + p(p-1)}\
&\equiv k^{k + p(p-1)}\
&\equiv k^k \left(k^{p-1}ight)^p.
\end{align*}
\begin{itemize}
\item If $p 
mid k$, then $k^{p-1} \equiv 1 \pmod p$ by Fermat's Theorem, thus $f(k + p(p-1))  \equiv f(k) \pmod p$.

\item I f $p \mid k$, then $f(k + p(p-1))  \equiv f(k) \equiv 0 \pmod p$.

\end{itemize}

In both cases, $f(k + p(p-1)) \equiv f(k) \pmod p$, so $p(p-1)$ is a period of the sequence $([k]_p^k)_{k\geq 1}$.

\bigskip
We recall some elementary properties of periodic sequences.

If $l>0$ is a period modulo $p$ of $f : \N^* 	o \N^*$, by definition $f(a + l) \equiv f(a) \pmod p$ for all positive integers $a$. By induction, $f(a + u l) \equiv f(u) \pmod p$ for all $u\geq 0$. If $u<0$ satisfies $b = a +ul >0$,  then $f(b) \equiv f(b + (-u) l) \pmod p$, thus $f(a+ul) = f(a)$. Therefore, for all positive integers $a,b$,
\begin{align}
a \equiv b \pmod l \Rightarrow f(a) \equiv f(b) \pmod p.
\end{align}

\bigskip
Let $h >0$ be the least period of $f$, so that $h \leq p(p-1)$. Since $f$ is not constant, $h>1$.
We show first that $p \mid h$.

Assume for contradiction that $p
mid h$, so that $p\wedge h = 1$. Then there exist some integers $\lambda_0, \mu_0$ such that $\lambda_0 p + \mu_0 h =1$. Since $(\lambda_0  + j h) p + (\mu_0 - jp) h = 1$ for all integers $j$, we can choose $j$ such that $\lambda = \lambda_0 + jh, \mu = \mu_0 - jp$ satisfy $\lambda>0$ and $\lambda p + \mu h= 1$.

By (1), since $\lambda p>0$, and $\lambda p + \mu h = 1>0$, then $$1 = f(1) = f(\lambda p + \mu h) \equiv f(\lambda  p) \equiv (\lambda p)^{\lambda p} \equiv 0 \pmod p.$$ The contradiction $1 \equiv 0 \pmod p$ shows that $p \mid h$.

So we can write $h = p d$ for some positive integer $d$. Now we show that $p-1 \mid d$.

Let $a>0$ be a primitive root modulo $p$. Then, using Fermat's Theorem,
\begin{align*}
f(a) &= a^a\
f(a+pd) &= (a + pd)^{a + pd}\
&\equiv a^{a + pd} = a^a \left(a^pight)^d\
&\equiv a^a  a^d \pmod p.
\end{align*}
Since $a$ is a primitive root modulo $p$, $a$ is prime to $p$, and $p \mid(a^a(a^d -1))$, thus 
$$a^d \equiv 1 \pmod p.$$
The order of $a$ is $p-1$, so $p-1 \mid d$. We have proved that $p(p-1) \mid h$, where $h \leq p(p-1)$, so $h = p(p-1)$ is the least period.
\end{proof}

Exercise 2.8.29* (Least period of $1^1,2^2,3^3,\ldots$)

Answers

Comments

Exercise 2.8.29* (Least period of $1^1,2^2,3^3,\ldots$)

Answers

Comments

Add answer