MHB Proof: polynomial with integer solutions

Johulus
Messages
6
Reaction score
0
I am stuck with one proof and I need some help because I don't have any idea how to proceed at this moment. The task says: If f(x) is a polynomial with integer coefficients, and if f(a)=f(b)=f(c)=-1, where a,b,c are three unequal integers, the equation f(x)=0 does not have integer solutions. Prove!

I know that if there is a polynomial with integer coefficients and if it has integer solutions, then those solutions are divisors of coefficient that does not have an 'x' next to it. But, I don't know how to use that fact along with f(a)=f(b)=f(c)=-1. So, I'm currently stuck and I hope someone could help me do something here.
 
Mathematics news on Phys.org
Let's begin by writing:

$$f(x)=\sum_{k=0}^{n}a_kx^k$$ where $a_k\in\mathbb{Z}$

Now, let's propose the following lemma:

For any two different integers $m$ and $n$, we must have:

$$(m-n)|(f(m)-f(n))$$

In order to prove this, observe that:

$$f(m)-f(n)=\sum_{k=1}^{n}a_k(m^k-n^k)$$

Since $$(m-n)|(m^k-n^k)$$ for all $0<k$, the lemma follows.

Okay, we are given:

$$f(a)=f(b)=f(c)=-1$$

Now suppose:

$$f(d)=0$$ where $d$ is an integer distinct from $a,\,b,\,c$.

What do we then obtain from our lemma?
 
MarkFL said:
Let's begin by writing:

$$f(x)=\sum_{k=0}^{n}a_kx^k$$ where $a_k\in\mathbb{Z}$

Now, let's propose the following lemma:

For any two different integers $m$ and $n$, we must have:

$$(m-n)|(f(m)-f(n))$$

In order to prove this, observe that:

$$f(m)-f(n)=\sum_{k=1}^{n}a_k(m^k-n^k)$$

Since $$(m-n)|(m^k-n^k)$$ for all $0<k$, the lemma follows.

Okay, we are given:

$$f(a)=f(b)=f(c)=-1$$

Now suppose:

$$f(d)=0$$ where $d$ is an integer distinct from $a,\,b,\,c$.

What do we then obtain from our lemma?

I would just like to say before I write anything else that I am not that experienced with this but I would really like to figure this proof out.

The first problem is that I am not that familiar with the meaning of the word lemma. But I looked for its meaning now,so I guess it's kind of clear what it means now. And I understand why that lemma you proposed is true, but I am not sure how it relates to proving that this polynomial can't have integer solutions for given condition. Well, the only thing that I can observe here is:

Our proposed lemma states that:

$$(m-n)|(f(m)-f(n)), \forall m,n\in\mathbb{Z}, m\neq n$$

The condition that task states is:

$$a,b,c\in\mathbb{Z}, a \neq b \neq c$$

So, the condition of lemma $$m \neq n $$ is satisfied if $$ m,n\in{\{a,b,c\}} $$.

We know that $$f(a)=f(b)=f(c)=-1 $$ and let's propose that $$f(d)=0, d\in\mathbb{Z}, d \neq a \neq b \neq c $$. The only thing that I can observe now is:

$$ (a-b)|(f(a)-f(b)) \implies \dfrac{f(a)-f(b)}{a-b}=\dfrac{-1-(-1)}{a-b}=\dfrac{0}{a-b}=0 $$

So, $$ (a-b)|(f(a)-f(b))$$ is true. But...

$$ (a-d)|(f(a)-f(d)) \implies \dfrac{f(a)-f(d)}{a-d}=\dfrac{-1-0}{a-d}=\dfrac{-1}{a-d} $$

And $$ (a-d)|(f(a)-f(d))$$ is true only if $$ a-d \in{\{1,-1\}} \implies d=a-1$$ or $$ d=a+1 $$.

Anyway, I probably got into a completely wrong direction and I don't know what to do with it now. Maybe I should just take a rest from it to clear out my thoughts.
 
I really just meant "lemma" as a theorem we could use in our proof. So, what I had in mind was to then observe that:

$$(d-a)|(f(d)-f(a))=0-(-1) = 1$$

$$(d-b)|(f(d)-f(b))=0-(-1) = 1$$

$$(d-c)|(f(d)-f(c))=0-(-1) = 1$$

So, these 3 differences $(d-a,\,d-b,\,d-c)$ all divide 1. How many divisors does 1 have?
 
MarkFL said:
I really just meant "lemma" as a theorem we could use in our proof. So, what I had in mind was to then observe that:

$$(d-a)|(f(d)-f(a))=0-(-1) = 1$$

$$(d-b)|(f(d)-f(b))=0-(-1) = 1$$

$$(d-c)|(f(d)-f(c))=0-(-1) = 1$$

So, these 3 differences $(d-a,\,d-b,\,d-c)$ all divide 1. How many divisors does 1 have?

1 can be divided by -1 and 1... right?

Since

$$(d-a)|(f(d)-f(a)) \qquad (d-b)|(f(d)-f(b)) \qquad (d-c)|(f(d)-f(c))$$

$$ (f(d)-f(a))=(f(d)-f(b))=(f(d)-f(c))=1 $$, that is:

$$(d-a)|1 \qquad (d-b)|1 \qquad (d-c)|1$$

Since 1 has two divisors -1 and 1, then at least two of $$(d-a), \, (d-b), \, (d-c)$$ have to be the same.
Let's suppose $$(d-a)=(d-b)=-1 \, (d-c)=1$$. Then we have: $$(d-a)=(d-b) \implies a=b $$.
But, the condition at the beginning states that $$ a \neq b \neq c $$. So, this is in contradiction. Can I draw any conclusion from that?
 
Yes, good! (Yes)

Since we have found that $a,\,b,\,c,\,$ cannot all be distinct, we have proved the given proposition by contradiction. We started by positing the opposite proposition is true, and then showed that such an assumption leads to a contradiction.
 
MarkFL said:
Yes, good! (Yes)

Since we have found that $a,\,b,\,c,\,$ cannot all be distinct, we have proved the given proposition by contradiction. We started by positing the opposite proposition is true, and then showed that such an assumption leads to a contradiction.

I am still not completely sure how $$ a=b $$ contradicted to $$ a \neq b \neq c $$ proves that $$ \nexists x\in\mathbb{Z}: f(x)=0 $$.

I am not sure what do you mean when referring to 'opposite proposition'? That kind of bothers me. Opposite of what?

I will have a look at it tomorrow.

But thank you very much on your effort.
 
Essentially, we were asked to show that there is no $d$ such that $f(d)=0$...so we made the assumption that there IS a $d$ such that $f(d)=0$, and then demonstrated that this assumption led to a contradiction of the conditions of the problem. This effectively proves that there is no $d$ such that $f(d)=0$, subject to the conditions of the problem...and this is what we were asked to do. :D
 
MarkFL said:
Essentially, we were asked to show that there is no $d$ such that $f(d)=0$...so we made the assumption that there IS a $d$ such that $f(d)=0$, and then demonstrated that this assumption led to a contradiction of the conditions of the problem. This effectively proves that there is no $d$ such that $f(d)=0$, subject to the conditions of the problem...and this is what we were asked to do. :D

Thank you so very much :) ! You've helped a big deal. I understand everything now. I've mixed up conditions with assumption and everything but now it's all clear.
 
Back
Top