*Originally posted by PBE6*

**Can you give us a solution using the Chinese Remainder Theorem? I've never used it before.**

I haven't thought about commutative algebra in a while, so this is going to be pretty stream-of-consciousness, but it will work. I've defined most of the important concepts in a very quick-and-dirty way; if you're familiar with them, ignore these definitions. If not, then the explanations are pretty bad and I suggest an engooglement.

"2) Find the polynomial (over the Real numbers) of least degree, p(x), such that (x^2 + 1) divides p(x) and (x^3 + 1) divides p(x)-1."

Okay, throughout "R" means the reals, the symbol "^" means intersection of sets and R[x] is the ring of polynomials with real coefficients (a ring, roughly speaking, is a set with an addition and a multiplication -- here they are the normal addition and multiplication of polynomials). Also, observe that we can't multiply two nonzero polynomials to get 0, and that the multiplication is commutative.

In general, let q(x) and r(x) be two polynomials which have no common factors (like the two given above). Let I and J, respectively, be the

*ideals* they generate, ie the subrings of R[x] consisting of all multiples of q(x) and r(x) respectively. Then since q(x) and r(x) have no common factors, the only elements in I^J are multiples of qr(x): if s(x) is in I and J, then s(x) = t(x)q(x) = u(x)r(x). Thus tq(x) is divisible by r(x), so since q and r have no common factors, t(x) must be divisible by r(x), ie t(x) = v(x)r(x), so that s(x) = v(x)[qr(x)]. Conversely, any multiple of qr(x) is clearly in both I and J, so that IJ = I^J.

We're going to prove a special case of the Chinese Remainder Theorem, and get what we need to solve the problem out of the proof.

First, whenever we have an ideal I, (which, since R[x] is what's called a "principal ideal domain", you can think of as a subring consisting of all multiples of some element), we can form the

*factor ring* R[x]/I by identifying I with 0. The elements of this ring are the

*cosets* of I, and two elements of R[x] represent the same element of R[x]/I exactly when their difference is in I.

Our claim is that, with I and J defined by the polynomials q and r, R/IJ is isomorphic to the product (R/I)x(R/J). We'll prove this in a second; first we'll reflect on how this relates to our problem.

The problem give two ideals, I and J, and asks for p(x) such that q(x) divides p(x) and r(x) divides p(x) - 1. The first statement is equivalent to saying that p(x) is in I, and the second is equivalent to saying that p(x) - 1 is in J. The latter statement is in turn equivalent to saying that p(x) represents the coset 1 + J in the ring R[x]/J. In other words, we need to find p(x) in R[x] such that p(x) represents a coset in R[x]/IJ which corresponds via the isomorphism (whose existence we haven't even proved yet!) to (I, 1+J) in (R[x]/I)x(R[x]/J).

Define a function F from R[x]/IJ --> (R[x]/I)x(R[x]/J) by sending the coset a(x) + IJ to (a(x) + I, a(x) +J). We have to check a few things.

First, if a and b are two polynomials, F(a(x) + b(x) +IJ) = (a(x) + b(x) + I, a(x) + b(x) + J), by definition. Since addition of cosets works in the obvious way (this is part of the definition of factor rings), this is equal to F(a(x)+I) + F(b(x)+J). A similar argument, with addition exchanged for multiplication, shows that F preserves the multiplication -- such a map between two rings, which respects addition and multiplication, is called a

*homomorphism*, and F is one of them.

Slightly more interesting: suppose there is some a(x) so that F(a(x) + IJ) = (I, J). Then a(x) + I = I and a(x) + J = J; in other words, a(x) represents the zero cosets in the two factor rings, ie a(x) is in I and J. But we proved before that IJ = I^J, so a(x) must be in IJ, ie the coset a(x) + IJ that we hit with F was just IJ to start with. This shows that if F sends something to the zero element, which is represented by (I,J), then the thing it sent was the zero element (represented by IJ). Combining this with the fact that F preserves the addition and multiplication shows that F is one-to-one -- it sends different things to different things.

An "isomorphism" is a homomorphism which is one-to-one and has the property that every element of the ring into which it maps is in fact F(something). This means that so far, we are halfway to showing that F is an isomorphism. Once we show that it is an isomorphism, we'll be able to smugly say "well, (I, 1+J) is in the target ring, so there must be a p(x) such that F(p(x)) = (I, 1+J), so a solution exists". We want to actually exhibit such a p(x), though. Clearly the way to go about this is to find an inverse map for F (if F is truly an isomorphism, it will have one) and hit (I, 1+J) with this inverse, and we'll have a solution. This is why I've done things in general so far; we'll make an inverse that always works, and then we'll have both our solution and a proof of the CRT (which is just the assertion that F is an isomorphism).

Recall that q(x) and r(x) are relatively prime. The Euclidean Algorithm says that this gives us some polynomials, s(x) and t(x), such that sq(x)+tr(x) = 1. Now define a homomorphism E from (R[x]/I)x(R[x]/J) to R[x]/IJ by sending each coset-pair (a(x)+I, b(x)+J) to a(x)*t(x)*r(x) + b(x)*s(x)*q(x) + IJ. In particular, if the coset pair came from F, then a(x) = b(x), so that E(F(a(x)+IJ)) = E(a(x)+I,a(x)+J) = a(x)*[tr(x)+sq(x)] +IJ = a(x)*1 + IJ = a(x)+IJ, so EF is the identity. On the other hand, F(E(a(x)+I,b(x)+J)) = (a(x)*t(x)*r(x) + b(x)*s(x)*q(x) + I, a(x)*t(x)*r(x) + b(x)*s(x)*q(x) + J). Now a(x)*t(x)*r(x) + b(x)*s(x)*q(x) + I = atr(x) + I (because I kills multiples of q). But atr(x) = a(x)[1-sq(x)], which represents the same coset of I as a(x). Doing a similar thing for the second coordinate, with J, shows that FE is the identity, so E is an inverse to F.

Thus we just need to find s(x) and t(x), and we can find E((I, 1)) = p(x). This is the extended Euclidean algorithm; I've tried to write it in a way that can be carried out pretty algorithmically, but see end of post:

1. Start with q(x), r(x). It's best to keep track of things with three vectors, X,Y,Z each with three coordinates (for example X1 X2 X3). Start with X = (p(x), 1, 0), Y = (q(x), 0, 1), Z = (0,0,0)

2. While Y1 is not 0, do the following:

Z = X - k(x)Y, where k(x) is the polynomial part of X1/Y1, ie the quotient without the remainder.

Now set X = Y, Y = Z and repeat until Y1 = 0

3. Then, if q and r really have no common factors except 1, you'll finish with X1 = 1, X2 = t(x), X3 = s(x). Now you can construct E, and apply it to (0, 1) to get p(x).

End of post: This Euclidean algorithm is really the heart of the matter; can you prove that it terminates in the way I claim it does?