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

Question

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

Answer 1

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?

Answer 2

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

Answer 3

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.