One of my number theory exercises this week asks the following:
Let $n$ be an odd natural number and assume that the Legendre symbol $\left(\frac np\right)$ equals $1$ for some prime $p>2$. Show that $N_{x^2−n}(p^k) = 2$ for all natural numbers $k = 1,2,3,...$.
As I understand, I am supposed to prove that $x^2 \equiv n \pmod{p^k}$, from which the result follows, but I am not sure how to show that based on the information given.
Even if I managed to prove the base case of the induction, how do I proceed from there, what would my induction step be?
Edit: $N_{x^2−n}(p^k)$ is defined as the number of roots to the equation $x^2−n \equiv 0 \pmod{p^k}$.
Proof: Let $g$ be a primitive root of $\bmod p^\alpha$ and since gcd$(a,p)=1 \,\,\exists \,\, i \in \mathbb{Z}$ such that $g^i \equiv a \bmod p^\alpha $. If there exist $x$ such that $x^2 \equiv a \bmod p^\alpha $ , then gcd$(x,p^\alpha)=1$. So $g^u \equiv x \bmod p^\alpha $ for some $u$. This implies $g^{2u} \equiv g^{i} \bmod p^\alpha $, which means $2u \equiv i \bmod p^{\alpha-1}(p-1) $. This equation has gcd$(2,p^{\alpha-1}(p-1)) = 2 $ solutions if $2 \mid i $ and no solutions if $2 \nmid i$. Now we have to consider the following cases:
If $2 \mid i$, then $\left(\dfrac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \equiv \left(g^{p-1}\right)^{\frac{i}{2}} \equiv 1 \bmod p$ . Similarly if $2 \nmid i, \left(\dfrac{a}{p}\right) =-1 $
So, from the above claim, $N_{x^2-n}(p^k) = 1 + \left(\dfrac{n}{p}\right)$. Now you can finish from here :) .