# If $y$ is a $k$th power modulo $p^\gamma$, then it is also a $k$th power modulo $p^t$ for $t \geqslant \gamma$

This question is the true version I wanted to ask of this question.

Say $$p$$ is an odd prime number, $$k$$ a positive integer and $$p^{\tau} || k$$. Let $$\gamma = \tau + 1$$. I would like to prove

If $$y \in \mathbf{Z}$$ is a $$k$$-th power modulo $$p^\gamma$$, then it is also a $$k$$-th power modulo $$p^t$$ for any $$t \geqslant \gamma$$.

I don't know how standard this fact is. Stated like this, it seems to be a rather simple fact. However, I do not find any simple proof for this fact, and I tried to write a messy proof (see post quoted above) but nothing that convinces me or shed lights on what is happening.

This questions comes from my misunderstanding of the following statement, from Vaughan:

• You need $y$ coprime to $p$ for the highlighted statement to be true. – Bart Michels Feb 14 at 9:08

Hensel's lemma for singular points implies that:

When $$y$$ is coprime to $$p$$ and a $$k$$th power residue mod $$p^\gamma$$, with $$\gamma > 2 \tau$$, then $$y$$ is a $$k$$th power residue mod all $$p^t$$.

The philosophy behind Hensel's lemma is to use Newton's method, which requires that an approximation to a root is sufficiently close to a root relative to the derivative. Here: $$f(x) = x^k-y$$, $$|f'(x)| = p^{-\tau}$$, and one needs $$|f(x)| < |f'(x)|^2$$, i.e. $$\gamma > 2\tau$$.

In this particular case, the proof of Hensel's lemma can be adapted to show that $$|f(x)| < |f'(x)|$$ is sufficient, i.e. that $$\gamma > \tau$$ is sufficient.

Here we go. Take $$\gamma > \tau$$ and $$x \in \mathbb Z$$ with $$x^k -y \equiv 0 \pmod {p^\gamma}$$. We will find $$a \in \mathbb Z$$ with $$(x+ a p^{\gamma - \tau})^k - y \equiv 0 \pmod{p^{\gamma+1}}$$. By induction, it then follows that $$y$$ is a $$k$$th power modulo all $$p^t$$. Divide by $$p^\gamma$$ to obtain the condition $$\frac{x^k - y}{p^\gamma} + kx^{k-1}ap^{-\tau} + \sum_{j = 2}^k \binom k j x^{k-j} a^j p^{j(\gamma-\tau)-\gamma} \equiv 0 \pmod p \,.$$ The coefficient of $$a$$ in the second term is invertible mod $$p$$ (this is why we took the power $$p^{\gamma-\tau}$$ in the beginning of the proof). Let's show that all terms in the sum are divisible by $$p$$. We can then take $$a = - \frac{x^k - y}{p^\gamma} \cdot (kp^{-\tau}x^{k-1})^{-1} \bmod p \,.$$ Write the $$j$$th term as $$\frac{k}j \binom{k-1}{j-1} x^{k-j} a^j p^{j(\gamma-\tau)-\gamma} = \frac{kp^{-\tau}}j \binom{k-1}{j-1} x^{k-j} a^j p^{(j-1)(\gamma-\tau)} \,.$$ We want to show that $$v_p(j) < (j-1)(\gamma-\tau)$$. Because $$\gamma > \tau$$, it suffices to show that $$v_p(j) < j-1$$. Because $$j < p^{j-1}$$ (here we use that $$p >2$$ for the only time), $$j$$ cannot be divisible by $$p^{j-1}$$.

• Thank you very much for your answer. However, it is not sufficient to prove Vaughan's statement, right? (he only requires $\gamma = \tau + 1$) – Gory Mar 18 at 15:39
• @Gory the answer addresses this – hunter Mar 18 at 15:43
• @Gory My answer is a proof of that statement. You can skip the first three paragraphs and start reading from "Here we go", which is where the proof begins. – Bart Michels Mar 18 at 15:56