Have we a P(x) with integer coefficients in which...
MJDousti
[[[P= Polynomial]]]
Have we a P(x) with integer coefficients in which
P(19)=85 and
P(1)=19
and why???
thanx
Robert Israel
Hint: what must P(x) - P(y) be divisible by?
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
Virgil
<4e8f376f.03040...@posting.google.com>,
MJDo...@myrealbox.com (MJDousti) wrote:
There are infinitely many such polynomial functions with
rational coefficients.
There is, however, a unique one on minimal degree, in this
case of degree 1.
Try fitting P(x) = m*x + b to your two points, by finding
suitable values for m and b.
David C. Ullrich
How does that answer the question?
******************
David C. Ullrich
Virgil
It doesn't, necessarily, but it is a reasonable first step.
If it works, you're done. if it doesn't, you haven't
wasted much energy.
Bill Dubuque
>
> Can a polynomial P(x) with integer coefficients satisfy
>
> satisfy: P(19) = 85 and P(1) = 19 ?
Big Hint: mod 18 yields a contradiction.
Alternatively, use the polynomial root-factor or remainder theorem
that x - y | P(x) - P(y) e.g. 10-1 | P(10)-P(1) "casting out nines"
i.e. x = y => P(x) = P(y) e.g. 10=1 => P(10)=P(1).
For much more on this see my ealier posts, e.g.
From: Bill Dubuque <w...@berne.ai.mit.edu>
Subject: Re: Proof for : n + (n+1)^2 + (n+2)^3 is divisible by (n+3)
Date: 1997/12/19
Message-ID: <y8zoh2c...@berne.ai.mit.edu>#1/1
Patrick De Geest <Patrick...@ping.be> wrote:
|
| Can someone provide me a more or less elegant proof
| ( elegant also meaning understandable for the layman )
| of the following statement :
|
| Every number of the form (n+0)^1 + (n+1)^2 + (n+2)^3
| or n + (n+1)^2 + (n+2)^3
| is divisible by (n+3)
In high-school you probably learned the following
ROOT FACTOR THEOREM. The linear polynomial (x-r) divides the
polynomial P(x) if and only if P(r)=0, i.e. r is a root of P.
Applying this theorem to your example we find that (n+3)
divides your polynomial P(n) iff p(-3) = 0, which holds
true since P(-3) = -3 + (-2)^2 + (-1)^3 = -3 + 4 - 1 = 0.
The Root Factor Theorem is just a special case of the
REMAINDER EVALUATION THEOREM. P(x) mod (x-r) = P(r), i.e.
the remainder upon dividing the polynomial P(x) by (x-r) is P(r),
which follows by using the Division Algorithm to divide P(x) by (x-r)
P(x) = Q(x) (x-r) + R(r), with deg(R(x)) < deg(x-r)=1
so R(x) has degree 0, i.e. R(x)=R is a constant, whose value
may be determined by evaluating the above at x=r:
P(r) = Q(r) (r-r) + R, i.e. R = P(r), so the theorem.
Another way to state the Remainder Evaluation Theorem is
that x-r | P(x)-P(r) where "a | b" means "a divides b".
This has as an immediately corollary the very classical
"casting out nines" test for divisibility by 9:
Decimal notation is a polynomial function of the radix 10:
N = P(10) = a + b 10 + c 10^2 + d 10^3 + ...
e.g. 234 = P(10) = 4 + 3 10 + 2 10^2
Now x-r | P(x) -P(r) for any polynomial P by the theorem
so 10-1 | P(10)-P(1) by evaluating at x=10, r=1
ie. mod 9, P(10)=P(1) = a + b + c + d + ... = sum of digits,
so that 9 divides N iff 9 divides the sum of the digits of N.
e.g. 234 = P(10) = 2 10^2 + 3 10 + 4
and P(1) = 2 + 3 + 4 = 9
so that 9 | 234, and indeed 9*26 = 234.
Isn't that pretty?
In fact connections like the above between evaluation and
divisibility are very special instances of general results that
are standard topics of college algebra (homomorphisms, congruences,
quotient objects, etc). See any good textbook for further
details, e.g. Jacobson, Hungerford, Lang, Birkhoff and MacLane
or, for a very gentle introduction, Herstein or Fraleigh.
For further discussion of casting nines etc. see my other posts
http://groups.google.com/groups?q=group%3A*math*+dubuque+casting
-Bill Dubuque
MJDousti
P(x) is something like this:
P(x)=f(n)*x^n + f(n-1)*x^n + ... + f(2)*x^2 + f(1)*x + b
^ ^
Index Integer
f(n), f(n-1),...F(2), f(1) is coefficients.
and aslo I try it P(x)= m*x + b but I can't solve this problem in this mode (also)
thanx.
David C. Ullrich
But it doesn't work. That only takes a second to verify.
More to the point, it seems awesomely clear that if it
_did_ work then the OP would not have asked the
question in the first place.
******************
David C. Ullrich
David C. Ullrich
<ull...@math.okstate.edu> wrote:
Although having said that I feel I should maybe clarify:
When I asked how this solved the problem I wasn't
meaning to assert that this _didn't_ solve the problem:
It's clear that there is no linear polynomial that works;
it _could_ have been that you had some result in mind
that implied that if there _was_ a solution then there
must be a linear solution. If so then what you said
_would_ solve the problem, hence the question.
But I guess not.
******************
David C. Ullrich
Jonathan Miller
>More to the point, it seems awesomely clear that if it
>_did_ work then the OP would not have asked the
>question in the first place.
>
Unfortunately, that's not necessarily true.
Jon Miller
Ignacio Larrosa Cañestro
news:y8zu1dg...@nestle.ai.mit.edu...
> MJDousti <MJDo...@myrealbox.com> wrote:
> >
> > Can a polynomial P(x) with integer coefficients satisfy
> >
> > satisfy: P(19) = 85 and P(1) = 19 ?
>
> Big Hint: mod 18 yields a contradiction.
>
Perhaps somebody want to have fun with this:
"Prove that for any integer n, exists a unique polynomial Q(x) with
coefficients in the set {0,1,2,...9}, with Q(-2) = Q(-5) = n"
--
Best Regards from a "PPrestigeada" Galicia
in the 15th day of Infamy
(www.noalaguerra.org)
Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosaQUIT...@mundo-r.com
Virgil
David C. Ullrich <ull...@math.okstate.edu> wrote:
> On Thu, 03 Apr 2003 00:34:38 GMT, Virgil <vmh...@attbi.com> wrote:
>
> >In article <8ktm8vc8uoe1hk5a1...@4ax.com>,
> > David C. Ullrich <ull...@math.okstate.edu> wrote:
> >
> >> On Wed, 02 Apr 2003 22:27:34 GMT, Virgil <vmh...@attbi.com> wrote:
> >>
> >> >In article
> >> ><4e8f376f.03040...@posting.google.com>,
> >> > MJDo...@myrealbox.com (MJDousti) wrote:
> >> >
> >> >> Hi,
> >> >> [[[P= Polynomial]]]
> >> >> Have we a P(x) with integer coefficients in which
> >> >>
> >> >> and why???
> >> >>
> >> >> thanx
> >> >
> >> >There are infinitely many such polynomial functions with
> >> >rational coefficients.
> >> >
> >> >There is, however, a unique one on minimal degree, in this
> >> >case of degree 1.
> >> >
> >> >Try fitting P(x) = m*x + b to your two points, by finding
> >> >suitable values for m and b.
> >>
> >> How does that answer the question?
> >>
> >> ******************
> >>
> >> David C. Ullrich
> >
> >It doesn't, necessarily, but it is a reasonable first step.
> >If it works, you're done. if it doesn't, you haven't
> >wasted much energy.
>
> But it doesn't work. That only takes a second to verify.
>
> More to the point, it seems awesomely clear that if it
> _did_ work then the OP would not have asked the
> question in the first place.
>
> ******************
>
> David C. Ullrich
After that, consider that if the two equations are true for
a polynomial with integer coefficients, they must also be
true as congruences modulus any positive integer.
When you try them in mod 9 arithmetic you get
P(19)=85 becomes P(1) == 4 (mod 9) and
P(1)=19 becomes P(1) == 1 (mod 9)
which is an impossible situation.
Thus there can be no polynomial with integer coefficients
satisfying the given conditions.
Virgil
When approaching a problem like this, I sometimes find it
useful to be sure that trivial methods don't work before
digging deeper. Even when they don't work, trying them often
gives me some insight into what will work.
In this problem, seeing that the slope of a linear function
must be fractional, made me think about methods that only
involved integers - which lead to congruences and a
solution.
Viewing the equations as congruences mod 9 shows them to be
incompatible.
William C Waterhouse
Maybe it is worthwhile to write out the result here
with no mention of congruences.
Theorem. Let a, b, m, and n be integers. Then the following are
equivalent:
1) There is some polynomial P(x) with integer coefficients
satisfying P(a) = m, P(b) = n.
2) n-m is a multiple of b-a.
3) There is a first-degree polynomial R(x) with integer coefficients
satisfying R(a) = m, R(b) = n.
Proof. Assume 1). Let Q(x) = P(x+a), which will also have integer
coefficients and will satisfy Q(0) = m, Q(b-a) = n. Now
clearly Q(b-a) equals m plus a number of terms all involving
the factor b-a. If this equals n, then n-m must be a multiple
of b-a, so 2) is true.
Assume 2). Say n-m = c(b-a). Let P(x) = cX + (m-ac). Clearly
P(a) = m, and P(b) = m + cb - ca = m + c(b-a) = n. Thus 3) is true.
Obviously 1) is true when 3) is true.
William C. Waterhouse
Penn State
Oscar Lanzi III
where Q(18) is determinable from the given information. Oops.
--OL
Gerry Myerson
"Ignacio Larrosa Cañestro" <ilarrosaQUIT...@mundo-r.com>
wrote:
> Perhaps somebody want to have fun with this:
>
> "Prove that for any integer n, exists a unique polynomial Q(x) with
> coefficients in the set {0,1,2,...9}, with Q(-2) = Q(-5) = n"
Nice. Where'd you get it?
Something like a solution follows.
S
P
O
I
L
E
R
S
P
O
I
L
E
R
S
P
O
I
L
E
R
S
P
O
I
L
E
R
S
P
O
I
L
E
R
S
P
O
I
L
E
R
S
P
O
I
L
E
R
Let P(x) = Q(x) - n.
Q(-2) = Q(-5) = n if and only if P(-2) = P(-5) = 0,
equivalently P(x) = (x^2 + 7x + 10) R(x) for some polynomial R(x)
with integer coefficients; say, R(x) = r_d x^d + ... + r_0.
All coefficients of P(x) must be in {0,1,2,...9} except (possibly)
the constant term, which must be of the form a - n with a in
{0,1,2,...9}.
But the constant term of P(x) is a multiple of 10, so it is
uniquely specified, thus uniquely specifying r_0.
Now the linear term of P(x) is 10 r_1 + 7 r_0. There is a unique
value of r_1 that puts this in {0,1,2,...9}.
Now the quadratic term of P(x) is 10 r_2 + 7 r_1 + r_0. There is
a unique value of r_2 that puts this in {0,1,2,...9}.
Etc.
The coefficients r_0, r_1, ..., are thus determined, uniquely,
and with them the polynomial P(x) and thus Q(x). It remains to
show that the process terminates.
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
Ignacio Larrosa Cañestro
news:gerry-025A10....@sunb.ocs.mq.edu.au...
> In article <b6hsgc$5bn92$1...@ID-137122.news.dfncis.de>,
> "Ignacio Larrosa Cañestro" <ilarrosaQUIT...@mundo-r.com>
> wrote:
>
> > Perhaps somebody want to have fun with this:
> >
> > "Prove that for any integer n, exists a unique polynomial Q(x) with
> > coefficients in the set {0,1,2,...9}, with Q(-2) = Q(-5) = n"
>
> Nice. Where'd you get it?
I saw it in the newsgroup es.ciencia.matematicas. I don't know its origin.
> Something like a solution follows.
>
> Let P(x) = Q(x) - n.
>
> Q(-2) = Q(-5) = n if and only if P(-2) = P(-5) = 0,
> equivalently P(x) = (x^2 + 7x + 10) R(x) for some polynomial R(x)
> with integer coefficients; say, R(x) = r_d x^d + ... + r_0.
>
> All coefficients of P(x) must be in {0,1,2,...9} except (possibly)
> the constant term, which must be of the form a - n with a in
> {0,1,2,...9}.
>
> But the constant term of P(x) is a multiple of 10, so it is
> uniquely specified, thus uniquely specifying r_0.
>
> Now the linear term of P(x) is 10 r_1 + 7 r_0. There is a unique
> value of r_1 that puts this in {0,1,2,...9}.
>
> Now the quadratic term of P(x) is 10 r_2 + 7 r_1 + r_0. There is
> a unique value of r_2 that puts this in {0,1,2,...9}.
>
> Etc.
>
> The coefficients r_0, r_1, ..., are thus determined, uniquely,
> and with them the polynomial P(x) and thus Q(x). It remains to
> show that the process terminates.
My solution, basically identicall:
Q(x) = (x + 2)(x + 5)P(x) + n = (x^2 +7x +10)P(x) + n
The cofficients of P aren't necessary in {0,1,2,...9}, but they are
integers. Let b(n) to be the coefficient of x^n in P(x). Then,
0 <= 10b(0) + n <= 9 ===> 0 <= b(0) + n/10 <= 9/10 ===> b(0) = -[n/10]
(valid for n positive or negative)
For b(1),
0 <= 10b(1) + 7b(0) <= 9 ===>
0 <= b(1) + 7b(0)/10 <= 9/10 ===>
b(1) = -[7b(0)/10]
For b(2),
0 <= 10b(2) + 7b(1) + b(0) <= 9 ===>
0 <= b(2) + 7b(1)/10 + b(0)/10 <= 9/10 ===>
b(2) = - [(7b(1) + b(0))/10]
In general,
b(k+2) = - [(7b(k+1) + b(k))/10], para k >= 0
All b(n) are univocally determined, and for all n, they are zero from a
certain k, because they hav alternate signs, and therefore, each one is, in
absolute value, less or equal than 7/10 of the previous.
By example, for n = 196,
b(0) = -[196/10] = -19
b(1) = -[-7*19/10] = -[-13.3] = -(-14) = 14
b(2) = -[(7*14 -19)/10] = -7
b(3) = -[(7(-7) + 14)/10] = -(-4) = 4
b(4) = -[(7*4 - 7)/10] = -2
b(5) = -[(7(-2) + 4)/10] = -(-1) = 1
b(6) = -[(7*1 - 2)/10] = 0
b(7) = -[(7*0 + 1)/10] = 0
and all of the rst b(n) are nulls. Then,
P(x) = (x^2 +7x +10)(x^5 - 2x^4 + 4x^3 - 7x^2 + 14x - 19) + 196
= x^7 + 5x^6 + x^4 + 5x^3 + 9x^2 + 7x + 6
--
Best regards from a 'PPrestigeada' Galicia,
in the 20th day of Infamy