Polynomials - Sethuraman Chapter 5.

1. Prove that the "standard algorithm for long division" is correct. By this time in the course you should understand that just an example won't suffice. You need to start with two arbitrary positive integers m and n and show how to use the algorithm to compute q and r such that n = q*m + r and r < m. You'll have to begin by representing n and m explicitly in base 10 notation.

2. In class we discussed the standard algorithm for long division with remainder for monic polynomials with coefficients in a ring R. If the ring is a field then we don't need to worry about the restriction that the polynomial be monic, since we can always multiply through by the reciprocal of the leading coefficient to make the polynomial monic. Recall that long division with remainder was just what we needed to as an ingredient in the Euclidean algorithm. That's where we're going now, for polynomials. Let

   	f(x) = x6 + x4 + x + 1
   	g(x) = x5 + x4 + x3 + x2 + x + 1
   

   1. Think of f and g as polynomials in the ring Z₂[x]. That is, deal with their coefficients as integers modulo 2.

      • Compute the quotient and remainder polynomials when you divide f by g.

      • Continue the Euclidean algorithm, at each step using the previous g(x) as the new f(x) and the previous remainder as the new g(x), just as we did for integers. Use this procedure to find the polynomial that's the greatest common divisor d(x) of the original two polynomials.

      • Work the Euclidean algorithm backwards (as we did for integers) to express the polynomial d(x) as a combination of f(x) and g(x) with polynomial coefficients. That is, find polynomials a(x) and b(x) such that

        	a(x)f(x) + b(x)g(x) = d(x)
        

   2. Repeat the previous computations, this time assuming that the coefficients come from Z₃.

3. The fundamental theorem of arithmetic - for polynomials.

   Suppose F is a field. Let R = F[x] be the ring of polynomials in the variable x with coefficients in the field F. We'll call a polynomial g(x) prime (the standard word is irreducible) if it has no factors of degree lower than itself. That allows us to factor 6x 6*x or 3*(2x) or even 30x*(1/5) without having to count those as "real" factorizations - so 6x is prime. In fact, any linear polynomial (polynomial of degree 1) is prime.

   Go back to your notes from the first weeks of class and review how we proved the fundamental theorem of arithmetic, starting from the Euclidean algorithm and what we could deduce from it about greatest common divisors. Then prove the fundamental theorem of arithmetic for polynomials:

   When F is a field, every polynomial in F[x] can be written uniquely as a product of irreducible polynomials, where "uniquely" means "up to rearranging the order of the factors and inserting and removing constant factors."

4. Solving equations.

   1. Show that when n is prime every linear polynomial ax + b (a!= 0) in Z_n[x] has exactly one root. (Do carefully what you do casually in Algebra 1 when you learn to "solve a linear equation".)

   2. You all know the quadratic formula for the roots of the quadratic equation ax2 + bx + c :

      	-b +- sqrt( b2 - 4ac )
      	---------------------
                      2a
      

      - but may never have thought seriously about why its true. Think about that now - starting with some empirical investigations. Make conjectures and prove what you can.

      • For which rings Z_n[x] can you even write it down for all quadratics? For some quadratics?

      • When you can write it down, does it always produce roots of the quadratic?

      • When you can write it down, does it always produce all the roots of the quadratic (remember that sometimes some quadratics may have more than two roots).

5. Counting roots. We saw in class that in Z₈[x] the polynomial x²-1 had four roots: 1, 3, 5 and 7 (or, if you prefer, +-1 and +-3). Then I proposed some possible homework problems along these lines. Here they are (revised).

   We will prove that when n is prime, a polynomial in Z_n[x] never has more roots than its degree. Here you investigate what happens when it's not.

   • Show that if n is composite, there is at least one linear polynomial in Z_n[x] that has more than one root.

   • Suppose n is composite. Is there at least one quadratic polynomial with more than two roots?

     I do not know the answer to this question (yet). It might be "yes" for all composite n. It can't be "no" for all composite n since we know the answer is "yes" when n=8. If the answer is "sometimes yes sometimes no" try to figure out just when it's "yes". Conjecture first, then prove what you can.

From: Ethan Bolker 
To: "John Bussey" 
Cc: , , ,
        , ,
        , ,
        , ,
        , 
Subject: Question 2a, Second Bullet Point
Date: Mon, 27 Mar 2006 08:45:31 -0500 (EST)

 > 
 > Question 2a, second bullet point, has to do with applying the Euclidean
 > Algorithm in reverse on the polynomials f(x) and g(x).  The problem
 > explains that the point is to find some a(x) and b(x) such a(x)f(x) +
 > b(x)g(x) = d(x).  But what is d(x), again?  Is it the least common
 > multiple of f and g?

d(x) is the greatest common divisor of f(x) and g(x) - just what it
says in the text: "the greatest common divisor d(x)". So I don't have
other words for it.

"greatest common divisor" and "least common multiple" are not the
same, although most people think they are, or at least use the second
phrase when they mean the first. The greatest common divisor of 9 and
15 is 3. The least common multiple is 45. It's the least common
multiple you need if you want to add fractions with denominators 9 and
15. But it's the greatest common divisor that's the more interesting
and the more useful when you're studying number theory and algebra as
opposed to learning arithmetic.

 > On that same problem, is going to involve a huge amount of calculation
 > multiplying polynomials?  In the way I'm starting it, it seems like the
 > first thing I have to do is get the product of f and g.  If that's how
 > it has to be done, it's not a problem.  But is that right?

Why would you want to multiply f(x) and g(x)? Just because you can?
The point of this example is to ask you to think about (remember) what
we did when we learned how to find the greatest common divisor (not
the least common multiple) of two ordinary integers - say, 9 and
15. The Euclidean algorithm doesn't start by multiplying 9 and 15, it
starts this way:

       15 = 1 * 9 + 6
       ...

Yes, you will need to do some polynomial arithmetic to work this out.
Whether that qualifies as "huge" I don't know. Remember that the
coefficients are mod 2 or mod 3, so there's not much to keep track of
there.