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

From Wikibooks, open books for an open world
< High School Mathematics Extensions‎ | Further Modular Arithmetic
Jump to: navigation, search
High School Mathematics Extensions75% developed

Supplementary Chapters50% developedPrimes and Modular Arithmetic100% developedLogic75% developed

Mathematical Proofs75% developedSet Theory and Infinite Processes50% developed Counting and Generating Functions75% developedDiscrete Probability25% developed

Matrices100% developedFurther Modular Arithmetic50% developedMathematical Programming0% developed

100 percent.svg Further Modular Arithmetic
100 percent.svg Multiplicative Group and Discrete Log
Problems & Projects
100 percent.svg Problem Set
100 percent.svg Project
100 percent.svg Exercises Solutions
50%.svg Problem Set Solutions
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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle k + 2x_0x_1 \equiv 0 \pmod{p} } , we simply need to make the subject


..generalisation ..example

..method for finding a sqr root mod p