### Calculating a p-adic square root, p an odd prime

This returns the first n p-adic digits of the two p-adic sqroots x of a quadratic residue a (mod p).

Here p is an odd prime and x ≡ b (mod p), where b^{2} ≡ a (mod p), 0 < b < p.

This is a BCMATH translation of a BC program.

A sequence of positive integers a_{n} < p^{n+1}, n ≥ 0 is constructed, which converges p-adically to a p-adic square root of a:

a_{0} = b and a_{n} = a_{n-1} + b_{n}p^{n}, n ≥ 1.

a_{n-1}^{2} ≡ a (mod p^{n}), k = (a_{n-1}^{2} - a)/p^{n},

k + 2a_{n-1}b_{n} ≡ 0 (mod p), 0 ≤ b_{n} < p.

Then the two p-adic square roots of a are a_{0} + b_{1}p + ···
Also see lecture notes and solutions.

*Last modified 15th March 2011*

Return to main page