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

{{High School Mathematics Extensions/TOC}}
{{High School Mathematics Extensions/Primes/TOC}}

== Project -- The Square Root of -1 ==
'''Notation:''' In modular arithmetic, if
:<math>x^2 \equiv y \pmod{m} \!</math>
for some ''m'', then we can write
:<math>x \equiv \sqrt{y} \pmod{m}</math>
we say, ''x'' is the square root of ''y'' mod ''m''.

Note that if ''x'' satisfies ''x''<sup>2</sup> &equiv; ''y'', then ''m'' - ''x'' &equiv; -''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
:<math>x \equiv \sqrt{-1} \equiv \sqrt{p-1} \pmod{p}</math>
exists for ''p'' &equiv; 1 (mod 4) prime. Explain why no square root of -1 exist if ''p'' &equiv; 3 (mod 4) prime.

2. Show that for ''p'' &equiv; 1 (mod 4) prime, there are exactly 2 solutions to
:<math>x \equiv \sqrt{-1} \pmod{p}</math>

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'' &equiv; a (mod m)
:''x'' &equiv; b (mod n)
is that number.
E.g. Suppose m = 2, n = 3, then 4 is uniquely represented by
:''x'' &equiv; 0 (mod 2)
:''x'' &equiv; 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'' &equiv; 1 (mod 4) prime and ''q'' &equiv; 3 (mod 4) prime. Does
:<math>x \equiv \sqrt{-1} \pmod{pq}</math>
have a solution? Why?

5. If ''p'' &equiv; 1 (mod 4) prime and ''q'' &equiv; 1 (mod 4) prime and p &ne; q. Show that 
:<math>x \equiv \sqrt{-1} \pmod{pq}</math>
has 4 solutions.

6. Find the 4 solutions to
:<math>x \equiv \sqrt{-1} \pmod{493} </math>
note that 493 = 17 &times; 29.

7. Take an integer ''n'' with more than 2 prime factors. Consider:
:<math>x \equiv \sqrt{-1} \pmod{n}</math>
Under what condition is there a solution? Explain thoroughly.