问题及解答

证明: 若 $a$ 是 $p$ 的平方剩余, 则它是 $p^k$ 的平方剩余, $k$ 为任意正整数.

假设 $x^2\equiv a\pmod p^k$, 即 $x^2=a+tp^k$, $t$ 是某个整数. 于是

\[
\begin{split}
(x+np^k)^2&=x^2+2nxp^k+n^2 p^{2k}\\
&=a+(t+2nx)p^k+n^2 p^{2k}\\
&\equiv a+(t+2nx)p^k\pmod p^{k+1}.
\end{split}
\]

选取合适的 $n$ 使得 $t+2nx\equiv 0\pmod p$, 从而 $(x+np^k)^2\equiv a\pmod p^{k+1}$.

这实际上是更一般的 Hensel 引理的特殊情形.

References:

译自

http://mathoverflow.net/questions/223430/relationship-between-quadratic-residues-modulo-a-prime-and-quadratic-residues-mo

https://en.wikipedia.org/wiki/Hensel%27s_lemma