Math 560
Spring, 2006
hw3
Solutions

In these solutions I have gone out of my way to write lots of words - both to make it easier for you to understand what I've written, and to give you a model of what I expect your own solutions to look like.

  1. In class we conjectured that Zn is a field just when n is prime. Prove that. Let me remind you that the "just when" means you have two things to prove: first that when n is not prime, Zn is not a field, and second that when n is prime every nonzero element in Zn has a multiplicative inverse and hence Zn is a field.

    First I will show that when n is not a prime, Zn is not a field. How will I go about that? Well I know that what makes a ring a field is the existence of a multiplicative inverse for every nonzero element, so if I can find just one nonzero element without a multiplicative inverse I will have done the job. Where will I find such a thing? Let me look at Z6 to see if I can get an idea about how to start. There I notice that 2*3=0, and that neither 2 nor 3 has a multiplicative inverse. That suggests to me that I might be able to prove that when a*b = n, neither a nor b will have a multiplicate inverse in Zn. I worked it out on scratch paper and I can do it! So here's the proof of the first part of the theorem:

    If n is not prime then Zn is not a field
    Proof:     Since n is not prime there are numbers a and b each less than n such that n = ab. That means that in Zn we have ab = 0 but a and b are not 0. I will show that a cannot have a multiplicative inverse. Well suppose it does, and write c for a-1. Then 

    	b = 1*b    // property of 1
          = (ca)b  // since c is the multiplicative inverse of a
	  = c(ab)  // associative law for multiplication
          = c*0    // I chose a and b so that ab=0
	  = 0      // previous theorem about rings: anything*0 = 0
    but that's a contradiction since b isn't 0. Actually, now that I've finished the proof I notice that I have proved even more than was asked for. I have actually proved that every field is an integral domain.

    Now for the second part of the theorem. Suppose n is prime. I need to show that Zn is a field. So I need to show that every nonzero element k of Zn has a multiplicative inverse. That means I must show that row k of the multiplication table for Zn has a 1 in it somewhere. That seems to be the case for all the examples, so I am hopeful. But of course just looking at a few examples doesn't prove the theorem. And there doesn't seem to be any kind of pattern about where in each row the 1 appears. So I need to think some more. Well I do know that k is less than n. Because n is prime that means k and n are relatively prime: their greatest common divisor is 1. We've spent a fair amount of time thinking about greatest common divisors. The teacher seems particularly fond of the Euclidean algorithm, so that might help here. Since gcd(k,n)=1 I know I can find integers x and y such that 

    	x*k + y*n = 1
    Aha! I will look at that equation as an equation in Zn rather than just in Z. It's still true there. But n=0 in Zn, so that equation becomes 
    	x*k = 1
    which means that x is the multiplicative inverse of k in Zn.

    That was pretty tricky. What if I hadn't thought of the Euclidean algorithm? Well here's another argument. I notice in the table for Z7 that I worked out last week that not only does every row (except row 0) contain a 1, every row (except row 0) contains one of each of the numbers 0, 1, ..., 6, with no repetitions. That's a clue. If I can show that there are no repetitions in the row k of the multiplication table for Zn then that row is just a scramble of the numbers 0, 1, 2, ... n-1 so there must be a 1 somewhere in the row, although I won't know where. So I will prove that there are no repetitions.

    Suppose that the same number c appears twice in row k. That means there are two different numbers a and b, each less than n, such that 

    	a*k = b*k = c  // in Zn
    That means 
    	(a-b)*k = 0    // in Zn
    but that can happen only when n divides (a-b)*k in the ordinary integers Z. But n is prime, so if it divides (a-b)*k it must divide (a-b) or k. It can't divide k, since k is less than n. So it must divide (a-b). But a and b are themselves each less than n, so that's impossible too unless a=b. But I assumed a and be were different, so I have the contradiction I wanted. There are no duplicate entries in row k, so there's a 1 somewhere, k has a multiplicative inverse, and Zn is a field when n is prime.

    Optional extra challenge: prove that any finite integral domain is a field.

    Solution coming soon.

  2. On pages 37 and 38 (and then again on page 60) Sethuraman discusses the ring of polynomials with real coefficients. Then he notes that there is nothing special (as far as ring theory goes) about real coefficients - the coefficients can come from any ring. We covered this in class. We write R[x] for the ring whose elements are the polynomials in the variable x whose coefficients come from the ring R.

    We know about the degree of a polynomial. In Z[x] the polynomial x2+1 has degree 2. The constant polynomial 37x0 has degree 0. In fact any nonzero constant polynomial has degree 0. What about the degree of the 0 polynomial? It's not degree 0, since the degree is supposed to be the largest exponent with a nonzero coefficient, but for the 0 polynomial there are no such exponents. There's a good reason for declaring that the degree of the 0 polynomial is -infinity (that's minus infinity. Take my word for that now.

    Let's count polynomials. Consider Z2[x]. That's the ring of polynomials whose coefficients are just 0 and 1, with the usual addition and multiplication rules except for 1+1, which is 0 and not 2. In that ring there are four polynomials whose degree is at most 1, namely 0, 1, x and 1+x.

    1. How many polynomials are there in Z2[x] with degree at most 2? at most 3? at most d?

      Eight polynomials of degree at most 2: 0, 1, x, 1+x, x2, 1+x2, x+x2, 1+x+x2.

      Note that these are just the four with degree at most 1 and then the same four with x2 added. That makes eight. So for the ones of degree at most 3 we will use these 8 and the 8 more that come from adding an x3. And so on. There are thus 2d+1 polynomials of degree at most d.

    2. Answer the same question for Z3[x], and then for Zn[x] (if you can). That is, try to find a formula involving n and d that tells you the number of polynomials in Zn[x] whose degree is at most d.

      There are 3 polynomials of degree at most 1 in Z3[x]: the constant polynomials 0, 1 and 2. To get the polynomials of degree at most 2 we use these three, the three we get by adding x and the three we get by adding 2x. So there are 9 in all. To build the polynomials of degree at most 2 we use these 9, the 9 we get by adding x2 and the 9 we get by adding 2x2. Clearly this continues: at each stage there are three times as many as at the stage before, so there are 3d+1 polynomials of degree at most d.

      It's clear that this argument works to show that there are exactly nd+1 polynomials of degree at most d in Zn[x].

    3. Explain why there are exactly as many polynomials in Zn[x] of degree at most d as there are words of length d+1 you can write using an alphabet with just n letters in it. (Words don't need to make any sense: "etaionshrdlu" is a word of length 12 using letters from our ordinary 26 letter alphabet.) (Where do you think I got that word?)

      "Explain why" is a gentle way to say "prove". It invites you to write a convincing argument, in English, with only the symbols you really need.

      While I was writing down all these polynomials I realized that the x's were important only to mark the place where a particular coefficient was placed. Any sequence of coefficients of length d+1 specifies a polynomial of degree at most d. (The degree is less than d just when the coefficient of xd happens to be 0.) When the coefficient ring is Zn you have n choices (0,1,...,n-1) for each coefficient, so nd+1 choices for a "word" of length d+1. The analogy with place value notation is striking. We write 

      	abcd
      instead of 
      	a*103 + b*103 + c*101 = d*100
      In our decimal notation there are just 10 digits (0,..9) and each "word" of length d using those letters specifies a number less than 10d.

      In fact, if you think about it (and please do), polynomial arithmetic is really easier than the adding and subtracting we teach for numbers, since there's never any carrying or borrowing. Whatever happens in the xk column stays in that column.

  3. One of the hardest things an algebra teacher needs to do is to convince his or her students that (1+x)2 is not 1 + x2.

    Prove that 

    	in Z2[x]: (1+x)2 = 1 + x2
	in Z3[x]: (1+x)3 = 1 + x3

    What happens in Z4[x] and Z5[x]? Try to find a pattern, frame a conjecture, and prove it if you can.

    We did this one in class. The theorem is: 

    	(1+x)n = 1 + xn in Zn[x] if and only if n is prime.
    The proof depends on the formula we discovered in class: the coefficient of xk in the expansion of (1+x)n is 
    	n * (n-1) * ... * (n-k+1)
	-------------------------
        k * (k-1) * ... *   1
    and the observation that when n is prime this number clearly has n for a factor since there's no way for anything in the denominator to cancel it.

  4. Suppose f and g are polynomials in R[x]. Investigate the question 
    	degree( fg ) = degree(f) + degree(g)
    Find out when it's true, and prove it when it's true.

    Can you say now why mathematicians define the degree of the 0 polynomial to be -infinity?

  5. When you studied calculus you studied power series: expressions like these: 
    	g(x) = 1 +  x +  x2 +  x3 + ...
	h(x) = 1 + 2x + 3x2 + 4x3 + ...
	f(x) = 1 +  x + 2x2 + 3x3 + 5x4 + 8x5 + ...
    Think of them as polynomials of infinite degree. When you first saw these you were probably asked to figure out when they converged. Here we won't bother! It's pretty clear how to add and to multiply power series, and that the coefficents don't need to be integers. They can come from any ring. This is an extremely powerful and interesting abstraction we can barely touch on, but it's so pretty I wanted you to see just a little bit of it. Here are some (easy?) exercises. Recall that if r is an element of a ring then we write (1/r) for the multiplicative inverse of r (if it has one). You can check whether some ring element s is equal to (1/r) by checking that r*s=1, since by definition (1/r) is the solution to the equation r*?=1

    1. The first series isn't called g by accident. It's the famous geometric series. Prove that 
      	g(x)*(1-x) = 1
      so that (in any ring whatsoever) g(x) = 1/(1-x).

    2. The third power series above has the Fibonacci numbers as coefficients, which is why I called it f. Prove that f(x) = 1/(1-x-x2) .

    3. Hard (or at least tricky) question. Find the multiplicative inverse of the second power series, h(x) above. Hint: h seems to be the derivative of the geometric series.