Proving a polynomial has no integer solution

[timetraveller123]

Homework Statement

let p(x) be a polynomial with integer coefficients satisfying p(0) = p(1) = 1999
show that p has no integer zeros

Homework Equations

The Attempt at a Solution

$p(x) = \sum_{i= 0}^{n}{a_i x^i}$[/B]
using the given information
a₀ = 1999( a prime number)
and
$a_n + a_{n-1} ... a_1 = 0$

then rewriting p(x)

$p(x) = a_n(x_n + \frac{a_{n-1}}{a_n} x^{n-1} ... \frac{1999}{a_n})\\ p(x) = a_n(x-r_1)(x - r_2) ...(x - r_n)\\$
i am hoping to do the rest of the proving by contradiction
if i assume the polynomial has integer solution then how can i disprove it

 

[Buffu]

Use Rational roots theorem.

If $p/q$ is a root of the given polynomial then $p$ must be a factor of $a_0$.
Which means $p = 1$ or $p = 1999$.

 

[timetraveller123]

ya i tried doing that what do i get from that

 

[Buffu]

ya i tried doing that what do i get from that

You know that $q$ is a factor of $a_n$. If $p/q$ is a integer then what condition do you get on $q$ for $p = 1$ ?

 

[timetraveller123]

$P(x) = (qx - p)(Q(x))\\ q|a_n \\ p|1999\\ p = \pm 1 or \pm 1999\\$

if p = ±1 then q must also equal ±1
if p = ±1999 then q must equal ±1 or ±1999

 

[Buffu]

$P(x) = (qx - p)(Q(x))\\ q|a_n \\ p|1999\\ p = \pm 1 or \pm 1999\\$

if p = ±1 then q must also equal ±1
if p = ±1999 then q must equal ±1 or ±1999

So what the possible integer values ?

 

[timetraveller123]

you mean the roots the possible integer roots are ±1 and ±1999

 

[Buffu]

you mean the roots

Sorry. Yes I mean roots.

 

[timetraveller123]

you mean the roots the possible integer roots are ±1 and ±1999

 

[Buffu]

you mean the roots the possible integer roots are ±1 and ±1999

$1$ is out because $p(1) = 1999$. Can you eliminate others ?

 

[timetraveller123]

i am sorry i just can't think of ways to eliminate the rest give me another hint
edit:
after much trying managed to eliminate just 1 of the roots
if we a
$a_n + a_{n- 1} ... a_1 = 0\\ a_n + a_{n-1} ... a_2 = -a_1\\ p(-1) = a_n(-1)^n + a_{n-1} (-1)^n-1 ... -a_1 + 1999\\ p(-1) = a_n(-1)^n + a_{n-1} (-1)^n-1 ... a_2 +a_2 +a_3 + ... a_n + 1999\\$
the right hand side will cancel out all the terms with odd subscripts leaving only 2 of each even subscript terms and since they are integers the right hand side is 1 mod 2 thus cannot be zero is this correct?
please give me hints for the next two roots

 

[Buffu]

i am sorry i just can't think of ways to eliminate the rest give me another hint
edit:
after much trying managed to eliminate just 1 of the roots
if we a
$a_n + a_{n- 1} ... a_1 = 0\\ a_n + a_{n-1} ... a_2 = -a_1\\ p(-1) = a_n(-1)^n + a_{n-1} (-1)^n-1 ... -a_1 + 1999\\ p(-1) = a_n(-1)^n + a_{n-1} (-1)^n-1 ... a_2 +a_2 +a_3 + ... a_n + 1999\\$
the right hand side will cancel out all the terms with odd subscripts leaving only 2 of each even subscript terms and since they are integers the right hand side is 1 mod 2 thus cannot be zero is this correct?
please give me hints for the next two roots

Yes except I think it should be $p(-1) = a_n(-1)^n + a_{n-1} (-1)^\color{green}{n-1} ... a_2 +a_2 +a_3 + ... a_n + 1999$.

Hint :

Product of roots is $|a_0/a_n|$

Or $\dfrac{|a_0|}{|a_n|} = |r_1r_2 \cdots r_n|$

If one root is $1999$
then,
$|1999| = |a_n||r_2 \cdots r_n| \times 1999 \implies 1 = |a_n||r_2 \cdots r_n|$

 

[haruspex]

please give me hints for the next two roots

If 1999 is a root, how many times might 1999 divide a_i1999ⁱ? Given that it divides a₀ exactly once, what does that tell you about a₁? Then, what about the relationship between a₂ and a₃?

 

[timetraveller123]

@haruspex

Did you mean ...−a1+a2−a3+...an+1999...−a1+a2−a3+...an+1999... - a_1 +a_2 -a_3 + ... a_n + 1999?

i think what @Buffu wrote is correct as he substituted $- a_1 = a_2 + a_3 ... a_n$

@Buffu
following on what you said
$1 = (\mid a_n \mid)(\mid r_2 r_3 ...r_n)$ since $a_n$ is integer$\mid a_n \mid = 1$
then this make $p(x)$ a monic polynomial then its roots can only be integers or irrationals not fractions then from $\mid r_2 r_3 ...r_n\mid = 1$ we get that $r_i$ has to equal 1 but its shown that 1 is not possible hence 1999 is not possible is this valid ?

 

[haruspex]

i think what @Buffu wrote is correct

Ok, I misinterpreted the ...

$1 = (\mid a_n \mid)(\mid r_2 r_3 ...r_n\mid)$ since $a_n$ is integer $\mid a_n \mid = 1$

I'm not following. If $\mid r_2 r_3 ...r_n\mid=\frac 12$ then $(\mid a_n \mid)=2$, etc. How are you ruling that out?

 

[timetraveller123]

I'm not following. If ∣r2r3...rn∣=12∣r2r3...rn∣=12\mid r_2 r_3 ...r_n\mid=\frac 12 then (∣an∣)=2(∣an∣)=2(\mid a_n \mid)=2, etc. How are you ruling that out?

oh you i got over excited and did that and i am stuck again one more hint please is there some kind of restriction on a_n
should i be writing $\mid a_n \mid$ as $\mid a_1 + a_2 ... a_{n-1} \mid$ does that help

 

[haruspex]

oh you i got over excited and did that and i am stuck again one more hint please is there some kind of restriction on a_n
should i be writing $\mid a_n \mid$ as $\mid a_1 + a_2 ... a_{n-1} \mid$ does that help

Did you think about my post #13?

 

[timetraveller123]

oh i completely didn't see the post only noticed it after you pointed it out don't know what happened there will take a look now thanks oh wait you edited i forgot to see the edit

 

[timetraveller123]

@ haruspex
are you hinting at geometric series
because i thought of it at first but the fact that a₂ + ...a_n = 0
then i considered all the terms in that to be same but alternating signs but that forces n to be odd this was initial line of thought
i am sorry if am not seeing what you are suggesting

 

[haruspex]

@ haruspex
are you hinting at geometric series
because i thought of it at first but the fact that a₂ + ...a_n = 0
then i considered all the terms in that to be same but alternating signs but that forces n to be odd this was initial line of thought
i am sorry if am not seeing what you are suggesting

If you plug x=1999 into the polynomial you will get a factor of 1999 in every term of the sum. Some terms will have extra factors of 1999. But in the end, the sum is zero if 1999 is a root. Can there be one term with fewer factors of 1999 than the rest? What does that tell you about a₁?

 

[timetraveller123]

oh wow that is smart
$0 = a_n 1999^n + a_{n-1}1999^{n-1} ... + a_1 1999 + 1999\\ 0= a_n 1999^{n-1} + a_{n-1}1999^{n-2} ... + a_1 + 1\\ a_1 = -1999k -1 \\ 0 = a_n 1999^n + a_{n-1}1999^{n-1} ... + (-1999k -1 ) 1999 + 1999\\ 0 = a_n 1999^n + a_{n-1}1999^{n-1} ... + (a_2 - k)1999^2\\ k-a_2 = 1999l\\ 0 = a_n 1999^n + a_{n-1}1999^{n-1} ... +a_3 1999^3 + (-1999l)1999^2\\ l- a_3 = 1999m\\ .\\ .\\ .\\$

$a_1 + a_2 + a_3 ...a_n = -1 -1998k -1998l -1998m ... -1998y - 1999z = 0\\ 1998(k + l + m ... + y) + 1999 z = -1\\$
taking mod 1999
$-1(k + l + m ... + y) + 0 ≡ -1$
how to proceed?
would i be done if i can show k + l + m ... y ≠ 1

 

[Dick]

oh wow that is smart
$0 = a_n 1999^n + a_{n-1}1999^{n-1} ... + a_1 1999 + 1999\\ 0= a_n 1999^{n-1} + a_{n-1}1999^{n-2} ... + a_1 + 1\\ a_1 = -1999k -1 \\ 0 = a_n 1999^n + a_{n-1}1999^{n-1} ... + (-1999k -1 ) 1999 + 1999\\ 0 = a_n 1999^n + a_{n-1}1999^{n-1} ... + (a_2 - k)1999^2\\ k-a_2 = 1999l\\ 0 = a_n 1999^n + a_{n-1}1999^{n-1} ... +a_3 1999^3 + (-1999l)1999^2\\ l- a_3 = 1999m\\ .\\ .\\ .\\$

$a_1 + a_2 + a_3 ...a_n = -1 -1998k -1998l -1998m ... -1998y - 1999z = 0\\ 1998(k + l + m ... + y) + 1999 z = -1\\$
taking mod 1999
$-1(k + l + m ... + y) + 0 ≡ -1$
how to proceed?
would i be done if i can show k + l + m ... y ≠ 1

If you want to think about an alternative approach, can you show that if $n$ and $m$ are integers, that $n-m$ divides $p(n)-p(m)$?

 

[timetraveller123]

what information will i get from showing that

 

[timetraveller123]

i am getting back to where i started
this is what i did someone tell me if this is correct
$\frac{p(l) - p(m)}{l-m}$
for integers l and m

$\frac {\sum{a_i l^i} - \sum{a_i m^i}} {l-m} \\ \sum_{i = 2}^{n}{a_i (\sum_{j=0}^{n-1}{l^i m^{n-1-i}})} + 1999$
hence showing that $\frac{p(l) - p(m)}{l-m} = k$ for some integer k

assuming it has integer root z and p(z) = 0

then
$\frac {p(0) - p(z)} {0 - z} = k\\ \frac{1999}{-z} = k$
once again back to proving it is not 1999

 

[Dick]

i am getting back to where i started
this is what i did someone tell me if this is correct
$\frac{p(l) - p(m)}{l-m}$
for integers l and m

$\frac {\sum{a_i l^i} - \sum{a_i m^i}} {l-m} \\ \sum_{i = 2}^{n}{a_i (\sum_{j=0}^{n-1}{l^i m^{n-1-i}})} + 1999$
hence showing that $\frac{p(l) - p(m)}{l-m} = k$ for some integer k

assuming it has integer root z and p(z) = 0

then
$\frac {p(0) - p(z)} {0 - z} = k \frac{1999}{-z} = k z = \pm 1 && \pm 1999$

Sort of, I think. I don't know what the 1999 is doing in there. But it's pretty well known that $l-m$ divides $l^i-m^i$ for all $i$.

 

[timetraveller123]

no i know that too but now what do i do with the fact that p(m ) - p(n) is divisible by m - n

 

[Dick]

no i know that too but now what do i do with the fact that p(m ) - p(n) is divisible by m - n

Well, think about it. You know $p(0)$, $p(1)$ and you assume that you have an integer root. Put them all together.

 

[timetraveller123]

oh i did this help me check if this correct?
assuming z is a root
$\frac {p(1) - p(z)}{1 - z} = k_1\\ \frac{p(0) - p(z)}{-z} =k_2\\ \frac{199}{1-z} = k_1\\ \frac{1999}{-z} = k_2\\$
this above is not possible as no factors of 1999 are separated by one

 

[Dick]

oh i did this help me check if this correct?
assuming z is a root
$\frac {p(1) - p(z)}{1 - z} = k_1\\ \frac{p(0) - p(z)}{-z} =k_2\\ \frac{199}{1-z} = k_1\\ \frac{1999}{-z} = k_2\\$
this above is not possible as no factors of 1999 are separated by one

Sure. $z$ and $z-1$ must divide 1999. That's impossible.

 

[timetraveller123]

wow that was easy thanks a lot
is this is a standard trick in solving such problems
but can you help me with proving 1999 is not a root of the polynomial

 

[Dick]

wow that was easy thanks a lot
is this is a standard trick in solving such problems
but can you help me with proving 1999 is not a root of the polynomial

I don't know that it's a standard anything. It's just something I thought of thinking about the problem. Showing there are no integer roots pretty much rules out 1999 being a root. If you mean an alternative way like haruspex and Buffu were suggesting, I'm not sure. Maybe they would like to elaborate...

 

[Buffu]

I don't know that it's a standard anything. It's just something I thought of thinking about the problem. Showing there are no integer roots pretty much rules out 1999 being a root. If you mean an alternative way like haruspex and Buffu were suggesting, I'm not sure. Maybe they would like to elaborate...

I think I have to say sorry because now I don't know how to prove $1999$ is not a root. When I saw this question I scribbled something on paper which looked convincing to me at that point as a proof but now I look at it again I think I am missing one key element. I am really sorry.

Here is my approach, I think one key information is missing,

Using vieta's formula,

$\dfrac{|a_1|}{|a_n|} = |r_2 ... r_n + r_1 r_3 ... r_n + ... + r_1 r_2... r_{n-1}|$

$|a_1| =r_1 \left| \dfrac{1}{r_1} + \dfrac{1}{r_2} + \cdots + \dfrac1{r_n}\right|$

I thought it was easy enough to see that $a_1$ is not a integer if $r_1 = 1999$ but now that I look at the proof again I see that I don't have any convincing argument to prove that $\left| \dfrac{1}{r_1} + \dfrac{1}{r_2} + \cdots + \dfrac1{r_n}\right|$ is not a integer.

I think @haruspex have a proof that 1999 is not root.

 

[haruspex]

I think @haruspex have a proof that 1999 is not root

Like you, I thought I did, but it didn't pan out. I could show (if 1999 is a root) that a₁=-1 and that 1999 must divide a₂ exactly once more than it divides a₃. After that it petered out.
An interesting corollary of Dick's observation is that if a polynomial has integer coefficients then the gradient between two integer values of x is also an integer.

can you help me with proving 1999 is not a root of the polynomial

Haven't you proved that in post #28?

 

[timetraveller123]

yup that happened to me too at first before i posted here happens to every one but thanks a lot
@haruspex
how did you show if r₁ is 1999 then a₁ = -1 please tell me
@Dick
what i want to know how did you just pull out such a thing like how did you notice about the formula you said that's what i want to know that's why i asked if it is a standard thing and it is astonishing to me that you randomly thought of that please tell me thanks every one

 

[Dick]

yup that happened to me too at first before i posted here happens to every one but thanks a lot
@haruspex
how did you show if r₁ is 1999 then a₁ = -1 please tell me
@Dick
what i want to know how did you just pull out such a thing like how did you notice about the formula you said that's what i want to know that's why i asked if it is a standard thing and it is astonishing to me that you randomly thought of that please tell me thanks every one

Well, it wasn't exactly 'random'. I thought if there is a root then $f(n)=0$ for some $n$. Ok, so $f(n)-f(0)=f(n)-f(1)=-1999$ and 1999 is prime. Must be something wrong with that. Must be a factor. Then look at the differences and notice things like $n^i-1^i$ have $n-1$ as a factor. That's all. It's not that big a leap if you think along the right lines. Getting stuck trying to get the result using the rational roots theorem appears to be a bit of a trap.