# Property prime powers

Let us suppose that $p$ is an odd prime number and and $n$ a natural number greater than $2$. If $R$ is an integer such that $R \not \equiv 1 \pmod{p^{n-1}}$ and $R^{p} \equiv 1\pmod{p^{n-1}}$, does it necessarily hold that $p^{n-1} \parallel R^{p}-1$ (where $\,p^{n-1}\parallel \ell\,$ means $\, p^{n-1}\mid \ell \,$ but $\,p^n\not\mid \ell\,$)?

In the case of $p=2$, the answer would be a "no".

What is going on here?

Since $R^p\equiv R \pmod{p}$, we must have $R\equiv R^p\equiv1 \pmod{p}$. Let $l$ be the largest integer such that $R\equiv1 \pmod {p^l}$. So $1\leq l <n-1$. Then $$R^{p-1}+R^{p-2}+\dotsb+1\equiv p \pmod{p^l},$$ and so if $l>1$, we have $p \| (R^{p-1}+\ldots+1)$. It then follows from $$R^p-1=(R-1)(R^{p-1}+\dotsb+1)$$ that $p^{l+1} \| (R^p-1)$. Since $R^p\equiv1 \pmod{p^{n-1}}$, this implies that $l+1 \geq n-1$. On the other hand, $l<n-1$, and so $l+1<n$. It follows that $l=n-2$ and $p^{n-1} \|(R^p-1)$.

If $l=1$, that is if $R\equiv1\pmod{p}$ but $R \not\equiv1\pmod{p^2}$, let $R=xp+1$ where $x\not\equiv0\pmod p$. One has $$R^p-1=(xp+1)^p-1=\sum_{k=1}^p {{p}\choose{k}}(xp)^k=xp^2+Cp^3$$ which implies that $p^2 \|(R^p-1)$. Since $R^p-1\equiv0\pmod{p^{n-1}}$, we must have $2 \geq n-1$. By assumption $n>2$ and so $n=3$. Therefore, in this case also the claim that $p^{n-1} \|(R^p-1)$ holds.

We shall show that

Proposition. Let $p$ be an odd prime and $n\geq 2$ and integer. If $R$ is an integer such that $$R^p \equiv 1 \pmod{p^n}$$ Then $$R \equiv 1 \pmod {p^{n-1}}$$

So we cannot have both $$R\not\equiv 1 \pmod{p^{n-1}},\quad R^p\equiv 1 \pmod{p^n}$$ On the other hand $$R\not\equiv 1 \pmod{p^{n-1}},\quad R^p\equiv 1 \pmod{p^{n-1}}$$ is always possible since we can pick $R=g^{p^{n-2}(p-1)}$, where $g$ is the primitive root in $(\mathbb Z/p^{n-1}\mathbb Z)^*$.

Proof. Let $g$ be a primitive root of $K=(\mathbb Z/p^n\mathbb Z)^*$. Since $$R^p\equiv 1 \pmod{p^n},$$ we have $R\in K$ and hence $R\equiv g^k\pmod{p^n}$ for some $k$. Hence \begin{align} g^{kp} &\equiv 1\pmod {p^n}\\ \implies kp &\equiv 0 \pmod{\varphi(p^n)=p^{n-1}(p-1)}\\ \implies k &= wp^{n-2}(p-1) \end{align} for some integer $w$. Therefore

# $$R \equiv g^k \equiv g^{wp^{n-2}(p-1)} \equiv (g^{p^{n-2}(p-1)})^w\equiv 1^w \pmod{p^{n-1}}$$

contradicting $R\not\equiv 1 \pmod{p^{n-1}}$. $$\tag*{\square}$$

Remark: The condition $$R^p \equiv 1 \pmod{p^{n-1}}$$ is not used here since it is implied by $$R^p\equiv 1 \pmod{p^n}$$