MSU MATHEMATICS

MTH 418H
Honors Algebra I

Fall 2005

Main Course Page
Old Announcements
- Midterm Test 1: Fri, Oct 14, in class. Arrive 5 min early. Topics: Z, Q,R, the polynomial rings Q[x] and R[x], and general ring definitions. The test will not cover C. It will consist of problems applying the theorems and lemmas we have covered, proving simple consequences of the axioms and definitions, and applying the main algorithms.Prepare by reviewing the lecture notes, quizzes, and homework.
- Grade Policy Change: I will drop your lowest score in computing the overall Weekly Quiz grade (which is 20% of your total grade).
- Midterm Test 2: Wed Nov 16, in class.Arrive 5 min early. Topics: Complex numbers, complex and real polynomials, field plots, analytic functions, line integrals,Cauchy Vanishing & Mean Value Theorems, Newton's Method,Fundamental Theorem of Algebra. Prepare by reviewing the Lecture Notes, the quizzes (for more computational problems), and the homework below (for moretheoretical problems). .
Old Homework: Feel free to hand in old Extra Credit problems at any time during the course, no matter when they were posted. Exercise and page numbers refer to the Artin text.
- HW 9/2: Oral quiz. Notes 8/29,8/31.
  1. Derive the Quadratic Formula for solving an equationax² + bx + c = 0 by completing the square:i.e., by writing (ax² + bx + c)/a = x² + (b/a)x + c/a = (x+d)² - d² + c/a for an appropriate d, then setting the last expression equal to 0.
  2. Give a complete proof that √3 is irrational, using only elementary properties of the integers. (Do not assume the Fundamental Theorem of Arithmetic.) Can you extend this to show that √p is irrational for any prime p?
  3. In class we described how projecting from the point (-1,0) gives a geometric correspondence (stereographic projection) between the circle x² + y² = 1 and the line x = 1 . Use this to give a general formula which produces all Pythagorean triples of whole numbers (a,b,c) with a² + b² = c², and show that all such triples really do come from your formula.
- HW 9/9: Written quiz: Euclidean algorithm. Hand in Ex 1 below. Notes 9/7, 9/9.
  1. Proposition: If n/m is a fraction in lowest terms (meaning gcd(n,m) = 1), and (n/m)^1/2 (the square root of n/m) is a rational number, then n and m are perfect squares (meaning √n and √m are integers). Give a complete proof, assuming the Fundamental Theorem of Arithmetic.
  2. Use the Euclidean Algorithm to determine the greatest common divisor d = gcd(3587,1819). Then use back-substitution to write d = 3587n + 1819m for some integers n,m.
  3. Sieve of Eratosthenes. Use the following method to find all the prime numbers less than 100. Write a list of all the numbers 2,3,4,...,100, circle the first number (which is 2) and cross out all multiples of 2. Circle the first uncrossed number (which is 3) and cross out all multiples of it. Repeat until all further numbers are crossed out. The circled numbers are the primes. You can use a print-out of this table.
    Extra Credit: Show that all non-primes have been crossed out once you get to a prime p > √n .
  4. Extra Credit: Let π(x) be the number of primes p ≤ x . The amazing Prime Number Theorem (which we won't prove in this course) states that π(x) tends toward x / log(x) as x→∞, in the sense that the percentage error tends to zero. (Here log means natural logarithm, base e.) Make a graph or table of the functions π(x) and x / log(x) for x ≤ 100 , and verify that the percentage difference between the two gets smaller. What does the Prime Number Theorem say about the density of prime numbers in a large interval {1,2,...,n}, and how well does this hold up for n ≤ 100? What else can you say about the set of prime numbers (which I have not said in class)?
  5. Extra Credit: The sequence of primes is quite mysterious. Could there be a "formula for primes", meaning a fairly simple function f(n) whose values f(1), f(2), f(3),... are all prime? For example, the polynomial f(n) = 1 + n + n² gives f(1) = 3 , f(2) = 7 , f(3) = 13 , but f(4) = 21 = 3×7, so this does not work. Could any polynomial f(n) = a₀ + a₁n + ... + a_dn^d work? What else can you say about this question?
  6. Extra Credit: Show that if p is a prime with p|a², then p|a. (This was the tricky point in proving that √p is irrational.) Give as simple a proof as possible: don't assume our key lemma on primes (if p|ab then p|a or p|b).
  7. Extra Credit: Try to discover proofs of two famous theorems about primes p:
    1. Wilson's Theorem: p | (p-1)! + 1 , where (p-1)! means p-1 factorial.For example: 5 | (4! + 1) = 25 .
    2. Fermat's Little Theorem: p | n^p - n for any n . For example: 5 | (2⁵ - 2) = 30 .
  8. Extra Credit: Can you show that the only positive integer solution to a² + 2 = b³ is (a,b) = (5,3) ?
- HW 9/16 Quiz: Euclidean algorithm for polynomials. Notes: 9/12,9/14. References: Artin Ch 10.1, 11.1, 11.2.
  1. Euclidean algorithm on polynomials. Considerthe following polynomials in Q[x]:f(x) = 2x⁵ + x⁴ - 3x³ - 3x² + 1 g(x) = 2x⁴ - x³ - 6x² - x + 2
    1. Find the polynomial gcd( f(x), g(x) ) .
    2. Write gcd( f(x), g(x) ) = m(x)f(x) + n(x)g(x) for some m(x), n(x).
    3. Factor f(x) and g(x) into irredicible polynomials in Q[x](the analog of prime numbers). Hint: Look for linear factors (x - a).
  2. Consider the ring Z₁₂ defined by clock arithmetic: on a 12-hour clock, 13 o'clock is the same as 1 o'clock, which we write as 13 ≡ 1 (mod 12); and in general i ≡ i + 12k (mod 12). Adding hours on this clock, we get 10 + 6 = 16 ≡ 4 and 5 ×3 = 15 ≡ 3 (mod 12).
    Similarly, we define the ring Z_n of integers modulo n as the integers Z, but with i and i + nk identified (considered the same) for all integers i and k . We write this as: i ≡ i + nk (mod n) , or just i = i + nk ∈ Z_n . Thus, there are n distinct elements in Z_n , namely 0,1,2,...,n-1, each of which represents a class of equivalent integers (mod n). Since addition and multiplication of these classes satisfies the axioms, Z_n is a commutative ring.
    For example, in Z₃ we have 1 + 1 + 1 = 0 and2 × 2 = 4 = 1, so 1/2 = 2.
    Problem: Of the types of rings listed in my Definitions Handout, find the strongest description that applies to the following rings: for example Z is a Euclidean ring (and hence a domain, and a commutative ring). Find the units and zero-divisors in each case.
    (a) Z₂ (b) Z₃ (c) Z₄ (d) Z_n for each n
    (e) Z₂[x], polynomials with coefficients in Z₂
    (f) M₂(R), the 2×2 matrices with real entries (usual matrix + and ×)
    (g) M₂(Z₂), the 2×2 matrices with entries in Z₂ .(How many such matrices are there?)
    (h) Extra Credit: Z[x], polynomials with integer coefficients. Euclidean? (Is there division algorithm?)
    (i) Extra Credit: For M_n(R), the n×n matrices over the reals R (or over any field), the zero-divisors are exactly the singular matrices (det = 0).
  3. Prove the following:
    (a) A field is always a domain.
    (b) A commutative ring R is a domain if and only if the Cancellation Law holds in R: that is, for any a,b,c in R , ab = ac implies that b = c or a = 0 .
  4. Let R be a domain, and define a field F = { (a,b) such that a,b ∈ R , b ≠ 0 }where the pair (a,b) is supposed to represent the fraction a/b. Define the operations:(a,b) + (c,d) := (ad + bc , bd) (a,b)•(c,d) := (ac , bd) .Show that these operations really do satisfy the field axioms (i)--(iv), (i')--(iv'), (v). Also show that the elements of the form (a,1) make a copy of R inside F. Thus, we may consider F as the smallest field containing R.
- HW 9/23 Quiz: Finding roots, Rational Root Test. Notes: 9/19, 9/21.
  1. Re-submit your proof about the square root of m/n to gain credit. Also hand in your original submission. Revise according to my editorial comments, and make sure to state the result to be proved; to state any assumptions you make in the course of the proof (such as a fraction being in lowest terms); to explicitly cite any needed results from the lecture; and to prove any assertions which were not in the lecture (such as gcd(a,b)=1 and a|bc implying a|c).
  2. Explicitly find all the roots of the polynomial 3x³ - 7x² - 12x - 4 . Use the Rational Root Test: if f(x) = a_nxⁿ + ... + a₁x + a₀ ∈ Z[x] and x = c/d or -c/d is a root of f(x) for some rational number c/d in lowest terms, then c | a₀ and d | a_n.
  3. Give a careful proof of the Rational Root Test for a polynomial of degree one: f(x) = a₁x - a₀ . Show why the statement is false (and your proof does not apply) if c/d is not in lowest terms.
  4. Prove that the integer polynomials Z[x] could not possibly be a Euclidean ring, since gcd(2,x) = 1, but there are no integer polynomials n(x), m(x) such that 2 n(x) + x m(x) = 1 .
  5. Factoring polynomialsShow that for an integer m, the k^th root m^1/k is rational if and only if m is a perfect k^th power, i.e., m = r^k for some integer r.Hint: Apply the Rational Root Test to f(x) = x^k-m .Also: Can you use this strategy to show that (m/n)^1/k is irrational unless m and n are perfect k^th powers?
  6. Extra Credit: For any problem about integers, we can ask the analogous problem about polynomials in Q[x] . For example, can you find all polynomial solutions a(x), b(x), c(x) ∈ Q[x] of the equation a(x)² + b(x)² = c(x)² ? Or consider: there are infinitely many primes in Z; prove that there are irreducible polynomials of arbitrarily high degree (or of every single degree) in Q[x] . Think of your own examples.
- HW 9/30 Oral Quiz: Previous two weeks' HW. Notes: 9/28.
  Let F be any field. Prove the following formulas, using only the field axioms and the simple lemmas in the notes.
  1. FOIL: (a+b)(c+d) = ac + ad + bc + bd . This holds in any commutative ring, not necessarily a field.
  2. Quadratic formula: Let f(x) = ax² + bx + c ∈ F[x]. Then the only roots of f(x), meaning values r∈F with f(r) = 0 , are r = (-b±d) / 2a , where d ∈ F is an element with d² = b² - 4ac . If there is no such element d ∈ F , then f(x) has no roots in F.
  3. Binomial Theorem: (a+b)² = a² + 2ab + b²
    (a+b)³ = a³ + 3a²b + 3ab² + b³
    (a+b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴
    (a+b)ⁿ = aⁿ + (n|1)a^n-1b + (n|2)a^n-2b² + ... + bⁿ
    where the binomial coefficients (n | k) are defined recursively by:(n | 0) = (n | n) = 1 and (n+1 | k) = (n | k) + (n | k-1)Again, this holds in any commutative ring.
  4. aⁿ - bⁿ = (a - b) (a^n-1 + a^n-2b + ... + ab^n-2 + b^n-1)
- HW 10/7 Quiz: Continuous functions, Intermediate Value Theorem.Notes: 10/3, 10/10.
  Hand in: HW 9/30 #2, Quadratic Formula in any field.
  1. Let R be an ordered ring, meaning: if a < b and c is arbitrary, then a+c < b+c ;if 0 < a < b and 0 < c , then ac < bc ; and for any a we have exactly one of: a < 0 , a = 0 , or a > 0 . Then prove the following:
    1. If a < b and c < d , then a+c < b+d .
    2. If a < b and b < c , then a < c .
    3. If a > 0 , then -a < 0 .
    4. If a, b < 0 , then ab > 0 .
  2. Prove that if a commutative ring R satisfies either of the following conditions, then there is no possible order relation on R.
    1. R contains an element with a² = -1 . (Thus, the complex numbers R = C cannot be ordered.)
    2. A repeated sum of 1 with itself n times gives zero: 1+...+1 = 0 . (Thus, the clock-arithmetic ring R = Z_n cannot be ordered.)
  3. We have seen that the field of rational numbers Q is not topologically complete. Show that the ring of integers Z is topologically complete.
  4. In our construction of R, we defined a real number as a cutset S ⊂ Q which is a down-set (if s ∈ S and t ≤ s , then t ∈ S); which is neither empty nor all of Q; and which has no maximal element (if s ∈ S, then there is some t ≥ s with t ∈ S).
    Inequality < was defined to be strict containment of cutsets, S ⊂ T .
    Problem: complete our proof of the Topological Completeness of R. That is, suppose we have a set of real numbers A ⊂ R with an upper bound B ∈ R : that is, a collection of cutsets S ∈ A and a large cutset B which covers A, so that S ⊂ B for every S ∈ A. Now define C = U_{S ∈ A} S , the union of all the cutsets in A. Then show that:
    1. C really is a real number, meaning a cutset
    2. C is an upper bound of A ;
    3. C is less than or equal to any upper bound B of A .
  5. Recall that we defined a function f(x) from R to R to be continuous at x = a if a small change in x produces a small change in f(x): that is,
    for every ε>0, there is a δ>0 so that x ∈ [a-δ, a+δ] guarantees f(x) ∈ [f(a)-ε, f(a)+ε].
    Here we should think of δ as an x-error tolerance which guarantees a prescribed y-error tolerance ε
    1. Show that a value v is in an error-window [c-ε, c+ε] if and only if |v-c| ≤ ε . Reformulate the definition of continuity in this notation.
    2. Triangle inequality: Show that |a+b| ≤ |a| + |b| for real numbers a,b.
    3. Prove that f(x) = x and f(x) = const are continuous functions, by prescribing a δ for each ε.
    4. Prove that if f(x), g(x) are functions continuous at x = a, then f(x) + g(x) and f(x)*g(x) are also continuous at x = a, and so is 1/g(x) if g(a) ≠ 0.
      Hint: The first should go like this. Given f(x), g(x) continous at x = a, and an error tolerance ε>0, take δ small enough that |x-a| ≤ δ guarantees |f(x)-f(a)| ≤ ε/2 and |g(x)-g(a)| ≤ ε/2 . This is possible because we can meet the y-error tolerance ε/2 for f(x) and for g(x) by choosing sufficiently small x-error tolerances δ₁ and δ₂ : let our δ be the minimum of these two. Now |x-a| ≤ δ guarantees:|f(x)+g(x)-f(a)-g(a)| = |f(x)-f(a)+g(x)-g(a)| ≤ |f(x)-f(a)| + |g(x)-g(a)| ≤ ε/2 + ε/2 = εThe other two are harder.
  6. Use the Intermediate Value Theorem to prove that the polynomial f(x) = x³ - 5x + 1 has three real roots f(c) = 0.
    Determine these roots to an accuracy of 1 decimal place by finding a < b with b-a < 1/10 and f(a) < 0 < f(b) (or vice versa); then there is a root c ≈ ½(a+b), accurate to 1 decimal place.
- HW 10/21: Quiz: Picturing complex number operations. Notes 10/17,10/19.
  1. Recall that we defined the complex numbers C as all pairs of real numbers (a,b) ∈ c² with the operations (a,b) + (c,d) = (a+c, b+d) , (a,b) * (c,d) = (ac-bd, ad+bc) .Verify that this defines a field by directly checking the field properties. For example, multiply out to check that (a,b) * ( (c,d)*(e,f) ) = ( (a,b) * (c,d) ) * (e,f) and that (a,b)^-1 = ( a/(a²+b²) , -b/(a²+b²) ) .
  2. Recall that we identified each real number a ∈ R with (a,0) ∈ C, and we defined i = (0,1) , with i² = -1 , so that (a,b) = a + b*i . Henceforth, we will write complex numbers as a+bi with a,b ∈ R.
    1. Show that every real quadratic equation, ax² + bx + c = 0 with a,b,c ∈ R , has a solution in C .
    2. Show that every complex number a+bi has a complex square root. Hint: Write out (c+di)² = a+bi , set the real and imaginary parts equal on the two sides, and solve the system for the real numbers c,d.
    3. Show that every complex quadratic equation ( a,b,c ∈ C ), has a solution in C .
  3. Matrix representation of C
    1. Add and multiply two matrices of the form
      a -b
      b a
      to verify that they form a copy of the complex number field C inside the ring of 2 × 2 matrices with real entries, M_2×2(R) . Formally, this means that if we define the map φ : C → M_2×2(R) by setting φ(a+bi) equal to the above matrix, then φ is a morphism of rings. Note that M_2×2(R) is not a commutative ring nor a division ring, but the subset consisting of the above matrices is actually a field, isomorphic to C .
    2. Show that the complex conjugate corresponds to transpose of matrices, and the norm or length of a complex vector is the square root of the determinant of the corresponding matrix.
    3. Extra Credit: Let us try to form a "hypercomplex" number system consisting of matrices of the above form with complex number entries a,b ∈ C . Show that these matrices form a commutative ring but not a field.
    4. Extra Credit: On the other hand, consider complex matrices of the form:
      a -b
      b a
      where a,b ∈ C and a means the complex conjugate. Show that these matrices form a division ring but not a field. This ring is called the quaternions, usually denoted H, a fascinating number system which relates to three dimensions much as complex numbers relate to two dimensions. I can suggest you more exercises on them if you are interested.
  4. Recall that for a complex number α = a + bi , its complex conjugate is α = a - bi and its norm or length is ||α|| = √(a² + b²). Show that the norm is multiplicative: ||αβ|| = ||α|| ||β|| . Hint: Use ||α||² = αα .
  5. Draw α = 1 + 3i as a vector in the complex plane. Now compute the coordinates and draw pictures for the following: 2α , -α , α , α² , α³ , α⁵ , ±√α , ³√α .You might not be able to compute cube root exactly, but at least approximate it. Also, remember there are three cube roots of a complex number.
- HW 10/28: Quiz: Complex functions. Notes 10/24.
  1. Given a function f : C→C , f(a+ib) = u(a,b) + iv(a,b) , we say f is complex analytic (or just analytic) if any of the following conditions holds:
    1. The matrix of partial derivatives, Df =
      u_x u_y
      v_x v_y
      is a complex multiplication matrix, satisfying the Cauchy-Riemann equations v_x = -u_y and v_y = u_x .
    2. The gradient vector fields ∇u = (u_x, u_y) and ∇v = (v_x, v_y) are 90° rotations of each other. Thus, the level curves u(x,y) = const and v(x,y) = const are perpendicular to each other at their points of intersection.
    3. There is a well-defined complex number given byf '(a+ib) = lim_ε→0( f(a+ib+ε) - f(a+ib) ) / ε= lim_ε→0( f(a+ib+iε) - f(a+ib) ) / iε
    Show that conditions (a)--(c) are equivalent, and they imply:
    d. u(x,y) is a harmonic function: it satisfies u_xx + u_yy = 0 , where u_xx means second derivative in the x-direction. Likewise for v(x,y).
  2. Draw vector field pictures and compute real and imaginary components u(x,y) and v(x,y) for the functions f(z) = α ; f(z) = αz (choose a specific α∈C for the picture); f(z) = z² ; f(z) = z² + 1 . In each case verify that the components satisfy the Cauchy-Riemann equations, making f(z) analytic, and compute the derivatives. Extra Credit: Draw the level curves of u(x,y) and v(x,y) for these functions, and verify that they are perpendicular.
  3. Show that if f(z) and g(z) are analytic, then so are their sum, difference, and quotient (if g(z)≠0). Using definition (c) above, compute that (f+g)' = f' + g' , (fg)' = f 'g + fg' , and (f/g)' = (f 'g-fg')/g². Conclude that every polynomial function is analytic at all z∈C, and every rational function is analytic whenver g(z)≠0.
- HW 11/4: Quiz: Compute line integrals, circulation ∫_C g(c)•dc , flux ∫_C g(c)×dc , and complex ∫_C f(z) dz . Notes 10/31,11/2.
  These problems leads you through the line integrals we will use to prove the Cauchy Integral Formula, the Mean Value Inequality, and ultimately the Fundamental Theorem of Arithmetic.
  1. Show that the product of two complex numbers αβ = α•β + i α×β, where • means dot product and × means cross product of plane vectors.
    Recall that for vectors v₁ = (x₁,y₁) , v₂ = (x₂,y₂), the dot and cross products are: v₁•v₂ := x₁ x₂+ y₂ y₁ , v₁×v₂ := x₁ y₂- x₂ y₁ .Geometrically, the dot product is the product of the lengths of the two vectors times the cosine of the angle between them.The cross product is the product of the lengths of the two vectors times the sine of the angle between them: this is the area of the parallelogram spanned by the vectors .
  2. Let C be a closed curve in the complex plane C = R². The circulation of a vector field g(x,y) around the curve C is defined by taking a list of sample points c₀, c₁,..., c_n = c₀ counterclockwise around C, and computing:∫_C g(c)•dc := lim_n→∞ ∑_j=1ⁿ g(c_j) • (c_j - c_j-1) ,where we take the limit of more and more points densely distributed along C.
  3. Explain why this measures the strength of the net counterclockwise rotation of the flow associated to f around the curve C. Hint: the dot product of two vectors is the product of their lengths times the cosine of the angle between them.
  4. If C is parametrized by a function c(t) = (x(t),y(t)) for a≤t≤b and g(x,y) = (r(x,y),s(x,y)), we can compute circulation as an ordinary integral:∫_C g(c)•dc = ∫_a^b g(c(t)) •c'(t) dt = ∫_a^b r(x(t),y(t)) x'(t) + s(x(t),y(t)) y'(t) dt ,where c'(t) = x'(t) + iy'(t) is the tangent vector at the point c(t).
    Compute these integrals over a circle C with radius r and center 0 for the vector fields given by g(x,y) = const , g(x,y) = (x,y) , and g(x,y) = (-y,x) , and verify that, as one would expect from the field plot pictures, the first and second have no circulation, while the third has positive circulation proportional to the radius r.
  5. Repeat the above exercises for the flux defined as: ∫_C g(c)×dc := lim_n→∞∑_j=1ⁿ g(c_j) × (c_j - c_j-1) = ∫_a^b g(c(t)) ×c'(t) dt.Show that this measures the net outflow of f from the region surrounded by C . Hint: the cross product of two vectors is the product of their lengths times the sine of the angle between them.
    You should find that g(x,y) = const and g(x,y) = (-y,x) have no flux, and g(x,y) = (x,y) has positive flux.
  6. Finally, consider a complex analytic function f(z), and parametrize the curve C by a function c(t) = x(t) + iy(t) , with sample points c_i . The complex line integral defined by:∫_C f(z)*dz := lim_n→∞ ∑_j=1ⁿ f(c_i) * (c_j - c_j-1) = ∫_a^b f(c(t)) *c'(t) dt ,where * indicates multiplication of complex numbers.The previous two integrals take real values, but the line integral gives a complex number. Show that:∫_C f(z)*dz =∫_C f(c)•dc + i ∫_C f(c)×dc .That is, the real and imaginary parts of the complex integral are the circulation and flux integrals for the conjugate vector field g(z) = f(z) = u(x,y) - i v(x,y) . Hint: Use Problem 1 above.
    Compute this integral for the f(z) corresponding to the g(x,y) above: f(z) = const , f(z) = z , and f(z) = -iz ; and also for f(z) = z² . Hint: The first and last should be 0, but the others non-zero. Cauchy's Integral Theorem asserts that the complex line integral is zero for any function f(z) which is analytic on the region enclosed by C.
- HW 11/11: Quiz: Newton's Method. Notes 11/7.
  1. Use Newton's Method to approximate the three real roots of the real polynomial f(z) = z³ - 3z + 1 .Use two methods to find all the roots:
    a. Vary the initial guess z₀ until you get convergence to three different values
    b. Find one approximate root r, find the quotient g(z) = f(z)/(z-r) (ignorining the tiny remainder), and apply Newton's Method to g(z). Repeat for the last root.
  2. Explore Newton's Method for f(z) = z³ - z . Here the roots are obvious, but for each real value z, determine what happens if you take that value as the initial guess: to which root does the algorithm converge? Is there any initial guess which fails to converge?
  3. Approximate the complex roots of the complex polynomial f(z) = z² + iz - i to 1 decimal place in each component. Draw the field plot near each root z = r , which locally looks like the vortex g(z) = f '(r) (z-r) . Then interpolate arrows between the vortexes (or vortices).

u_x	u_y
v_x	v_y

MSU MATHEMATICS

MTH 418HHonors Algebra I

MTH 418H
Honors Algebra I