Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k

We give a counting argument. Let $p$ be an odd prime, and suppose that $a$ is not divisible by $p$. Then the congruence $x^2\equiv a\pmod{p^k}$ has either no solution or two solutions.

To prove this, suppose $b^2\equiv a\pmod{p}$. Then from $x^2\equiv b^2\pmod{p^k}$ we conclude that $p^k$ divides $(x-b)(x+b)$. Since $p$ cannot divide both, we conclude that $p^k$ divides one of $x-b$ or $x+b$. So if the congruence has at least one solution $b$, it has exactly two, namely $b$ and $-b$.

The function $f(x)=x^2$ (modulo $p^k$) maps the set $H$ of numbers between $1$ and $p^k-1$ that are not divisible by $p$ to $H$. By the above, this function is two to one.

So half of the elements of $H$ are QR of $p^k$, and half are not. Which half? The ones congruent to a quadratic residue modulo $p$. For if $a$ is not a square modulo $p$, it cannot be a square modulo $p^k$.

The above argument proves that for odd primes $p$, every quadratic residue modulo $p$ is a quadratic residue modulo $p^k$. The result does not hold for $p=2$: Note that $3$ is a quadratic residue of $2$ but not of $4$.

I have long appreciated this result in LeVeque's Fundamentals of Number Theory, Theorem 4.4:

Suppose $p$ is a prime relatively prime to $a$. Let $t_n$ be the order of $a$ modulo $p^n$ and assume that $p^z$ exactly divides $a^{t_1} - 1$. Then if $p > 2$ or $z > 1$,

$$ t_n = \begin{cases} t_1, \quad &\text{for $n \leq z$}\\\\ t_1 p^{n-z}, \quad &\text{for $n > z$.}\end{cases}$$

This result can be used to prove several congruences mod a prime power that are otherwise messy and annoying to prove (for instance, see Other ways to deduce Cyclicity of the Units of certain groups?).

In your question, if $a$ is a quadratic residue modulo $p$, then $t_1$ divides $\frac{p-1}{2}$. Thus in both of the above cases, $t_n$ is a divisor of $p^{n-1} \cdot\frac{p-1}{2} = \phi(p^n)/2$, so $a$ is a quadratic residue modulo $p^n$.