Show that $a^p \equiv 1$ (mod $p^n$) $\Rightarrow a \equiv 1$ (mod $p^{n-1}$)

I'm trying to show that $$a^p \equiv 1$$ (mod $$p^n$$) $$\Rightarrow a \equiv 1$$ (mod $$p^{n-1}$$), where $$p$$ is an odd prime.

Since $$a^p \equiv 1$$ (mod $$p^n$$) $$\iff aa^{p-1} \equiv 1$$ (mod $$p^{n-1}p$$), I was hoping to use Fermat's theorem, which states that $$a^{p-1} \equiv 1$$ (mod $$p$$). I therefore tried substituting $$a^{p-1}$$ with $$pk + 1$$ in the equation but I didn't manage to solve it like that.

I've been trying to solve it algebraically for some time but is no where close so I could use some help and ideas.

• Particular case of math.stackexchange.com/questions/2933720/… for $b = 1$ and $n = p$. – darij grinberg Jan 8 '20 at 17:31
• This is false . Take $p=2 , a=3$ and $n = 3$ – The Demonix _ Hermit Jan 8 '20 at 17:31
• Ah yes, you should require that $p>2$. – darij grinberg Jan 8 '20 at 17:32
• Yes, you need that $p$ is an odd prime. You have $3^2\equiv 1\pmod{2^3}$ but $3\not\equiv 1\pmod{2^2}.$ – Thomas Andrews Jan 8 '20 at 17:36
• You appear to have accepted an incorrect answer. – S. Dolan Jan 8 '20 at 20:11

Let $$a=1+p^iX$$, where $$X$$ is coprime to $$p$$.

Then $$a^p-1=\begin{pmatrix}p\\1\\\end{pmatrix}p^iX+ ... +p^{pi}X^p$$, where all the coefficients on the RHS except possibly the last are divisible by $$p$$.

We know that $$p^{n}$$ divides the LHS so $$i>0$$. Then, on the RHS, the first term has the lowest power of $$p$$ and so its power, $$i+1$$, must be at least $$n$$.

• The first term has power $i+1$. All the other terms have power $ki+1,k>1$ except the last which has power $pi$. Where's the problem? – S. Dolan Jan 8 '20 at 18:30
• +1 Ok. So the argument is (1) the last term must be divisible by $p$ (because all the others are), so $i>0$. Hence all terms except the first are divisible by $p^{2i}$, except the first which is divisible by $p^{i+1}$. So if $i<n-1$ the sum will not be divisible by $p^n$, whereas the lhs is divisible by $p^n$. – almagest Jan 8 '20 at 18:47
• Yes, I've now written it to make this clearer. – S. Dolan Jan 8 '20 at 18:50

Actually,

$$a^p \equiv 1 \bmod p^n \iff a \equiv 1 \bmod p^{n-1}$$

The key relevant fact is this:

If $$G$$ is a cyclic group of order $$m$$ and $$d$$ divides $$m$$, then there is exactly one subgroup of order $$d$$: $$H=\{ x \in G : x^d=1 \}$$.

The group in question is $$G=U(p^n)$$, the group of units mod $$p^n$$. Then $$G$$ has order $$\phi(p^n)=p^{n-1}(p-1)$$, a multiple of $$p$$. Let $$H$$ be the subgroup of order $$p$$.

If $$a \equiv 1 \bmod p^{n-1}$$ then $$a=1+bp^{n-1}$$ and so $$a^p=(1+bp^{n-1})^p=1+cp^n \equiv 1 \bmod p^n$$. In other words, $$a=1+bp^{n-1} \in H$$ for $$b=0,\dots,p-1$$. This gives us $$p$$ elements in $$H$$. Therefore, they are all the elements of $$H$$ since $$H$$ has order $$p$$.

• – lhf Jan 9 '20 at 22:25

If $$a^p≡1 \mod (p^n)$$ then $$\phi (p^n)=p$$$$p^{n-1}(p-1)=p$$$$p^{n-2}(p-1)=\phi(p^{n-1})=1$$$$\phi(p^{n-1})=1$$$$a^{\phi(p^{n-1})}=a^1≡1 \mod (p^{n-1})$$.

• I'm not sure why $\phi(p^n) = p$. I know that we must have $p | p^{n-1}(p-1)$, but the equality confuses me. – virreand Jan 8 '20 at 18:47
• That is what $a^{\phi(N)}≡1 \ mod(N)$ says. N can not be prime as $p^n$ is not. – sirous Jan 8 '20 at 19:19
• This is not correct. For example $4^3\equiv1\pmod{3^2}$ but still $\phi(3^2)=6\neq3$. Do observe that $4\equiv1\pmod{3^{2-1}}$ :-) – Jyrki Lahtonen Jan 8 '20 at 19:26
• The result $a^p≡1 \mod (p^n)$ is satisfied by $a=1$ for any prime power. It implies nothing about the prime at all. So what reason is there for the claim about $\phi(p^n) = p$? – S. Dolan Jan 8 '20 at 20:08