Remainders

1) Find the least x such that x has remainder 1 when divided by 2, 2 when divided by 3, and 1 when divided by 5.

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.

As opposed to just guessing, can you find a systematic way of doing this? There is an exceptionally beautiful theorem which states that there is such a number/polynomial, and naturally there exists a constructive proof. However, it is still a perfectly do-able problem without knowledge of this theorem. 🙂

Originally posted by Swlabr
1) Find the least x such that x has remainder 1 when divided by 2, 2 when divided by 3, and 1 when divided by 5.

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.

As opposed to just guessing, can you find a systematic way of doing this? There is an exceptionally beautiful ...[text shortened]... ve proof. However, it is still a perfectly do-able problem without knowledge of this theorem. 🙂

Hint: This theorem also explains why there are always leftovers when one dines on a certain Asian cuisine.

Originally posted by Swlabr
1) Find the least x such that x has remainder 1 when divided by 2, 2 when divided by 3, and 1 when divided by 5.

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.

As opposed to just guessing, can you find a systematic way of doing this? There is an exceptionally beautiful ...[text shortened]... ve proof. However, it is still a perfectly do-able problem without knowledge of this theorem. 🙂

The first one was easy: 11
becaue 11/2 gives 1 as reminder,
11/3 gives 2 as reminder and
11/5 gives 1 as reminder.

It was too easy, do I feel something fishy here?
Yes, of course there are many x < 11, 11 is not the least one, but they are negative, do they count?

When I studied math, we were given full points if we found any error in the question, even if we didn't solve the problem.
Here the error is that x was assumed to be a positive integer, but it didn't say that.

Originally posted by FabianFnas
The first one was easy: 11
becaue 11/2 gives 1 as reminder,
11/3 gives 2 as reminder and
11/5 gives 1 as reminder.

It was too easy, do I feel something fishy here?
Yes, of course there are many x < 11, 11 is not the least one, but they are negative, do they count?

When I studied math, we were given full points if we found any error in the ques ...[text shortened]... oblem.
Here the error is that x was assumed to be a positive integer, but it didn't say that.

I was, obviously, working over the natural numbers... 😛

The problem is finding a systematic way of doing it. Finding x such that x=
a_1 mod b_1
a_2 mod b_2
.
.
.
a_n mod b_n

?

Originally posted by Swlabr
I was, obviously, working over the natural numbers... 😛

I know you was. Among mathematicians there are a number of things that are understood without writing it explicit. Lie the pi symbol represent 3.14159... (approx), that n generally represent a natural number, and x a real, and such, but here we deal with non matematicians.

The "a_1 mod b_1" doesn't say much for people not studying number theory, yet many non matematicians do in fact think of reminders very elaborately, like carpenters and tailors.

The answer of your question (1) can be described as a problem where the "chinese reminder theorem" can be used, but testing all numbers, whithout crt, from one and upwards gets a result very quickly.

When my grand grand mother was a little girl, she was given a basket of eggs by her mother, and was told to go to the neighbours and sell them.
When she came home she was asked how many she had sold. She didn't know, but she answered that she sold them all. "At the first house I sold half of the eggs I had plus a hlf an egg. At the second house I sold half the eggs I had left plus a half. At the third house I sold half the eggs I had left plus a half. At the fourth house I sold half the eggs I had left plus a half." "Oh," said her mother, "did you have to break them in order to sell them?" And she answered very correctly "No, I didn't break any of them!"
Question: How many eggs did she sell?

Even here one can use the chinese reminder theoreme, but counting backwards is much simpler.

Originally posted by Swlabr
1) Find the least x such that x has remainder 1 when divided by 2, 2 when divided by 3, and 1 when divided by 5.

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.

As opposed to just guessing, can you find a systematic way of doing this? There is an exceptionally beautiful ...[text shortened]... ve proof. However, it is still a perfectly do-able problem without knowledge of this theorem. 🙂

(2) I tried assuming the answer was a polynomial of the form:

p(x) = SUM(i=1..n) [ai*x^i] = a0 + a1*x + a2*x^2 + ... an*x^n

and then performing synthetic division on it (dividing p(x) by (x^2+1) and p(x)-1 by (x^3+1)). You end up with a quotient and a remainder, but since the remainder is 0 in this problem by definition, you can set each remainder term equal to 0 and thereby develop a system of equations to solve. Intuitively I thought n=5 would be the least degree, but I tried n=3 and n=4 to start with anyway. With n=3, you end up with 4 unknowns (a0, a1, a2, a3) but 5 equations, which I believe makes this problem over-defined because you end up with nonsense. With n=4 you end up with 5 unknowns (a0, a1, a2, a3, a4) and 5 equations, so it's solvable. The solution of this system gave me:

p(x) = -(1/2)x^4 - (1/2)x^3 - (1/2)x + (1/2)

Of course, you can always just factor out the (1/2) to make it slightly prettier, but this polynomial works just fine.

I suppose this could be thought of as a systematic method to find such a polynomial, since you must start checking equations of a degree equal to or greater than the degree of the highest-degree divisor (in this case, n(min)=3 because we have (x^3+1) as a divisor) and work your way up one degree at a time, but it's pretty work-intensive. Is there a better way? Does the Chinese Remainder Theorem apply here as well? Or is there another theorem for polynomials?

Originally posted by PBE6
(2) I tried assuming the answer was a polynomial of the form:

p(x) = SUM(i=1..n) [ai*x^i] = a0 + a1*x + a2*x^2 + ... an*x^n

and then performing synthetic division on it (dividing p(x) by (x^2+1) and p(x)-1 by (x^3+1)). You end up with a quotient and a remainder, but since the remainder is 0 in this problem by definition, you can set each remainder term e ...[text shortened]... he Chinese Remainder Theorem apply here as well? Or is there another theorem for polynomials?

The Chinese Remainder Theorem does indeed apply here, since R[x] is a commutative ring. That's what my lame joke above is referring to.

Originally posted by ChronicLeaky
The Chinese Remainder Theorem does indeed apply here, since R[x] is a commutative ring. That's what my lame joke above is referring to.

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

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?

Originally posted by ChronicLeaky
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 p ...[text shortened]... atter; can you prove that it terminates in the way I claim it does?

Thanks! Holy crap that looks complicated though, gonna have to sit down and look at this one for a while...

Originally posted by PBE6
Thanks! Holy crap that looks complicated though, gonna have to sit down and look at this one for a while...

Really most of the part which is actually a "systematic solution" is in the numbered stuff at the end. I'm sure it's not too clear, so post a shout (shout a post?) if something should be broken down.