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

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


*Finding the square root*

edit

Legendre Symbol

edit

.. 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

 

and if a is not a square then

 

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

*Finding the square root*

edit

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

 

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

 

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

 

we want x2 ≡ a (mod p2), so

 
 

for some k as   so  , we see that

 

so if we need to find   such that  , we simply need to make   the subject

 .

..generalisation ..example

..method for finding a sqr root mod p