# High School Mathematics Extensions/Further Modular Arithmetic/Project/Finding the Square Root

Content HSME Further Modular Arithmetic Multiplicative Group and Discrete Log Problem Set Project Exercises Solutions Problem Set Solutions Definition Sheet Full Version PDF Version

## Legendre Symbol

.. to be expanded There is actually a simple way to determine whether a is square

Let g be a generator of G where G is the multiplicative group mod p. Since all the squares form a group therefore, if a is a square, then

${\displaystyle a^{\frac {p-1}{2}}\equiv 1}$

and if a is not a square then

${\displaystyle a^{\frac {p-1}{2}}\equiv -1}$

we shall use these facts in the next section. .. to be expanded

## *Finding the square root*

We aim to describe a way to find a square root in mod m. Let's start with the simplest case, where p is prime. In fact, for square root finding, the simplest case also happens to be the hardest.

If p ≡ 3 (mod 4) then it is easy to find a square root. Just note that if a has a square root then

${\displaystyle (a^{\frac {p+1}{4}})^{2}\equiv a^{\frac {p+1}{2}}\equiv a^{\frac {p-1}{2}}a\equiv a}$

So let us consider primes equivalent to 1 mod 4. Suppose we can find the square root of a mod p, and let

${\displaystyle x_{0}^{2}\equiv a{\pmod {p}}}$

With the above information, we can find the square of a mod p2. We let

${\displaystyle x=x_{0}+x_{1}p\!}$

we want x2 ≡ a (mod p2), so

${\displaystyle x^{2}=x_{0}^{2}+2x_{0}x_{1}p+x_{1}^{2}p^{2}\!}$
${\displaystyle x^{2}=a+kp+2x_{0}x_{1}p{\pmod {p^{2}}}\!}$

for some k as ${\displaystyle x_{0}^{2}\equiv a{\pmod {p}}}$  so ${\displaystyle x_{0}^{2}=a+kp}$ , we see that

${\displaystyle x^{2}=a+p(k+2x_{0}x_{1}){\pmod {p^{2}}}\!}$

so if we need to find ${\displaystyle x_{1}}$  such that ${\displaystyle k+2x_{0}x_{1}\equiv 0{\pmod {p}}}$ , we simply need to make ${\displaystyle x_{1}}$  the subject

${\displaystyle x_{1}\equiv -k(2x_{0})^{-1}{\pmod {p}}}$ .

..generalisation ..example

..method for finding a sqr root mod p