| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1716.1 | 51 | AUSSIE::GARSON | | Wed Feb 03 1993 05:06 | 0 |
| 1716.2 | | STAR::ABBASI | i think iam psychic | Wed Feb 03 1993 10:35 | 7 |
| need to make sure x is not any a special value.
ie. the divison is oo when x=1 and it is 0 when x=0. for example.
|
| 1716.3 | | STAR::ABBASI | i think iam psychic | Wed Feb 03 1993 11:45 | 28 |
| > 1 + x^2 + x^4 + x^6 +....+x^100 is divided by (x^2 - 1) ?
for those like me who did not see the solution very quickly, this
is one way to do it:
write it as
1+x^2 x^4 x^100
----- + ---- +..... + -------
x^2-1 x^2-1 x^2-1
the first term divides to 1 with reminder 2
the second term divides with reminder 1
the third term divides to the second term, which divides with reminder 1
(i.e. dont have to do the full long division for every term, once it
it becomes the term before it, you already done the division on
that and we know the reminder is 1)
etc...
<----- 49 times ----->
so add the reminders, so we get 2 + [ 1 + 1 +.......... +1] = 51
ok, it took me 15 minutes to see the solution ;-( but i still have
not had my morning coffe so this is my execuss.
\bye
\nasser
|
| 1716.4 | | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Wed Feb 03 1993 13:46 | 8 |
| Or write it using y = x^2,
1 + y + y^2 + y^3 + ... + y^50 divided by y-1
The remainder when a polynomial p(y) is divided by y-a
is just p(a). Here, p(1) = 51, one for each term.
Dan
|
| 1716.5 | | STAR::ABBASI | i think iam psychic | Wed Feb 03 1993 14:24 | 15 |
| .-1
i like that! that makes it even easier !
but offcourse one had to know that f(x)/f(x-a) = f(a). when f(x) is
a poly.
now, one got'a go try to proof this!
what kind of functions does this relation hold for? my intuition tells
me for not too many, 'cause it seems like a special relation ..
\bye
\nasser
|
| 1716.6 | | HANNAH::OSMAN | see HANNAH::IGLOO$:[OSMAN]ERIC.VT240 | Wed Feb 03 1993 15:48 | 45 |
|
The original question:
Divide 1 + x^2 + x^4 + x^6 ... + x^100 by x^2 -1, what's the remainder ?
Well, I started thinking of it this way. If there *is* a remainder, that is,
if the remainder is a particular number, and doesn't depend on x, then
we can choose x to be anything we want, as long as we're not dividing by
0.
Hence x can be anything except 1 or -1. So, let x = 2.
So we have
1 + 2^2 + 2^4 + 2^6... + 2^100 / 2^2 - 1
Writing this in binary, we have
1010101...010101 / 11
Hey, I just thought of something. Since we're dividing by 3, the remainder
has to be 0,1 or 2. So why did someone say the answer is 51 ???
Anyway, we do long division:
1110001
11 ) 101010101...01010101
11
---
100
11
---
011
11
---
00101
At this point, we've got 101, which was our first dividend, so it will
repeat.
But I'm still curious about how the remainder can *possibly* be 51 since
dividing by 3 only produces a remainder of 0, 1, or 2.
Any explanations ?
/Eric
|
| 1716.7 | i think you are right, the answer cant be 51 !! | STAR::ABBASI | i think iam psychic | Wed Feb 03 1993 16:35 | 25 |
|
good question!
iam now sure the answer 51 is WRONG !!
i think i know why, at least how i did it:
i divided the polynomial into many different polynomials,
and took the reminder of EACH on of those when dividing
by the x^2-1 , and then ADDED the reminders. this is not right !
just as example , just as saying that reminder of 99 when divided by 5 is
<...... 11 times ............................>
REM(9,5) + REM(9,5) + REM(9,5) +.....+ REM(9,5) = 4+4+...+4 = 44
but we know that is not right, 'cause REM(99,5)= 4
iam pretty sure now that 51 is the wrong answer !!
you get a cigar. you know i did have a deep feeling at first that the
reminder should be a function of x !
\nasser
|
| 1716.8 | | AUSSIE::GARSON | | Wed Feb 03 1993 17:12 | 39 |
| re .last few
Some hand-waving about what is meant by the remainder from dividing one
polynomial by another...
First look at what it means to say what the remainder on dividing is
for integers. Suppose we divide 7 by 3 and say the remainder is 1. This
means 7 = k.3 + 1.
By analogy
P(x) = Q(x)D(x) + R(x)
can be used to find the remainder from dividing P(x) by D(x) which in
the above notation is R(x), Q(x) being the quotient.
Now just as with the integer case there is a rule for deciding what to
use for k so that the remainder is unique (otherwise I could have
written 7 = k'.3 + 4) so it is with polynomials. For integers the
remainder must be in the range 0..d-1 where d is the number you are
dividing by.
For polynomials the remainder polynomial R(x) must have degree less
than D(x) i.e. deg R is in the range 0..deg D - 1.
Thus when D(x) is of the form (x-a), deg D = 1 and so the remainder
must have degree 0 i.e. be a constant, say r.
P(x) = Q(x)(x-a) + r (1)
The Remainder Theorem (alluded to in .4) states that r = P(a)
Proof: Since (1) is an equation about functions it must hold for all x and
thus we may put x=a and the result drops out.
Hence, in fact, the original problem, not being chosen at random, can be
done in one's head! The only flaw was that the answer should have been
made to be 42. (-:
|
| 1716.9 | iam going home to study my polys again | STAR::ABBASI | i think iam psychic | Fri Feb 05 1993 14:02 | 67 |
| well, maple says it is 51, so it must be 51 ;-(
> den;
2
x - 1
> num;
2 4 6 8 10 12 14 16 18 20 22 24 28
1 + x + x + x + x + x + x + x + x + x + x + x + x + x
26 40 38 36 34 32 30 42 44 46 48 50
+ x + x + x + x + x + x + x + x + x + x + x + x
52 54 56 58 60 62 64 66 68 70 72 74
+ x + x + x + x + x + x + x + x + x + x + x + x
76 78 80 82 84 86 88 90 92 94 96 98
+ x + x + x + x + x + x + x + x + x + x + x + x
100
+ x
> rem(num,den,x,'q');
51
by the way , the quotient Q is:
q;
2 4 6 8 10 12 14 16 18
50 +49 x +48 x + 47 x + 46 x + 45 x + 44 x + 43 x + 42 x + 41 x
20 22 24 28 26 40 38 36
+ 40 x + 39 x + 38 x + 36 x + 37 x + 30 x + 31 x +32 x
34 32 30 42 44 46 48 50
+ 33 x + 34 x + 35 x + 29 x + 28 x + 27 x + 26 x +25 x
52 54 56 58 60 62 64 66
+ 24 x + 23 x + 22 x + 21 x + 20 x + 19 x + 18 x +17 x
68 70 72 74 76 78 80 82
+ 16 x + 15 x + 14 x + 13 x + 12 x + 11 x + 10 x + 9x
84 86 88 90 92 94 96 98
+ 8 x + 7 x + 6 x + 5 x + 4 x + 3 x + 2 x + x
so: Q*(x^2-1)+51 = 1+x^2+.....+x^100
/nasser
ps.
funny thing why maple has the numenator poly written, it jumps from
x^24 to x^28 then write x^40 down to x^30 then starts writing them
in the correct order again!
i inputed the numenator poly in steps, but dont know why maple is
written the poly out with some terms shuffled in between, weried ,
isn't?
> num;
2 4 6 8 10 12 14 16 18 20 22 24
1 + x + x + x + x + x + x + x + x + x + x + x + x
> num:=num+x^26+x^28+x^30+x^32+x^34+x^36+x^38+x^40+x^42+x^44+x^46+x^48;
2 4 6 8 10 12 14 16 18 20 22 24
num := 1 + x + x + x + x + x + x + x + x + x + x + x + x
28 26 40 38 36 34 32 30 42 44 46 48
+ x + x + x + x + x + x + x + x + x + x + x + x
|
| 1716.10 | | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Sun Feb 07 1993 16:23 | 5 |
| Try
> num := (1 - x^102) / (1 - x^2) ;
Dan
|
| 1716.11 | | HANNAH::OSMAN | see HANNAH::IGLOO$:[OSMAN]ERIC.VT240 | Mon Feb 08 1993 11:17 | 9 |
|
I'm still feeling frustrated and confused. Can someone *please* explain
how the remainder can be 51, when any x less than 52 can't *possibly* produce
a remainder of 51 ?
Thanks.
/Eric
|
| 1716.12 | | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Mon Feb 08 1993 12:39 | 38 |
| Don't substitute a number in for x.
What polynomial division means is that to divide a(x) by b(x),
you find polynomials q(x) and r(x) with the degree of r less
than the degree of b, such that a(x) = b(x) q(x) + r(x). The
quotient is defined to be q(x) and the remainder is defined to
be r(x). If the coefficients of the polynomials come from a
field, then you can always do this (when b(x) has at least one
nonzero coefficient) and come up with a unique such q(x) and r(x).
This definition is just the most useful analog of defining
positive integer division of m by n to be the quotient q and
remainder r such that m = nq + r, 0 <= r < n.
For example, x^2 + 3x + 6 divided by x + 2. Well,
x^2 + 3x + 6 = (x + 2)(x + 1) + 4,
so the quotient is x + 1 and the remainder is 4.
That is the answer because that is the definition, period.
It is completely irrelevant that you can find values of x to
plug into x+2 so that it divides 4. One thing you can say is
that if you plug in a particular n for x, then the remainder
of dividing n^2 + 3n + 6 by n+2 is the same as the remainder
of dividing 4 by n+2. But that is just an obvious consequence
of the definition of polynomial division.
Likewise, with 1 + x^2 + ... + x^100 = (x^2 - 1)q(x) + 51,
the remainder of the polynomial division is defined to be 51.
At a particular value n for x, the remainder when 1+n^2+...+n^100
is divided by n^2 - 1 will the same as the remainder when 51
is divided by n^2 - 1. But that doesn't change the definition
of polynomial division, or that the result of that polynomial
division was a remainder of 51.
Dan
|
| 1716.13 | | STAR::ABBASI | i think iam psychic | Mon Feb 08 1993 14:09 | 3 |
| iam starting to think that may be physics is easier than math. :)
\nasser
|
| 1716.14 | Here is another method | MARX::PADHY | | Mon Feb 08 1993 17:45 | 37 |
|
For those of you who have not convinced yet, here is another way:
original problem: Let Q = (1+ x^2 + x^4 + x^6 +.. + x^100)/(x^2 -1).
Let y = x^2, then
Q = (1 + y + y^2 +.. +y^50)/(y-1)
= ((y^51 -1)/(y-1)) / (y-1)
Now let z = y -1 = x^2 -1, then
Q = ((1+z)^51 - 1) /z^2
Applying binomial theorem,
(1+z)^51 = 1 + 51*z + f(z)*(z^2)
Hence,
Q = (51*z + f(z)*z^2)/ (z^2)
= (51 + f(z)*z))/z
Thus, we have reduce the original problem to a simpler form, with
z = x^2 - 1.
It is obvious that Q has a remainder of 51.
Hope this helps,
Bud
|
| 1716.15 | | AUSSIE::GARSON | | Sat Feb 20 1993 23:57 | 20 |
| re .13
You should think of the polynomials as the objects being manipulated
and not try to substitute particular values of x. To get more of a feel
for it you can do long division of polynomials in the same way you
would have done with numbers in the pre-calculator days.
Example (coefficients chosen at 'random'):
2x� -21x +132 <--- quotient
__________________________
x�+6x+1 ) 2x^4 -9x� +8x� -35x+100
-(2x^4+12x� +2x�)
-21x� +6x� -35x+100
-(-21x�-126x� -21x)
132x� -14x+100
-(132x�+792x+132)
-806x -32 <--- remainder
e&oe
|