# Powers modulo higher residues

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

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 try to write below the only thing I have in mind to justify it properly. Any comment on the proof or any proposal for a more elegant argument is welcome.

The proof is essentially working on rephrasing the sentence "$$y$$ is a $$k$$-th power modulo $$n$$".

Let $$n = p^\gamma$$ in this paragraph. Since $$p\geqslant 3$$, we know that $$(\mathbf{Z}/n\mathbf{Z})^\times$$ is cyclic, say generated by the element $$x$$. Thus, the element $$y \in (\mathbf{Z}/n\mathbf{Z})^\times = \langle x \rangle$$ can be written $$y=x^a$$ for a certain $$a \geqslant 0$$. Moreover, we assumed that $$y$$ is a $$k$$-th power modulo $$p^\gamma$$, that is to say $$y = (x^b)^k = x^{kb}$$ for a certain $$b \geqslant 0$$. So that we get $$x^a = x^{kb}$$, that is finally $$x^{a-kb} = 1$$. That is possible if and only if $$\phi(n) \mid a - kb$$. By Bezout identity, this is equivalent to $$(\phi(n), k) \mid a$$.

Assume $$n = p^t$$ for a certain $$t\geqslant \gamma$$. We have $$\phi(n) = p^{t-1}(p-1)$$ and $$(\mathbf{Z}/p^t \mathbf{Z})^\times = \langle x \rangle$$ for a certain $$x \in \mathbf{Z}/p^t\mathbf{Z}$$. Finally, $$y=x^a$$ is a $$k$$-th power if and only if $$(p^{t-1}(p-1), k) \mid a$$. By definition, $$p^{\gamma - 1} \mid k$$, so that we also have $$\begin{equation} (p^{t-1}(p-1), k) \mid a \Longleftrightarrow (p^{t-\gamma}(p-1), kp^{1-\gamma}) \mid a p^{1-\gamma}. \end{equation}$$

Assume $$n = p^\gamma$$. We have $$\phi(n) = p^{\gamma-1}(p-1)$$ and $$(\mathbf{Z}/p^\gamma \mathbf{Z})^\times = \langle x^{p^{t-\gamma}} \rangle$$ for a certain $$x \in \mathbf{Z}/p^t\mathbf{Z}$$. Thus, $$y=x^{ap^{t-\gamma}}$$ is a $$k$$-th power if and only if $$(p^{\gamma-1}(p-1), k) \mid a p^{t}$$ so that $$\begin{equation} (p^{\gamma-1}(p-1), k) \mid ap^{t-\gamma} \Longleftrightarrow (p-1, kp^{1-\gamma}) \mid ap^{1-\gamma}. \end{equation}$$

Finally, for all $$t \geqslant \gamma$$, I would like to say that the first relation is implied by the second, so that any $$k$$-th power modulo $$p^\gamma$$ is also a $$k$$-th power modulo $$p^t$$.

This questions comes from my misunderstanding of the following statement, from Vaughan: • $\mathbb{Z}_{2^k}$ is not cyclic ($k \ge 3$), so if result you prove is false for $p=2$, might be evidence you need a not-so-simple proof. though, to be fair, $2$ is weird for many reasons – mathworker21 Feb 8 at 10:48
• @mathworker21 I indeed do assume $p$ is not 2. – Gory Feb 9 at 2:37
• I might be missing something, but the statement does not seem to be true :-) Consider $p=3$ and $k=9$. Number $8$ is $k$-th power modulo $9=3^2$, but it is not $9$-th power modulo $27=3^3$. More generally, $(p^\gamma-1)$ is $k$-th power modulo $p^\gamma$ but does not seem to be $k$-th power modulo $p^{\gamma+1}$ – Peter Košinár Feb 9 at 10:32
• ... I just noticed I missed a bit in the "more general" case in my previous comment; $k$ is meant to be equal to $p^{\gamma+1}$. – Peter Košinár Feb 9 at 10:45

When you wrote

If $$y \in \mathbf{Z}$$ is a $$k$$-th power modulo $$p^\gamma$$

I assume, similar to how a Quadratic residue is described, this only requires for $$y$$ that there exists an $$x \in \mathbb{Z}$$ where

$$y \equiv x^{k} \pmod{p^\gamma} \tag{1}\label{eq1A}$$

This answer is based on that understanding. Similar to Peter Košinár's comment, consider $$p = 3$$, $$\gamma = 1$$ and $$k = p^{\gamma + 1} = 9$$, so obviously $$p^{\gamma + 1} \mid k$$.

Now, consider modulo $$p^t$$ where $$t = \gamma + 2 = 3$$, so $$p^t = 27$$. You can verify that for all $$a \in \mathbb{Z}$$ and all $$b \in \{-1,0,1\}$$ that

$$(ap + b)^k \equiv b^k \pmod{p^t} \tag{2}\label{eq2A}$$

Thus, the only $$k$$'th power values modulo $$p^t$$ are $$0$$, $$1$$ and $$p^t - 1 = 26$$. However, there are many values of $$y$$ which are a $$k$$'th power modulo $$p^{\gamma} = 3^1 = 3$$ which are not equivalent to these. Since

$$2 \equiv 2^{9} \pmod{3} \tag{3}\label{eq3A}$$

this means among any $$27$$ consecutive integers, only $$1$$ of the $$9$$ values which are $$2$$ mod $$3$$ would work.

Regarding your proof, I believe part of the problem is you're mixing equality and equivalence statements. For example, for a certain generator element $$x$$, you state

$$y=x^a$$ for a certain $$a \geqslant 0$$

rather than $$y \equiv x^a \pmod p$$. This restriction to an equality, which is not (based on my understanding) in the original statement, means you can end up drawing conclusions that are inconsistent with what you are trying to prove.

Also, you should be careful with your reuse of variable names in different contexts. For example, you have $$n = p^{\gamma}$$, then $$n = p^{t}$$ and once again $$n = p^{\gamma}$$. This is a small issue as you make it fairly clear it only applies to the paragraph. However, you also seem to suggest a single value of $$x$$ can be reused as the same cyclic element for various powers of $$p$$, with the same power of $$a$$, as the value of $$y$$ in your second & third paragraphs where you have $$n = p^{\gamma}$$ and then $$n = p^{t}$$, but then switch to $$y=x^{ap^{t-\gamma}}$$ in the next paragraph even though you say $$y = x^a$$ for the same group $$2$$ paragraphs above.

One final thing is you have near the end

$$(p^{\gamma-1}(p-1), k) \mid ap^{t-\gamma} \Longleftrightarrow (p-1, kp^{1-\gamma}) \mid ap^{1-\gamma} \tag{4}\label{eq4A}$$

Going from the left to the right, you're multiplying by $$p^{1-\gamma}$$. However, on the far right, you should then get $$ap^{t+1-2\gamma}$$ instead of $$ap^{1-\gamma}$$.

• Thanks a lot for your answer, I am beginning to see what is really falling short in what I wrote. In fact this statement is somewhat written in Vaughan's book on the circle method (page 22, just before 2.26) and I am stuck understanding why this is true in that setting, while I believe having written here all the hypotheses... – Gory Feb 14 at 1:51
• I edited my question so that to display his statement. – Gory Feb 14 at 1:52
• @Gory You're welcome for my answer. As for displaying his statement in your question, the question text has not been updated since Feb. $6$. Did you perhaps forget to click "Save Edits" (if you clicked "Cancel" by mistake after making changes, you should have got a confirmation dialog, so I assume this didn't happen)? – John Omielan Feb 14 at 2:37
• I hope it is updated now, the image took some time to upload, but on my page there is a link displayed. – Gory Feb 14 at 3:06
• @Gory Yes, I now also see an image. Thanks for uploading it. There are several important parts which weren't included in your question. One other small note is you originally correctly wrote $p^{\tau} || k$, which means the highest power of $p$ which divides $k$ is $\tau$, but an edit changed it to $p^{\tau} \mid k$, which is less constrained. – John Omielan Feb 14 at 3:30