# Number of Solutions Mod $2^k$

I am trying to solve this problem and would appreciate any direction: Let $a\in \mathbb Z$ with $a ≡ 1 \pmod 8$ and $k\in \mathbb N$ with $k ≥ 3$ be given. Prove that $x^2 ≡ a \pmod {2^k}$ has precisely $4$ solutions

I have worked out that the solutions always take the form $\pm (2^{k-3}+1)$ and $\pm (2k+1)$ but do not know how to show this is always true and that these are the only solutions.

The previous questions on this assignment have all involved Hensel's Lemma but I am not sure if this can be applied for $p=2$.

• Have you checked quadratic residues modulo power of a prime? – Tal-Botvinnik Mar 24 '18 at 13:55
• I don't understand how I'm supposed to check this – user529653 Mar 24 '18 at 14:04
• Combine this and this. We probably have an exact duplicate somewhere here. – Jyrki Lahtonen Mar 24 '18 at 14:39
• So you can use Hensel's lifting on powers of 2? This is what I needed to know, thank you. – user529653 Mar 24 '18 at 14:47

Hensel certainly does apply here. Write $a=1+8k$, and then we want to solve $X^2=1+8k$. Set $Y=(X-1)/2$, $X=2Y+1$, and substitute to get $Y^2+Y-2k=0$, to which you now apply Hensel to get a root $Y=y_0$, and a root $x_0=2y_0+1$ that solves the original equation $X^2=a=1+8k$ modulo $2^k$.

You now have one root of $X^2\equiv a\pmod{2^k}$, and you want to find all. But if $\rho$ is another root, then $a/\rho$ is a square root of unity modulo $2^k$, so you need only find all $r\pmod{2^k}$ with $r^2\equiv1\pmod{2^k}$. There are four, and here’s the reason:

The group of odd numbers modulo $2^k$ is of form $C_2\times C_{2^{k-2}}$, where the factors are cyclic groups of the indicated order. More precisely, it’s $\{\pm1\}\times\bigl((1+4\Bbb Z)\big/(1+2^k\Bbb Z)\bigr)$, and the elements of order two here are $\pm(1\pm2^{k-1})$, so that your four square roots of $a$ are $\pm x_0\cdot(1\pm2^{k-1})$, where $x_0$ is the number you found before.

Perhaps the most interesting example can be gotten by looking at $a=-7$; for fun, let’s take $k=8$. Your first square root (via Hensel) is $x_0\equiv181\pmod{256}$. The others are $-181\equiv{75}$, $181\cdot129\equiv53\pmod{256}$, and $-53\equiv203\pmod{256}$

$x^2 = 2^k p + a = 2^k p + 2^3 q+1$

now making $x = 2^n+1$

$2^{2n}+2^{n+1}+1 = 2^k p + 2^3 q+1$ and then

$p = 2^{2n-k}$ and $q=2^{n-2}$

then for $n \ge 2$ and $k \lt 2n$ we have

$x^2=(2^n+1)^2 \equiv a \mod 2^k$ and also $a \equiv 1 \mod 8$

• I understand what you did to find p and q but do not understand how they help prove the problem. Can you elaborate? – user529653 Mar 24 '18 at 14:26
• $a≡ 1\mod 8 ⇒ a=9^n=( ± 3)^{2n} ⇒ x^2≡( ± 3)^{2n}\mod 2^3⇒x≡( ± 3)^n\mod 2^3$ – sirous Mar 24 '18 at 14:37
• How does this apply to the higher powers? I'm sorry I'm very lost. – user529653 Mar 24 '18 at 14:43
• If $a \equiv 1 \mod 8 \rightarrow a = 8q+1$ – Cesareo Mar 24 '18 at 14:57