High School Mathematics Extensions/Primes/Project/The Square Root of -1
HSME |
Content |
---|
Primes |
Modular Arithmetic |
Problems & Projects |
Problem Set |
Project |
Solutions |
Exercise Solutions |
Problem Set Solutions |
Misc. |
Definition Sheet |
Full Version |
PDF Version |
Project -- The Square Root of -1
[edit | edit source]Notation: In modular arithmetic, if
for some m, then we can write
we say, x is the square root of y mod m.
Note that if x satisfies x2 ≡ y, 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
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
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
have a solution? Why?
5. If p ≡ 1 (mod 4) prime and q ≡ 1 (mod 4) prime and p ≠ q. Show that
has 4 solutions.
6. Find the 4 solutions to
note that 493 = 17 × 29.
7. Take an integer n with more than 2 prime factors. Consider:
Under what condition is there a solution? Explain thoroughly.