I'm trying to prove this statement. I've already checked here in StackExchange but I can only find the proof of the converse.
In Wikipedia, it is stated: "A number $a$ relatively prime to an odd prime $p$ is a residue modulo any power of $p$ if and only if it is a residue modulo $p$", and I want to prove the only if part.
This problem appeared to me when I wanted to solve the following problem:
Check that the only solutions, up to congruence, of $X^2 \equiv 25 $ (mod $p^k)$, for any $k$ and for any prime $p \neq 2$, $5$, are $X \equiv \pm 5 $ (mod $p^k)$.
Any help would be appreciated.
Best Answer
You indicated that the problem
Let $k$ be a positive integer and let $p$ be a prime other than $2$ or $5$.
Show that the only solutions, up to congruence, of $x^2 \equiv 25\;(\text{mod}\;p^k)$ are $x \equiv \pm 5\;(\text{mod}\;p^k)$.
is the underlying problem which you are trying to solve.
For the above problem, there is no need to consider quadratic residues.
Instead, we can argue as follows . . .
Suppose $x$ is an integer such that $x^2 \equiv 25\;(\text{mod}\;p^k)$.
Note that $x+5$ and $x-5$ can't both be divisible by $p$, else their difference $$ (x+5)-(x-5)=10 $$ would be divisible by $p$, contrary to $p\ne 2,5$. \begin{align*} \text{Then}\;\;& x^2 \equiv 25\;(\text{mod}\;p^k) \\[4pt] \implies\;& p^k{\,\mid\,}x^2-25 \\[4pt] \implies\;& p^k{\,\mid\,}(x+5)(x-5) \\[4pt] \implies\;& p{\,\mid\,}(x+5)(x-5) \\[4pt] \implies\;& p{\,\mid\,}(x+5)\;\text{or}\;p{\,\mid\,}(x-5)\;\text{but not both} \\[4pt] \end{align*} Then since $p^k{\,\mid\,}(x+5)(x-5)$ and exactly one of $x+5,x-5$ is divisible by $p$, it follows that exactly one of $x+5,x-5$ is divisible by $p^k$.
Therefore $x \equiv \pm 5\;(\text{mod}\;p^k)$, as was to be shown.