[proofplan] Both parts are proved by induction on $n$, lifting a solution modulo $p^n$ (respectively $2^n$) to one modulo $p^{n+1}$ (respectively $2^{n+1}$). The lifting step is a local Newton iteration: given $x$ with $x^2 \equiv a \pmod{p^n}$, we write $x^2 = a + k p^n$ and perturb $x \mapsto x + tp^n$ (or $x + t \cdot 2^{n-1}$ in the dyadic case); the squared perturbation introduces a linear-in-$t$ correction, and solving a linear congruence modulo $p$ (respectively modulo $2$) eliminates the residual. For $p$ odd the solvability of that linear congruence uses the invertibility of $2x$, which holds because $x$ is coprime to $p$; for $p = 2$ the parity of $x + k$ plays the analogous role and requires the stronger base case $a \equiv 1 \pmod 8$. [/proofplan] [step:Base case for $p$ odd: use the Legendre hypothesis] Let $p$ be an odd prime and suppose $\left(\frac{a}{p}\right) = 1$. By the definition of the Legendre symbol, there exists $x_1 \in \mathbb{Z}$ with $x_1^2 \equiv a \pmod{p}$, and $(a, p) = 1$ (since the Legendre symbol is $\pm 1$ only for $(a, p) = 1$). In particular $(x_1, p) = 1$, because $p \mid x_1$ would force $p \mid x_1^2 \equiv a$, contradicting $(a, p) = 1$. This establishes the assertion for $n = 1$. [/step] [step:Inductive step for $p$ odd: solve a linear congruence modulo $p$ to upgrade from $p^n$ to $p^{n+1}$] Suppose we have $x \in \mathbb{Z}$ with $(x, p) = 1$ and $x^2 \equiv a \pmod{p^n}$ for some $n \geq 1$. Write \begin{align*} x^2 = a + k p^n \qquad \text{for some } k \in \mathbb{Z}. \end{align*} We seek $t \in \mathbb{Z}$ such that $(x + tp^n)^2 \equiv a \pmod{p^{n+1}}$. Expanding: \begin{align*} (x + tp^n)^2 &= x^2 + 2xtp^n + t^2 p^{2n} \\ &= a + kp^n + 2xtp^n + t^2 p^{2n} \\ &\equiv a + (k + 2xt)p^n \pmod{p^{n+1}}, \end{align*} where we used $2n \geq n + 1$ (equivalent to $n \geq 1$) to drop the $t^2 p^{2n}$ term. We require $(k + 2xt) \equiv 0 \pmod{p}$, i.e. \begin{align*} 2xt \equiv -k \pmod{p}. \end{align*} Since $p$ is odd and $(x, p) = 1$, the coefficient $2x$ is a unit in $\mathbb{Z}/p\mathbb{Z}$ by [Units in $\mathbb{Z}/n\mathbb{Z}$](/theorems/1699). Hence $t := -k \cdot (2x)^{-1} \bmod p$ solves the congruence. Setting $x' = x + tp^n$, we have $(x')^2 \equiv a \pmod{p^{n+1}}$, and $(x', p) = (x, p) = 1$ since $x' \equiv x \pmod p$. This completes the inductive step. [guided] Suppose by induction that we have $x \in \mathbb{Z}$ with $x^2 \equiv a \pmod{p^n}$ and $(x, p) = 1$. We want to produce $x'$ with $(x')^2 \equiv a \pmod{p^{n+1}}$. The natural ansatz is the local Newton correction: perturb $x$ by $tp^n$ and choose $t$ to cancel the error. Write $x^2 = a + kp^n$; the integer $k$ measures the obstruction at level $n$. Then \begin{align*} (x + tp^n)^2 = x^2 + 2xtp^n + t^2 p^{2n} = a + (k + 2xt)p^n + t^2 p^{2n}. \end{align*} Why is $t^2 p^{2n}$ negligible modulo $p^{n+1}$? Because $2n \geq n + 1$ whenever $n \geq 1$, which is our case. So modulo $p^{n+1}$ the perturbed square is $a + (k + 2xt) p^n$. We therefore need $p \mid k + 2xt$, i.e. a linear congruence for $t$: \begin{align*} 2xt \equiv -k \pmod p. \end{align*} The question is whether this is solvable. The coefficient $2x$ is invertible modulo $p$ provided $\gcd(2x, p) = 1$. Why does that hold? Because $p$ is odd, $\gcd(2, p) = 1$; and by the inductive hypothesis $(x, p) = 1$. Hence $\gcd(2x, p) = 1$, and by [Units in $\mathbb{Z}/n\mathbb{Z}$](/theorems/1699) (whose hypothesis $\gcd(a, n) = 1$ is met), $2x$ has an inverse modulo $p$. Set \begin{align*} t := -k \cdot (2x)^{-1} \pmod p. \end{align*} Then $x' = x + tp^n$ satisfies $(x')^2 \equiv a \pmod{p^{n+1}}$. It remains to verify the inductive hypothesis for $x'$: we need $(x', p) = 1$. Since $x' = x + tp^n$ and $p^n \equiv 0 \pmod p$, we have $x' \equiv x \pmod p$, and $(x, p) = 1$ gives $(x', p) = 1$. So the induction continues. **Remark on technique.** This is the dyadic version of Newton's method: given an approximate root modulo $p^n$, the perturbation $x \mapsto x + tp^n$ plays the role of $x \mapsto x - f(x)/f'(x)$ with $f(x) = x^2 - a$ and $f'(x) = 2x$. The non-vanishing of $f'(x) = 2x$ modulo $p$ — the unit hypothesis — is exactly the non-degeneracy condition that Hensel's lemma requires. [/guided] [/step] [step:Base case for $p = 2$: the hypothesis $a \equiv 1 \pmod 8$ gives solutions at $n = 1, 2, 3$] Suppose $a \equiv 1 \pmod 8$. We verify solubility at low levels. For $n = 1, 2, 3$: the element $x = 1$ satisfies $x^2 = 1 \equiv a \pmod 8$, so in particular $1^2 \equiv a \pmod{2^n}$ for $n \in \{1, 2, 3\}$. Note that $(x, 2) = 1$: the solution is automatically odd. This is essential for the induction. [/step] [step:Inductive step for $p = 2$: lift from $2^n$ to $2^{n+1}$ for $n \geq 3$ using an odd-parity perturbation] Suppose $n \geq 3$ and $x \in \mathbb{Z}$ with $x$ odd and $x^2 \equiv a \pmod{2^n}$, so $x^2 = a + 2^n k$ for some $k \in \mathbb{Z}$. **Case 1: $k$ is even.** Then $2^n k \equiv 0 \pmod{2^{n+1}}$, so $x^2 \equiv a \pmod{2^{n+1}}$ already; take $x' = x$. **Case 2: $k$ is odd.** Consider the perturbation $x' = x + 2^{n-1}$: \begin{align*} (x')^2 &= x^2 + 2 x \cdot 2^{n-1} + 2^{2n-2} \\ &= x^2 + x \cdot 2^n + 2^{2n-2}. \end{align*} Since $n \geq 3$, we have $2n - 2 \geq n + 1$, so $2^{2n-2} \equiv 0 \pmod{2^{n+1}}$. Thus \begin{align*} (x')^2 \equiv a + 2^n k + 2^n x = a + 2^n (k + x) \pmod{2^{n+1}}. \end{align*} We required $x$ odd (inductive hypothesis) and $k$ odd (case assumption), so $k + x$ is even. Hence $2^n (k + x) \equiv 0 \pmod{2^{n+1}}$, giving $(x')^2 \equiv a \pmod{2^{n+1}}$. In both cases, the new $x'$ is odd: $x$ itself in Case 1, and $x + 2^{n-1}$ in Case 2 (the addition of $2^{n-1}$ with $n - 1 \geq 2$ preserves parity). This completes the induction. [guided] Suppose inductively that $n \geq 3$, $x$ is odd, and $x^2 = a + 2^n k$. We want $x'$ with $(x')^2 \equiv a \pmod{2^{n+1}}$ and $x'$ odd. Why does the dyadic case require a stronger base ($a \equiv 1 \pmod 8$) and a different perturbation ($x + 2^{n-1}$ instead of $x + tp^n$)? The issue is the coefficient $2x$ in the Newton expansion $(x+t)^2 = x^2 + 2xt + t^2$: when $p = 2$, the factor $2$ is not a unit modulo $2$, so we cannot solve $2xt \equiv -k \pmod 2$ for $t$ (the left side is always even). We need a finer perturbation. **Case 1: $k$ is even.** Then the obstruction $2^n k$ is already divisible by $2^{n+1}$, and $x^2 \equiv a \pmod{2^{n+1}}$. Take $x' = x$. **Case 2: $k$ is odd.** Try $x' = x + 2^{n-1}$ (note: not $x + t \cdot 2^n$ — the lower power is what lets us hit $p^{n+1}$ with a linear correction). Compute \begin{align*} (x')^2 = x^2 + x \cdot 2^n + 2^{2n - 2}. \end{align*} The cross-term $x \cdot 2^n$ contributes at level $2^n$ — exactly where the obstruction lives. The quadratic term $2^{2n-2}$ contributes at level $2^{2n-2}$, and we need $2n - 2 \geq n + 1$, i.e. $n \geq 3$. **This is precisely where the hypothesis $n \geq 3$ is consumed**, and why we needed the base case established up to $n = 3$: for $n < 3$ the perturbation $2^{n-1}$ is too small to make $2^{2n-2}$ negligible. Substituting: \begin{align*} (x')^2 \equiv a + 2^n (k + x) \pmod{2^{n+1}}. \end{align*} For this to be $\equiv a \pmod{2^{n+1}}$ we need $k + x$ to be even. Since $x$ is odd (inductive hypothesis) and $k$ is odd (case assumption), $k + x$ is even. Good — the perturbation works. **Why did we need $a \equiv 1 \pmod 8$?** Because the base case must provide an odd $x$ with $x^2 \equiv a \pmod 8$. The squares of odd integers are $1, 9, 25, \ldots$, all $\equiv 1 \pmod 8$. So $a \equiv 1 \pmod 8$ is necessary for solubility even at level $n = 3$; the theorem says this is also sufficient, because the induction then propagates indefinitely. Finally, the new $x'$ is odd: in Case 1 we took $x' = x$ and $x$ is odd by hypothesis, and in Case 2 we have $x' = x + 2^{n-1}$ with $n - 1 \geq 2$, so $2^{n-1}$ is even and $x + 2^{n-1}$ shares the parity of $x$, which is odd. [/guided] [/step] [step:Conclude] By induction on $n$, in part (i) there exists $x_n \in \mathbb{Z}$ with $x_n^2 \equiv a \pmod{p^n}$ for all $n \geq 1$, and in part (ii) there exists $x_n \in \mathbb{Z}$ with $x_n^2 \equiv a \pmod{2^n}$ for all $n \geq 1$. This completes the proof. [/step]