# How to set up Newton-Raphson method for 2-adics

Amongst others I have read the following references: [1], [2], [3] and [4]. In [4] ccorn gives an iteration of the reciprocal square root while the others ([1] in equation (2), [2] in equation (14) and [3] at the bottom of page 12) use the normal formula as in $\mathbb{R}$. I can follow ccorn's method and iterate increasing sequences of bit strings with the windows calculator in programming mode. With the other method I fail to do so because the calculation actually results in accumulating fractions instead of integers. What am I doing wrong and why is ccorn's method not mentioned elsewhere?

The above was for square roots. Now in general I would like to know, which irrationals are in $\mathbb{Q}_2$. That is what are the equivalent conditions as the 1 mod 8 for the square roots? And how does one set up the iteration? That is with or without ccorn's trick of reciprocal. And it would be nice to contrast that to odd primes.

• Are you familiar with Hensel lifting? I'm not entirely sure what you are asking when you are looking for irrationals in $\mathbb{Q}_2$. For instance, you can make define any arbitrary string of 0s and 1s to the left and as long as it's not eventually repeating, it will be irrational as any number that is eventually repeating you can subtract off the part that doesn't repeat and then shuffle the repeating part to solve for the rational number it represents just like the trick you would do for periodic decimal digits of a real number normally. – user207119 Apr 17 '18 at 15:14
• Also, more of a trick to do with inverting numbers since it seems to loosely pertain to what you're asking; you can use Euler's theorem that $a^{\varphi(p^n)-1} \equiv a^{-1} \mod p^n$ to approximate the inverse of a number in $\mathbb{Q}_p$ although I think computationally, this is less than ideal. At least it gets you a systematic way to do this without tricks which seems like part of what you're looking for? – user207119 Apr 17 '18 at 15:18
• I suppose that you’re asking which algebraic irrationals are in $\Bbb Q_2$ or more generally in $\Bbb Q_p$. First you can look at the minimal polynomial over $\Bbb Q$ of your irrational number, and see whether Hensel can tell you that it factors. But here’s one where Hensel does you no good: $x^3+3x^2+6x+24$, irreducible over the rationals by Eisenstein, but has three roots in $\Bbb Q_2$ by looking at the Newton Polygon. – Lubin Apr 18 '18 at 3:27
• While searching for Newton Polygons I found this paper which at the top of page 13 makes two iterartions of the newton method of $\sqrt{2}$ in $\mathbb{Q}_7$. The crucial step that I have missed so far was the conversion of the fractional answer to a congruence mod $7^n$. Note that this means that this newton method is grinding out one digit per iteration instead of doubling the number of bits as in ccorn's method. And again this is for odd primes only. – glurks Apr 18 '18 at 13:58
• The Newton-Raphson method for $\sqrt2\in\Bbb Q_7$ certainly does double the accuracy at every stage. Using a $p$-adic package for my multiplications, subtractions, and divisions, I got the successive approximations $3;$, then $1111111111111113;$, then $3062113523306213;$, then $1623525321216213;$, then $2011266421216213;$, which is correct to sixteen $7$-ary places, in four iterations of the process. – Lubin Apr 21 '18 at 4:29