$$\newcommand\Q{\mathbb Q} \newcommand\Z{\mathbb Z}$$I am a bit confused on the square root of 2-adics. I am pretty sure I am mixing some steps in an algorithm. To be precise, I am trying to solve an exercise in Koblitz' book p-adic numbers, p-adic analysis and zeta functions (this is not a homework, I just want to do it). In exercise of I.7 the reader is asked to solve the square root of -7 in $$\Q_2$$ up to 5-digits and the hint is to use a generalization of Hensel's Lemma:

Let $$f(x)$$ be a polynomial with coefficients in $$\Z_p$$. If $$a_0$$ in $$\Z_p$$ satisfies

• $$f(a_0) = 0 \bmod p^{2m+1}$$
• $$f'(a_0) = 0 \bmod p^m$$
• $$f'(a_0) \ne 0 \bmod p^{m+1}$$

then there is a unique $$a\in\Z_p$$ such that $$f(a) = 0$$ and $$a=a_0 \bmod p^{m+1}$$

Obviously the procedure to solve comes from an algorithm to be seen in the proof of this generalized Hensel's lemma. For my particular problem $$f(x)=x^2+7$$ and $$p=2$$, I choose $$a_0$$ either $$1$$ or $$0$$ (so in fact an integer) and then I iterate to get, for a chosen $$b_1 =1$$ or $$b_1=0$$, $$a_1 = a_0 + b_1 p^{m+1}$$ for which $$f(a_1)=0 \bmod p^{2m+2}$$ and so on i.e. I need to get $$b_i$$ which gives $$a_i$$ such that $$f(a_i) = 0 \bmod p^{2m+1+i}$$.

I might be missing something, but for me the answer for square root of -7 would be of the form $$a_0 + b_12+ b_22^2 + \dots$$ But I have a problem getting the correct answer. So one of the square root (using Pari to check) is $$(a_0,b_1,b_2,\dots)=(1,1,0,1,0,\dots)$$.

Is there a cleaner way to think of this algorithm. I get easily confused and make mistakes with the iteration steps.

Maybe I have mixed something in the procedure. Could someone explain to me why for $$a_0=1$$, we get $$(1,1,0,1,0,\dots)$$?

From this I feel that manually taking roots and even doing simple arithmetic is not practical in the p-adics.

EDIT: The algorithm I have in mind is actually also written here in this online calculator: http://www.numbertheory.org/php/2adic.html

I still fail to get the correct $$b_4$$ using the algorithm. However, the online calculator gives me the correct $$b_4$$. If I follow the procedure, my $$b_4$$ is $$(a_3^2+7)/64 \bmod 2 = 7\bmod 2$$ so it is $$1$$, while the correct answer is $$0$$.

• Compare e.g. sharding4's answer to math.stackexchange.com/q/2298779/96384, for the analogous question with 17 insetad of $-7$. Commented May 29, 2021 at 14:36
• In your approach, I suggest you start with $m=0$, and then I think you should not name the $b_i$ you find there with the same name as the ones in the expansion in the final answer. They are just intermediate calculations. I.e use what you call $b_i$ first to get $a_i$, and then in the end you can write $a_i = a_0+ c_1 2+ c_2 2^2 + ...$. (I think the $b_i$ are not the same as the $c_i$.) Commented May 29, 2021 at 14:41
• why are they different. If I have $a_1=a_0+b_12$ then isn't $a_2 = a_1+b_22^2 = a_0+c_12+b_22^2$ and so on? Commented May 30, 2021 at 5:49
• @Torsten: I am actually a little worried of sharding4's answer in the aforementioned post. It requires me to keep the possible solution for every $p^k$ roots and get rid as I proceed to higher $k$ for which the solutions do not continue (which is at worst case exponential in space and time). I feel one already knows which ones to keep by this version of Hensel's Lemma (I mean there is only 2 possibilities for the root). Anyway, I couldn't determine the fifth digit after I continued to the 6th and 7thu using sharding4's method. Commented May 30, 2021 at 5:57
• Maybe I misunderstood your notation. But don't you get $a_0=1, a_1=3, a_2=3, a_3=11$? Then is not $(a_3^2+7)/64 =2$? Commented May 30, 2021 at 16:00

OK I was finally able to get the correct answer. The site http://www.numbertheory.org/php/2adic.html provides a code for 2-adic square roots and I just looked at it and figured out my embarassing mistake.

I will write the steps. We want to get $$(11010\dots)_2$$ in 2-adics. We have $$f(x) = x^2+7$$ , $$m=1$$ and most importantly that $$a_0=3$$ (not $$1$$). This will give me one (unique) solution and if we start with $$a_0=1$$ we get the negative of that solution. We want $$a_0=3$$ because, we (or I) want to obtain $$(11\dots)_2$$ so it must start with $$a_0=3$$ rather than $$a_0=1$$ because in the other case we would obtain $$(10\dots)_2$$. So what I am trying to say is: my idea was correct but I started with the wrong $$a_0$$.

We can use Hensel's lemma because $$f'(a_0)=6$$ and $$2\mid\mid 6$$.

To get the digit after $$(11)_2$$ we use this algorithm: For the i-th step we want to choose $$b_i$$ such that $$a_i = a_{i-1}+b_i2^{m+i}$$ satisfies $$f(a_i)=0 \bmod 2^{2m+i+1}$$.

• For $$i=0$$ (no steps here), $$a_0=3$$ , and $$f(a_0)=3^2+7=16$$

• For $$i=1$$ (the third digit) we want to choose $$b_1$$ such that $$a_1 = 3 + b_12^{1+1}$$ satisfies $$f(a_1) = 0 \bmod 2^{2+1+1}$$ So $$b_1=0$$ and $$a_0=a_1=3$$.

• For $$i=2$$ (the fourth digit) we want to choose $$b_2$$ such that $$a_2 = 3 + b_22^{1+2}$$ satisfies $$f(a_2) = 0 \bmod 2^{2+2+1}$$ So $$b_2=1$$ and $$a_2 = 3+8=11$$ with $$f(a_2)=128$$

• For $$i=3$$ (the fifth digit) we want to choose $$b_3$$ such that $$a_3=11 + b_32^4$$ satisfies $$f(a_3) = 0 \bmod 2^6$$ So $$b_3=0$$ and so I got the correct five digits $$11010$$.

It is much easier to program this than to iterate by hand, because it is so easy to make this stupid mistake I made (at some point I was confused modulo what powers of $$2$$ I should check the $$a_i$$ and the $$f(a_i)$$). Also, I do not need to "cache" the roots modulo $$2^k$$ after $$a_0=3$$ or $$a_0=1$$.

• Ok, but see there my confusion: $2$-adically, $3=1+1*2$ which I would have interpreted as $a_0=1, b_1=1$ whereas you interpret it as $a_0=3, b_1=0$. That's where I would have called one of the b's (yours or mine) c's instead. Commented May 30, 2021 at 16:23
• you are correct that it is confusing. I also made an error in the original post. The $b_1$ had to be multiplied with $2^{m+1}$ (in our case $m=1$). So the finaly $p$-adic number is $a_0+b_12^{m+1}+b_22^{m+2}+\dots$. So you are absolutely correct about the coefficients of the power of $2$s. Commented May 31, 2021 at 5:01

Since $$11^2\equiv-7\bmod2^6$$, why not render $$...01011_2$$ and call it a day?

Might be nice to know that we can do it a bit easier if we use series,

$$\sqrt{-7} = (1-8)^{1/2} = \sum_{n\ge 0} \binom{1/2}{n} (-8)^n$$

Remember $$\binom{a}{b}=\frac{1}{b!}\prod_{i=0}^{b-1}(a-i)$$, we want up to 5 digits, so we can chop it off at just 3 terms,

$$1+\frac{1}{2} (-8)+\frac{-1}{4*2!} (-8)^2 = 1+2^2+2^4 = 10101_2$$

Might be fair to call this our principal root, and since we're in a field we of course have two solutions to $$x^2+7=0$$ and the negative is simply to complement the digits and add 1, to get $$01011_2$$.