Re: sqrt(2) modulo a prime


We know that 2 is a square modulo any prime of the
form 8n-1 and 8n+1.
In the case 8n-1, the sqrt's of 2 are explicitly 4^n
and -4^n. Likewise
we know that -1 is a square mod p=4n+1 and there is
the explicit
formula +-(2n)! for its square roots. Last, there is
a tougher formula
(due to Jacobi) for the roots of xx+x+1 = 0 mod p
when p is 1 mod 6.
But what about sqrt(2) mod p=8n+1? Has any explicit
formula been found?
I suspected it was possible and that it would be easy
enough to smoke
out, but I haven't succeeded. TIA.


For the prime p = 8n+1, let r be a quadratic nonresidue.
The roots of x^2 = 2 mod p are +/- (r^7n + r^n).

First, r^[(p-1)/2] = r^(4n) = -1 mod p (Euler's criterion).
So also r^(12n) = -1, and since also r^8n = 1 we have
[r^(7n)+r^n]^2 = r^(14n) + 2*r^(8n) + r^(2n)
= (-1)*r^(2n) + 2 + r^(2n) = 2.

This is adapted from a problem in Burton's Intro. to Number Theory. In a problem [sec9.1 # 8] the above is asserted for the case r a primitive root, but as above it works for any quadratic nonresidue r.

For example with p=313 the least primitive root is 10, but 5,7 are nonresidues and would work for r above.

.