Exam I - Thursday, 7/8/04, 7-9PM, MATH215, covering ch. 1-4

------------------------------------------------------------------------------

Example: f(x) = 6x^3 + 13x^2 + x - 2, f(x) congruent to 0 (mod 75)
--------
f(x) congruent to 0 (mod 3)
f(x) congruent to 0 (mod 25)

x^2 + x + 1 congruent to 0 (mod 3)
f(0) congruent to 1 (mod 3)
f(1) congruent to 0 (mod 3)
f(2) congruent to 1 (mod 3)
1 solution mod 3

If f(x) congruent to 0 (mod 25), then f(x) congruent to 0 (mod 5)
f(0) congruent to 3 (mod 5)
f(1) congruent to 3 (mod 5)
f(2) congruent to 0 (mod 5)
f(3) congruent to 0 (mod 5)
f(4) congruent to 4 (mod 5)

From there, we get f(x) congruent to 0 (mod 25) when x = 2, 7, 12, 17, or 22
Therefore, we solve x congruent to 1 (mod 3) and x congruent to 2 (mod 25), x congruent to 1 (mod 3) and x congruent to 7 (mod 25), etc.

------------------------------------------------------------------------------

f(x) congruent to 0 (mod p^a)
f(x) = a[n]x^n + a[n-1]x^(n-1) + ... a[0]
For any particular m, the largest k for which m doesn't divide a[k] is the degree of f(x) (mod m).

Definition: f(x) is "monic" if its leading coefficient is 1

Theorem
-------
Let f(x), g(x) be polynomials with integer coefficients, and suppose that g(x) is monic.
Then, there exists unique q(x) r(x) so that f(x) = g(x) q(x) + r(x) and 0 ≤ log(r(x)) < deg(g(x)) or r(x) = 0.

Lagrange's Theorem
------------------
Let p be prime. Suppose f(x) is a polynomial of degree n with integer coefficients and that not all of these coefficients are divisble by p.
Then, f(x) congruent to 0 (mod p) has at most n solutions (mod p).

Exam info
- Thursday, 7-8-04, 7-9PM, MATH215
- 6-8 problems
- 1-2 proofs from the book/class (know the named ones)
- 0-2 problems from the homework

------------------------------------------------------------------------------

f(x) congruent to 0 (mod p)
if deg(f) = n, then it has at most n solutions
We may use Fermat's Theorem to assume deg(f) ≤ p-1 (mod p)
If f(x) = a[n]x^n + a[n-1]x^(n-1) + ... a[0] and if k is the largest integer with p not dividing a[k], then f(x) has at most k roots (mod p)
Suppose that p doesn't divide any a[k]. If a[n] != 1, we can choose some b with ba[n] congruent to 1 (mod p). That makes bf(x) "monic modulo p".

Chebyster's Theorem
-------------------
Let p be a prime and f(x) a monic polynomial of degree n, with n ≤ p.
We can write x^p - x = f(x)q(x) + r(x) with r(x) = 0, or deg(r(x)) < n (by the division algorithm).
Then, f(x) has n roots (mod p) if and only if every coefficient of r(x) is divisible by p, meaning r(x) congruent to 0 (mod p).

Proof
-----
r(x) = r[k]x^k + r[k-1]x^(k-1) + ... r[0], with p | r[i] for i = 1, 2, 3, 4, 5, ... k.
Since x^p - x = f(x)q(x) + r(x), we have x^p - x congruent to f(x)q(x) mod (p).
By Fermat's Theorem, f(x)q(x) now has p roots (mod p).
So, for any a, p | f(a)q(a), so p | f(a) or p | q(a). Since deg(q(x)) = p - n, q(x) has at most p-n roots.
So, this implies that f(x) has at least n roots (mod p), so it must have exactly n roots (mod p).

Suppose f(x) congruent to 0 (mod p) has no solutions (mod p). Let a[1], a[2], a[3], ... a[n] be these solutions.
Since x^p - x congruent to 0 (mod p), we have a[i]^p - a[i] congruent to 0 (mod p) for all i.
Therefore, 0 congruent to a[i]^p - a[i] congruent to f(a[i])q(a[i]) + r(a[i]) congruent to r(a[i]) (mod p).
So, r(x) congruent to 0 (mod p) has at least n roots. If r(x) != 0, then r(x) is a polynomial of degree k < n, with more than k roots (mod p).
So, by Lagrange's Theorem, r(x) must be the zero polynomial modulo p.

------------------------------------------------------------------------------

Corollary (4.8)
---------------

Suppose p is prime and d | p-1. Then, x^d - 1 congruent to 0 (mod p) has exactly d roots.

Proof
-----
Write p-1 = kd. x^p - x = (x^d - 1)f(x) + r(x), then p divides all coefficients of r(x).
x^p - x = x(x^(p-1) - 1) = x((x^d)^k - 1) = x(x^d - 1)(x^d(k-1) + x^d(k-2) + ... x^d + 1), so Chebyster's theorem gives d solutions.

------------------------------------------------------------------------------

Now, we want to solve f(x) congruent to 0 (mod p^k)

Lemma
-----
Let p be prime and k > 0. Then, for any x and t, f(x + (p^k)t) congruent to f(x) + f'(x)((p^k)t) (mod p^(k+1)).

Proof
-----
Use induction on degree of f. Suppose deg(f(x)) = 0. Then, f(x) = a[0] and f(x + ((p^k)t)) = a[0] = f(x) + f'(x)((p^k)t) since f'(x) = 0.
Now suppose this statement holds for all polynomials of degree less than or equal to n. Let deg(f) = n+1.
So, f(x) = a[n+1]x^(n+1) + ... a[0] = x(a[n+1]x^n + ... a[1]) + a[0] = x(g(x)) + a[0], with deg(g(x)) = n.
f(x + ((p^k)t)) = (x + ((p^k)t))(g(x + ((p^k)t)) + a[0] congruent to (x + ((p^k)t))(g(x) + g'(x)((p^k)t)) + a[0] (mod p^(k+1)).
So, f(x) = (xg(x) + a[0]) + (xg'(x) + g(x))((p^k)t). f'(x) = xg'(x) + g(x). Therefore, we get f(x + ((p^k)t)) congruent to f(x) + f'(x)((p^k)t) (mod p^(k+1)).

------------------------------------------------------------------------------

Theorem (4.10)
--------------
Let p be a prime and k > 0. Suppose f(s) congruent to 0 (mod p^k).

(i) Hensel's Lemma: If p doesn't divide f'(s), then there is precisely one solution s[k+1] to f(x) congruent to 0 (mod p^(k+1))
with the property s[k+1] congruent to s (mod p^k). Moreover, s[k+1] = s + ((p^k)t) where t is the unique solution to
f'(s)t congruent to -f(s)/p^k (mod p).

(ii) If p | f'(s) and p^(k+1) | f(s), then there are p solutions, s[1], s[2], ... s[p] of f(x) congruent to 0 (mod p^(k+1)),
with s[t] congruent to s (mod p^k), meaning s[t] = s + ((p^k)t), t = 0, 1, 2, ... p-1.

(iii) If p | f'(s) but p^(k+1) doesn't divide f(s), then there is no solution c to f(x) congruent to 0 (mod p^(k+1)) with c congruent to s (mod p^k).

Example:
--------
f(x) = 6x^3 + 13x^2 + x - 2
f(x) congruent to 0 (mod 25)
f(x) congruent to 0 (mod 5) yields x congruent to 2 or 3 (mod 5)
f'(x) = 18x^2 + 26x + 1, which is congruent to 3x^2 + x + 1 (mod 5)
s = 3
f'(3) = 3(3^2) + 3 + 1 and is congruent to 1 (mod 5)
p doesn't divide f'(s), so there is a unique solution
f'(s)t congruent to -f(3)/5
f(3) = 280, f(3)/5 congruent to 1 (mod 5)
t congruent to -1 (mod 5)
t congruent to 4 (mod 5)
s' = 3 + 5*4 = 23

Proof of Theorem 4.10
---------------------
Suppose f(c) congruent to 0 (mod p^(k+1)) and c congruent to s (mod p^k)
c = s + (p^k)t
From Lemma 4.9, f(c) = f(s + (p^k)t), which is congruent to f(s) + f'(s)(p^k)t (mod p^(k+1)), so (f(s))/(p^k) + f'(s)t congruent to 0 (mod p).
This can be rewritten as f'(s)t congruent to -(f(s))/(p^k) (mod p)
If p doesn't divide f'(s) (which is the coefficient on t, essentially), then there is a unique solution t to f'(s)t congruent to -(f(s))/(p^k) (mod p)
If p does divide f'(s), then it becomes 0 congruent to -(f(s))/(p^k) (mod p), so the righthand side must be divisible by p,
meaning that f(s) must be divisible by p^(k+1). If not, there cannot be any solutions.

Corollary
---------
Let p be prime and k > 0. If s[1] is a solution to f(x) congruent to 0 (mod p), and p doesn't divide f'(s[1]),
then there is exactly one solution s[k] of f(x) congruent to 0 (mod p^k) with s[k] congruent to s[1] (mod p).
Proof is by induction with iteration through and Theorem 4.10

Example
-------
f(x) = x^3 + 3x + 1
f'(x) = 3x^2 + 3
f(1) congruent to 0 (mod 5)
f'(1) not congruent to 0 (mod 5)
There is a unique solution s[k] to x^3 + 3x + 1 congruent to 0 (mod 5^k)

------------------------------------------------------------------------------

Theorem (given that p doesn't divide a)
---------------------------------------

Congruences of the form x^2 congruent to a (mod p^k) have either 2 or no solutions, according to whether x^2 congruent to a (mod p) is solvable of not

Proof
-----
If there is a solution s such that (s^2) congruent to a (mod p), then ((-s)^2) congruent to a (mod p) since s^2 = (-s)^2 for all s.
Since (a,p) = 1, (s,p) = 1, meaning that -s isn't congruent to s (mod p), so the solutions are distinct.
We can treat it as f(x) = x^2 - a and solve for f(x) congruent to 0, f'(s) = 2s, p doesn't divide 2s, so there is a unique s from Theorem 4.11.

------------------------------------------------------------------------------

Definition
----------
If a not congruent to 0 (mod m), then a is a "quadratic residue" (mod m) if x^2 congruent to a (mod m) has a solution.

Theorem 4.14
------------

Let a be odd.
(i) x^2 congruent to a (mod 2) has a unique solution
(ii) x^2 congruent to a (mod 4) has 2 solutions if a is congruent to 1 mod 4 and no solutions if a is congruent to 3 mod 4
(iii) If k≥3, then x^2 congruent to a (mod 2^k) is solvable if and only if a is congruent to 1 (mod 8), with 4 solutions.
If s^2 congruent to a (mod 2^k), then all solutions are 0 ± s ± 2^(k-1) (mod 2^k)

Proof
-----
(i) a congruent to 1 (mod 2), so there's the solution x congruent to 1 (mod 2)
(ii) Since a is odd, we either have a congruent to 1 (mod 4) or a congruent to 3 (mod 4).
Since 1^2 congruent to 3^2 congruent to 1 (mod 4), we have 2 solutions if a congruent to 1 (mod 4) and none if a congruent to 3 (mod 4)
(iii) If x is 1, 3, 5, or 7, then x^2 congruent to 1 (mod 8). So, if x^2 congruent to a (mod 2^k), then x^2 congruent to a (mod 8), a congruent to 1 (mod 8).
Suppose 1 ≤ b < a ≤ 2^(k-2), a and b odd. Suppose b^2 congruent to a^2 (mod 2^k). So, 2^k | (a^2 - b^2), so 2^k | (a - b)(a + b).
Either (a + b) or (a - b) is divisible by 4, while the other is divisible by 2 but not 4. Since 2^2 doesn't divide one of the factors, 2^(k-1) divides the other.
This is impossible, however, since 1 ≤ a + b < 2^(k-1) and 1 ≤ a - b < 2^(k-2).

x^2 congruent to a (mod m)