Exam
- Thursday night from 7-9PM in MATH215
- 7-8 problems
- Current draft is 8 problems
- Chapters 1-4 only
- At least one proof of theorem problem (a "named" theorem)
- At least one problem directly from homework
- May use a calculator (not programable), but won't be necessary
------------------------------------------------------------------------------
p.153 #4
--------
Choose some a* for each a such that aa* congruent to 1 (mod 73)
(a(a+1)\73) = (a(a + aa*)\73) = (a^2(a* + 1)\73) = ((a* + 1)\73)
1 ≤ a* ≤ 72, making the sum (2\73) + (3\73) + ... ((p - 1)\73)
This sum is as in #3 but without the (1\73) term, which is a residue
Therefore, the new sum is 0 - 1 = -1
------------------------------------------------------------------------------
Theorem 5.12
------------
Suppose p is odd. (2\p) = 1 if p congruent to ±1 (mod 8), (2\p) = -1 if
p congruent to ±3 (mod 8).
This can be rewritten as (2\p) = (-1)^(((p^2)-1)/8).
Proof
-----
Want to compute (2\p). Note that 2^((p-1)/2)*((p-1)/2)! = 2*4*6*...(p-1).
If ((p-1)/2) is even, we can rewrite the product as 2*4*6*...((p-1)/2)((p+3)/2)...(p-1).
(p+3)/2 congruent to (p+3)/2 - p,
which is congruent to -((p-3)/2) (mod p);
(p+7)/2 congruent to (p+7)/2 - p, which is congruent to -((p-7)/2) (mod p);
etc.
The
overall product becomes 2*4*6*...(-5)(-3)(-1), which can be written as (-1)^((p-1)/4)((p-1)/2)!.
Therefore, 2^((p-1)/2) must be congruent to (-1)^((p-1)/4).
p congruent to
1 (mod 4) so p congruent to 1 or 5 (mod 8) so ((p-1)/4) = (((8k+r)-1)/4) congruent
to (r-1)/2 (mod 2).
(p-1)/4 is even if p congruent to 1 (mod 8) and odd if
p
congruent to 5 (mod 8).
If ((p-1)/2) is odd, we use the same idea of multiplication by ((p-1)/2)!,
leading to (2\p) = (-1)^((p-1)/4), meaning (2\p) = 1
if p congruent to 7 (mod
8) and
(2\p) = -1 if p congruent to 3 (mod 8).
Together, (2\p) = 1 if p congruent to 1 or 7 (mod 8), (2\p) = -1 if p congruent
to 3 or 5 (mod 8). 7 congruent to -1, 5 congruent to -3
leads to the form given
in Theorem 5.12.
------------------------------------------------------------------------------
Theorem (Quadratic Reciprocity)
-------------------------------
If p,q are distinct odd primes. Then, (p\q)(q\p) = (-1)^((p-1)/2)((q-1)/2).
Since having either ((p-1)/2) or ((q-1)/2) even would result in 1, they must
both be odd if the product of the Legendre symbols is to be odd.
That means
that (p\q)(q\p) = -1 if p congruent to q congruent to 3 (mod 4), otherwise
1.
Gauss's Lemma
-------------
Let p be an odd prime and (a,p) = 1. Consider the integers a, 2a, 3a, ... ((p-1)/2)a
and take their least positive residues.
If n is the number of these residues
which are greater than (p/2), then (a\p) = (-1)^n.
Proof
-----
Let r[1], r[2], ... r[n] be the least positive residues of a, 2a, ... ((p-1)/2)a
which are greater than p/2. s[1], s[2], ... s[k]
are those that aren't. r[i]
cannot be congruent to s[j] for all i and j, n + k = ((p-1)/2), and r[i] cannot
be congruent to r[j]
unless i = j (same with s[i] and s[j]). Each p-r[i] satisfies
0 < p - r[i] ≤ ((p-1)/2).
Multiplying all (p-r[i]) by all s results
in ((p-1)/2)!, so division on both sides results in (-1)^n remaining, as exactly
n are nonresidues.
Notation
--------
[x] is the "greatest integer function", meaning [x] = n if n ≤ x < n+1.
Theorem A
---------
If p is odd and (a,2p) = 1, then (a\p) = (-1)^t, t = sum[j=1;(p-1)/2] [ja/p].
Proof
-----
Let r[i] and s[i] exist as in the proof of Gauss's Lemma. We can use the division
algorithm to write ja = mp + 4, 0 ≤ r < p.
m = [ja/p] since ja/p =
m + r/p. Thus, sum[j=1;(p-1)/2)] ja = sum[j=1;(p-1)/2)] p[ja/p] + sum[i=1;n]
r[i]
+ sum[j=1;k] s[k].
Follow the proof of Gauss's Lemma to reduce the summation
(more on this tomorrow).
(p\q)(q\p) = (-1)^((p-1)/2)((q-1)/2)
can be rewritten as
(p\q) = (q\p)(-1)^((p-1)/2)((q-1)/2)
Theorem A
---------
If p is an odd prime and (a,2p) = 1, then (a\p) = (-1)^t
where t = sum[j=1;(p-1)/2] floor(ja/p).
Proof
-----
Let r[1], r[2], ... r[n] be as in Gauss's Lemma. Let s[1], s[2], ... s[k] be
the least positive residues of a, 2a, ... ((p-1)/2)a.
For 1 ≤ j ≤ (p-1)/2,
write ja = p * floor(ja/p) + r where 0 ≤ r ≤ p-1. ja/p
= floor(ja/p) + r/p.
Therefore, we have sum[j=1;(p-1)/2] ja = sum[j=1;(p-1)/2]
p * floor(ja/p) + sum[j=1;n] r[j] + sum[j=1;k] s[j].
By rewriting and subtraction,
it is (a-1) sum[j=1;(p-1)/2] j = p(sum[j=1;(p-1)/2] floor(ja/p) - n) - 2 sum[j=1;n]
r[j].
(a-1)((p^2 - 1)/8) congruent to p(sum[j=1;(p-1)/2] floor(ja/p) - n) (mod
2). (a-1)((p^2 - 1)/8) congruent to sum[j=1;(p-1)/2] floor(ja/p) - n (mod 2).
Since we have (a,2p) = 1, a is odd, making the left side odd. Therefore, n congruent
to sum[j=1;(p-1)/2] floor(ja/p) (mod 2), which we call t.
Therefore, (a\p) =
(-1)^n = (-1)^t.
This can be used as an alternate proof for the 1 (mod 8) / 3 (mod 8) property.
Theorem (Quadratic Reciprocity)
-------------------------------
If p != q are odd primes, then (p\q)(q\p) = (-1)^((p-1)/2)((q-1)/2).
Proof
-----
Let S = {(x,y) | 1 ≤ x ≤ (p-1)/2 and 1 ≤ y ≤ (q-1)/2}.
Using the choice property, |S| = ((p-1)/2)((q-1)/2).
Let S[1] = {(x,y) | qx < py}
as well as S[2] = {(x,y) | py < qx}. We know that S = S[1] + S[2].
Rewriting
gives S[1] = {(x,y) | 1 ≤ y ≤ (q-1)/2 and 1 ≤ x ≤ py/q},
S[2] = {(x,y) | 1 ≤ x ≤ (p-1)/2 and 1 ≤ y ≤ qx/p}.
|S[1]| = sum[j=1;(q-1)/2] floor(pj/q) and |S[2]| = sum[j=1;(p-1)/2] floor(qj/p).
By Theorem A, (p\q) = (-1)^n and (q\p) = (-1)^m with n + m = |S| = ((p-1)/2)((q-1)/2).
Thus, (p\q)(q\p) = ((-1)^n)((-1)^m), or (p\q)(q\p) = (-1)^((p-1)/2)((q-1)/2).
Example
-------
Compute (14\311). By multiplicativity, (14\311) = (2\311)(7\311). Since 311 =
38*8 + 7, (2\311) = 1.
Thus, (14\311) = (7\311) = (311\7)(-1) = - (3\7). We have
(3\7) = -1 from Euler's Criterion, so (14\311) = 1.
Example
-------
Compute (1891\1999). (1891\1999) = (-108\1999) = (-1\1999)(3\1999), which
results in (-1)(3\1999) = -(1999/3)(-1) = 1.
Example
-------
Computer (13\31). This is (31\13)(-1)^(6*15) = (31\13) = (5\13). Using quadratic
reciprocity again, we get (13\5)(-1)^(2*6) = (13\5) = (3\5).
Doing it again,
we get (5\3)(-1)^(2*1) = (5\3) = (2\3). This is (-1)^((3^2 - 1)/8), which
is -1.
Jacobi Symbol (as mentioned on p.151)
-------------------------------------
Q is odd, Q > 0, Q = p[1]^k[1] p[2]^k[2] ... p[r]^k[r]. The Jacobi Symbol
of P with respect to Q, (P{Q), is π[i=1;r] (P\P[i])^(k[i]).
If (P,Q) ∫ 1,
(P{Q) = 0. Otherwise, (P{Q) = ±1. If P is prime, then it's the Legendre
Symbol.
NOTE: (P{Q) = 1 does not imply x^2 congruent to P (mod Q) is solvable.
Theorem B
---------
Suppose Q, Q' are odd positive integers
(1) (P{Q)(P{Q') = (P{QQ')
(2) (P{Q)(P'{Q) = (PP'{Q)
(3) If (P,Q) = 1, then (P^2{Q) = (P{Q^2) = 1
(4) If (PP',QQ') = 1, then (P'P^2{Q'Q^2) = (P'{Q')
(5) If P' congruent to P (mod Q), then (P'{Q)
Proof
-----
(1) Q = p[1]p[2]...p[r], Q' = q[1]q[2]...q[s], QQ' = p[1]...p[r]q[1]...q[s],
so (P{QQ') = (π[i=1;r] (P\p[i]))(π[i=1;r] (P\q[i]) = (P{Q)(P{Q').
Theorem C
---------
If Q>0, Q odd, then
(1) (-1{Q) = (-1)^((Q-1)/2)
(2) (2{Q) = (-1)^((Q^2 - 1)/8)
Proof
-----
(1) Let Q = p[1]p[2]...p[r] with each p[i] odd. Then, (-1{Q) = π[i=1;r]
(-1\p[i]) = π[i=1;r] (-1)^((p[i]-1)/2) = (-1)^(sum[j=1;r] (p[j]-1)/2).
If a and b are odd, note that (ab-1)/2 - ((a-1)/2 + (b-1)/2) = ((a-1)(b-1))/2,
which is congruent to 0 (mod 2).
(2) (a^2 b^2 - 1)/8 congruent to (a^2 - 1)/8 + (b^2 - 1)/8 (mod 8), so subtracting
gives ((a^2 - 1)(b^2 - 1))/8.
Theorem D
---------
If P and Q are odd positive integers and (P,Q) = 1, then (P{Q)(Q{P) = (-1)^(((p-1)/2)((q-1)/2))).
Remember: Jacobi encapsulates Legendre
------------------------------------------------------------------------------
Example
-------
Compute (105\317). This can be inverted from Theorem D, so we have (2{105),
which becomes (-1)^((105^2 - 1)/8) from Theorem C, which is 1.
Assuming we
didn't have the ability to use the Jacobi symbol, we could have written it
as (3\317)(5\317)(7\317), which we could've inverted in parts.
This would've
given us (2\3)(2\5)(2\7), which is (-1)(-1)(1) or 1.