1
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ Particular case of math.stackexchange.com/questions/2933720/… for $b = 1$ and $n = p$. $\endgroup$ – darij grinberg Jan 8 '20 at 17:31
  • 1
    $\begingroup$ This is false . Take $p=2 , a=3$ and $n = 3$ $\endgroup$ – The Demonix _ Hermit Jan 8 '20 at 17:31
  • 4
    $\begingroup$ Ah yes, you should require that $p>2$. $\endgroup$ – darij grinberg Jan 8 '20 at 17:32
  • $\begingroup$ 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}.$ $\endgroup$ – Thomas Andrews Jan 8 '20 at 17:36
  • 2
    $\begingroup$ You appear to have accepted an incorrect answer. $\endgroup$ – S. Dolan Jan 8 '20 at 20:11
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – S. Dolan Jan 8 '20 at 18:30
  • $\begingroup$ +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$. $\endgroup$ – almagest Jan 8 '20 at 18:47
  • $\begingroup$ Yes, I've now written it to make this clearer. $\endgroup$ – S. Dolan Jan 8 '20 at 18:50
2
$\begingroup$

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

$\endgroup$
1
-1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – virreand Jan 8 '20 at 18:47
  • $\begingroup$ That is what $a^{\phi(N)}≡1 \ mod(N)$ says. N can not be prime as $p^n$ is not. $\endgroup$ – sirous Jan 8 '20 at 19:19
  • $\begingroup$ 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}}$ :-) $\endgroup$ – Jyrki Lahtonen Jan 8 '20 at 19:26
  • 1
    $\begingroup$ 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$? $\endgroup$ – S. Dolan Jan 8 '20 at 20:08

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.