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*
editLegendre 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*
editWe 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 p^{2}. We let
we want x^{2} ≡ a (mod p^{2}), 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