High School Mathematics Extensions/Primes/Project/The Square Root of -1

From Wikibooks, open books for an open world
< High School Mathematics Extensions‎ | Primes
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% developed Primes
100% developed Modular Arithmetic
Problems & Projects
100% developed Problem Set
100% developed Project
100% developed Exercise Solutions
50% developed Problem Set Solutions
100% developed Definition Sheet
100% developed Full Version
25% developed PDF Version

Project -- The Square Root of -1[edit]

Notation: In modular arithmetic, if

x^2 \equiv y \pmod{m} \!

for some m, then we can write

x \equiv \sqrt{y} \pmod{m}

we say, x is the square root of y mod m.

Note that if x satisfies x2y, then m - x ≡ -x when squared is also equivalent to y. We consider both x and -x to be square roots of y.

1. Question 5 of the Problem Set showed that

x \equiv \sqrt{-1} \equiv \sqrt{p-1} \pmod{p}

exists for p ≡ 1 (mod 4) prime. Explain why no square root of -1 exist if p ≡ 3 (mod 4) prime.

2. Show that for p ≡ 1 (mod 4) prime, there are exactly 2 solutions to

x \equiv \sqrt{-1} \pmod{p}

3. Suppose m and n are integers with gcd(n,m) = 1. Show that for each of the numbers 0, 1, 2, 3, .... , nm - 1 there is a unique pair of numbers a and b such that the smallest number x that satisfies:

x ≡ a (mod m)
x ≡ b (mod n)

is that number. E.g. Suppose m = 2, n = 3, then 4 is uniquely represented by

x ≡ 0 (mod 2)
x ≡ 1 (mod 3)

as the smallest x that satisfies the above two congruencies is 4. In this case the unique pair of numbers are 0 and 1.

4. If p ≡ 1 (mod 4) prime and q ≡ 3 (mod 4) prime. Does

x \equiv \sqrt{-1} \pmod{pq}

have a solution? Why?

5. If p ≡ 1 (mod 4) prime and q ≡ 1 (mod 4) prime and p ≠ q. Show that

x \equiv \sqrt{-1} \pmod{pq}

has 4 solutions.

6. Find the 4 solutions to

x \equiv \sqrt{-1} \pmod{493}

note that 493 = 17 × 29.

7. Take an integer n with more than 2 prime factors. Consider:

x \equiv \sqrt{-1} \pmod{n}

Under what condition is there a solution? Explain thoroughly.