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!
Best Answer
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$.