### Calculating 2-adic square roots

This returns the first n binary digits of the two 2-adic sqroot x of an integer a=8k+1.

This is a BCMATH translation of a BC program.
A sequence of positive integers a_{n} < 2^{n+2}, n ≥ 0 is constructed, which converges 2-adically to a 2-adic square root of a:

a_{n-1}^{2} ≡ a (mod 2^{n+2}),

a_{0} = 1 or 3, a_{n} = a_{n-1} + b_{n}2^{n+1}, n ≥ 1.

b_{n} is 0 or 1 and is determined by b_{n} ≡ (a_{n-1}^{2} - a)/2^{n+2} (mod 2).

a_{0} = 1 implies x = 1 +0*2 + b_{1}2^{2} + ···

a_{0} = 3 implies x = 3 +1*2 + b_{1}2^{2} + ···

(See lecture notes and solutions).

*Last modified 17th March 2011*

Return to main page