3
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.