# Proving a polynomial has no integer solution

• timetraveller123
In summary: Sorry, I misread what you wrote. You're saying that 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. Is that what you meant to say?
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

## The Attempt at a Solution

##
p(x) = \sum_{i= 0}^{n}{a_i x^i}
##[/B]
using the given information
a0 = 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

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

vishnu 73 said:
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

vishnu 73 said:
##
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 ?

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

Buffu
vishnu 73 said:
you mean the roots
Sorry. Yes I mean roots.

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

vishnu 73 said:
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

Last edited:
vishnu 73 said:
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|##

timetraveller123
vishnu 73 said:
please give me hints for the next two roots
If 1999 is a root, how many times might 1999 divide ai1999i? Given that it divides a0 exactly once, what does that tell you about a1? Then, what about the relationship between a2 and a3?

Last edited:
@haruspex
haruspex said:
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 ?

vishnu 73 said:
i think what @Buffu wrote is correct
Ok, I misinterpreted the ...

vishnu 73 said:
##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
haruspex said:
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 an
should i be writing ## \mid a_n \mid ## as ## \mid a_1 + a_2 ... a_{n-1} \mid ## does that help

Last edited:
vishnu 73 said:
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 an
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?

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

@ haruspex
are you hinting at geometric series
because i thought of it at first but the fact that a2 + ...an = 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

vishnu 73 said:
@ haruspex
are you hinting at geometric series
because i thought of it at first but the fact that a2 + ...an = 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 a1?

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

Last edited:
vishnu 73 said:
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)##?

haruspex and timetraveller123
what information will i get from showing that

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

vishnu 73 said:
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##.

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

vishnu 73 said:
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

Buffu
vishnu 73 said:
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.

Buffu and 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

vishnu 73 said:
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...

timetraveller123
Dick said:
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.

Buffu said:
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 a1=-1 and that 1999 must divide a2 exactly once more than it divides a3. 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.
vishnu 73 said:
can you help me with proving 1999 is not a root of the polynomial
Haven't you proved that in post #28?

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 r1 is 1999 then a1 = -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

vishnu 73 said:
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 r1 is 1999 then a1 = -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.

<h2>1. What does it mean for a polynomial to have no integer solution?</h2><p>When a polynomial has no integer solution, it means that there is no value for the variable in the polynomial that would result in a whole number when plugged in. In other words, there are no integers that satisfy the equation.</p><h2>2. How can I prove that a polynomial has no integer solution?</h2><p>There are a few methods for proving that a polynomial has no integer solution. One way is to use the Rational Root Theorem to test all possible rational roots of the polynomial. If none of these roots result in a whole number, then the polynomial has no integer solution. Another method is to use the Fundamental Theorem of Algebra, which states that a polynomial of degree n has at most n complex roots. If the polynomial has a degree of n and no integer roots, then it must have no roots at all.</p><h2>3. Can a polynomial have no integer solution but still have real solutions?</h2><p>Yes, it is possible for a polynomial to have no integer solution but still have real solutions. For example, the polynomial x^2 + 1 has no integer solution, but it has two complex solutions (i.e. solutions that involve the imaginary number i).</p><h2>4. Are there any shortcuts for proving that a polynomial has no integer solution?</h2><p>Unfortunately, there are no shortcuts for proving that a polynomial has no integer solution. The best way to prove this is to use the methods mentioned in question 2, such as the Rational Root Theorem or the Fundamental Theorem of Algebra.</p><h2>5. Can a polynomial have an infinite number of integer solutions?</h2><p>No, a polynomial cannot have an infinite number of integer solutions. This is because a polynomial of degree n can have at most n distinct roots. Therefore, the number of integer solutions is limited by the degree of the polynomial.</p>

## 1. What does it mean for a polynomial to have no integer solution?

When a polynomial has no integer solution, it means that there is no value for the variable in the polynomial that would result in a whole number when plugged in. In other words, there are no integers that satisfy the equation.

## 2. How can I prove that a polynomial has no integer solution?

There are a few methods for proving that a polynomial has no integer solution. One way is to use the Rational Root Theorem to test all possible rational roots of the polynomial. If none of these roots result in a whole number, then the polynomial has no integer solution. Another method is to use the Fundamental Theorem of Algebra, which states that a polynomial of degree n has at most n complex roots. If the polynomial has a degree of n and no integer roots, then it must have no roots at all.

## 3. Can a polynomial have no integer solution but still have real solutions?

Yes, it is possible for a polynomial to have no integer solution but still have real solutions. For example, the polynomial x^2 + 1 has no integer solution, but it has two complex solutions (i.e. solutions that involve the imaginary number i).

## 4. Are there any shortcuts for proving that a polynomial has no integer solution?

Unfortunately, there are no shortcuts for proving that a polynomial has no integer solution. The best way to prove this is to use the methods mentioned in question 2, such as the Rational Root Theorem or the Fundamental Theorem of Algebra.

## 5. Can a polynomial have an infinite number of integer solutions?

No, a polynomial cannot have an infinite number of integer solutions. This is because a polynomial of degree n can have at most n distinct roots. Therefore, the number of integer solutions is limited by the degree of the polynomial.

• Precalculus Mathematics Homework Help
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
12
Views
2K
• Precalculus Mathematics Homework Help
Replies
14
Views
2K
• Calculus and Beyond Homework Help
Replies
7
Views
454
• Precalculus Mathematics Homework Help
Replies
20
Views
2K
• Precalculus Mathematics Homework Help
Replies
8
Views
8K
• Precalculus Mathematics Homework Help
Replies
9
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
506
• Precalculus Mathematics Homework Help
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
1K