1
$\begingroup$

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$.

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

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}$

$\endgroup$
0
$\begingroup$

$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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.