# How many solutions does the equation $x^p\equiv x \pmod{p^n}$ have in $\mathbb{Z}_{p^n}$?

where $p$ is a prime number and $n$ is a positive integer.

What I have done so far:
I thought that a solution to $x^p \equiv x \pmod p$ is a solution to $x^p \equiv x \pmod{ p^n}$.
Now $\gcd(x^p,p)=1$ or $\gcd(x^p,p)=p$.
I am not sure how to proceed from this point.

Edit:I have been considering using Hensel's lemma to solve this equation since we have p^n so considering the equation mod p and lifting it could help. But subtracting x from both sides and solving, I get $x \equiv 0 mod p$ or $x^{p-1} \equiv 1modp$ Substituting x in the first case into f'(x) yields $-1 \not\equiv 0modp$ but, how would I substitute x in the second case ?

Any ideas or hints are welcome and much appreciated

• Case $n=2$: Given $x$ coprime with $p$, the integer $q_p(x):=\frac{x^{p-1}-1}{p}$ is defined to be the Fermat quotient. Hence, for this case, you are equivalently asking how many $x \in \mathbf{Z}_{p^n}^\star$ satisfies $p\mid q_p(x)$. Feb 17, 2018 at 21:22
• @paololeonetti I haven't studied the Fermat quotient but the numerator of it reminds of Fermat's little theorem. Are there any properties if the Fermat quotient worth mentioning maybe as I am still not too sure ? Feb 17, 2018 at 22:50

Any such solution gives rise to a cyclic subgroup of $(\mathbb{Z}/p^n \mathbb{Z})^\times$ or order $p-1$.

If $p$ is an odd prime, then $(\mathbb{Z}/p^n \mathbb{Z})^\times \cong \mathbb{Z}/p^{n-1}(p-1) \mathbb{Z}$.

Can you take it from here?

Well, Maithreya Sitaraman has given a perfect answer, but using a fact that you may not know.

Let me take a different tack than she did, and give you a hint, looking at possible solutions $x$ for which $p|x$, i.e. $x\equiv0\pmod p$. Such an $x$ would have $p^n\vert(x^p-x)$, and if $x=p^mz$ with $0<m<n$ and $\gcd(p,z)=1$, then $$x^p-x=x^{pm}z^p-p^mz=p^m(x^{p(m-1)}z^p-z)\not\equiv0\pmod{p^n}\,.$$ In other words, there’s only one solution $x$ of your condition that also satisfies $x\equiv0\pmod p$.

Now your job is to show that among the $x$ with $x\equiv n\pmod p$, there is only one for which $x^p-x\equiv0\pmod{p^n}$. Thus you see that there are only $p$ solutions, in all, to the congruence $x^p\equiv x\pmod{p^n}$.

• why did you take $x=p^{m}z$? Feb 18, 2018 at 14:47
• Because I needed a $p$-unit $z$ somehow. Feb 18, 2018 at 21:29
• since $x^{p-1} \equiv 1 mod p$ is fermat's little theorem we can observe that there are p-1 solutions. Factoring $x^{p}-x = x(x-1)(x-2)...(x-(p-1))$ we would have x=0, x=1...x=p ? Would this be sufficient ? Feb 18, 2018 at 22:00
• More complicated than that. Try $p=5$ to see what goes wrong there. Feb 18, 2018 at 22:45

There are $p$ solutions to this question, one for each value from $0$ to $p-1$. Indeed, it is related to the issue that numbers ending in ...109376 have all their powers ending the same.

The case for $x^p=x \pmod{p^n}$ corresonds to $x^n \mid x^{p-1}$, and it is this second example that we shall look at. In essence, what we shall show, is that the last $n$ digits of $x$ in base $p$, must fall in a particular set of $p$ solutions, one for each digit.

Consider the general number $w, x$ where these are the last two places in base p. Raising this to the power of $p$, will give all multiples of $p^2$, + $pwx^{p-1}, x^p$. But we see already that the 'second remainder' or 'tens column' is already a multiple of $p$, by the binomial expansion, so the last digits of $w, x$, is a particular $x_1, x$.

This can be repeated by replacing $p$ with $p^2$, and shows that for any $x_0$, there is a unique sequence $x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0$ for every $x_0$, for which this sequence is unique, and must exist.

The missing case is $0$. Of course, one can have sequences ending in $0$, such as $1,0$. But the only instance where the condition holds true here is $p^n\mid x$, which is the case that $0$ is a soultion.

This last point raises questions about the vary nature of primes, since the effect of multiplication by primes seek to make the set more zero-like (even in $\mathbb Z$, so the net result is that one has to add a certain number of non-zero divisors to get 0, and where the case where p is composite, this means that the general endings 'converge' onto a smaller range of values.