A (simple) polynomial congruence to modulus prime power

Question

Take $R,n\in \mathbb Z$ and $p$ a prime. The congruence

\[ x^n \equiv R\text { mod }(p)\]

has $\ll _n1$ solutions $x\in \{ 0,1,...,p-1\} $ by Lagrange's Theorem.

Is the same true if I replace $p$ by an arbitrary prime power? As far as I can tell - yes, because of the following argument.

CLAIM:

For all $\alpha \geq 1$ the congruence

\[ x^n \equiv R\text { mod }(p^\alpha )\]

has $\ll _n1$ solutions modulo $(p^\alpha )$.

PROOF OF CLAIM:

Let's suppose there's $\ll _n1$ solutions to the congruence modulo $p^{\alpha -1}$, for some $\alpha \geq 1$, and argue with induction.

Recall Hensel's Lemma, which says that if

\[ x^n \equiv R\text { mod }(p^{\alpha -1})\]

has a solution $X^{'}_0$ then there's a unique solution $X_0$ mod $(p^\alpha )$ to

\[ x^n \equiv R\text { mod }(p^{\alpha })\hspace {5mm}\text { satisfying }\hspace {5mm}X_0\equiv X{'}_0\text { mod }(p^{\alpha -1}).\]

Suppose the solutions to the congruence modulo $(p^{\alpha -1})$ are given by $\{ x_1,...x_N\} $, where $N\ll _n1$ by the inductive hypothesis. If we have a solution $X_0$ to the congruence mod $(p^\alpha )$ then necessarily $X_0$ is a solution to the congruence mod $(p^{\alpha -1})$ and therefore

\[ X_0\equiv x_i\text { mod }(p^{\alpha -1}).\hspace {10mm}(1)\]

But Hensel's lemma says that $X_0$, being a solution to the congruence mod $(p^\alpha )$ and satisfying (1), is unique modulo $p^\alpha $. Therefore there is only one choice for $X_0$, given (1), and (1) is in turn one of $N$ possible congruences. So there's only $N\ll _n1$ possibles choices for $X_0$, and we're done.

I've just remembered I've forgotten the differntiability condition for Hensel's Lemma, so let's suppose $p$ doesn't divide $n$. Then is the argument right? I basically just want to check.

Thanks!

Answer 1

If $n,\alpha>1$ then for every integer $k$ the congruence class of $kp^{\alpha-1}$ is a solution to the congruence $$x^n\equiv0\pmod{p^{\alpha}},$$ so there are at least $p$ solutions. In particular the number of solutions is not bounded by any function of $n$.

Your argument fails because it fails to consider the differentiability condition of Hensel's lemma: The lemma requires that $$(X_0')^n\equiv R\pmod{p^{\alpha-1}} \qquad\text{ and }\qquad n(X_0')^{n-1}\not\equiv0\pmod{p}.$$ So the lemma, and hence your argument, works only if both $n$ and $R$ are coprime to $p$.