Proof: polynomial with integer solutions

In summary, the author is stuck and needs help proving that a polynomial with integer coefficients cannot have integer solutions. The lemma proposed states that if two different integers are given, then there must be a difference between the two that divides 1. However, when trying to use the lemma to prove that the polynomial cannot have integer solutions, the author gets stuck.
  • #1
Johulus
6
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
  • #2
Let's begin by writing:

\(\displaystyle 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:

\(\displaystyle (m-n)|(f(m)-f(n))\)

In order to prove this, observe that:

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

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

Okay, we are given:

\(\displaystyle f(a)=f(b)=f(c)=-1\)

Now suppose:

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

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

\(\displaystyle 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:

\(\displaystyle (m-n)|(f(m)-f(n))\)

In order to prove this, observe that:

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

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

Okay, we are given:

\(\displaystyle f(a)=f(b)=f(c)=-1\)

Now suppose:

\(\displaystyle 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:

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

The condition that task states is:

\(\displaystyle a,b,c\in\mathbb{Z}, a \neq b \neq c\)

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

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

\(\displaystyle (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, \(\displaystyle (a-b)|(f(a)-f(b))\) is true. But...

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

And \(\displaystyle (a-d)|(f(a)-f(d))\) is true only if \(\displaystyle a-d \in{\{1,-1\}} \implies d=a-1\) or \(\displaystyle 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.
 
  • #4
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:

\(\displaystyle (d-a)|(f(d)-f(a))=0-(-1) = 1\)

\(\displaystyle (d-b)|(f(d)-f(b))=0-(-1) = 1\)

\(\displaystyle (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?
 
  • #5
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:

\(\displaystyle (d-a)|(f(d)-f(a))=0-(-1) = 1\)

\(\displaystyle (d-b)|(f(d)-f(b))=0-(-1) = 1\)

\(\displaystyle (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

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

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

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

Since 1 has two divisors -1 and 1, then at least two of \(\displaystyle (d-a), \, (d-b), \, (d-c)\) have to be the same.
Let's suppose \(\displaystyle (d-a)=(d-b)=-1 \, (d-c)=1\). Then we have: \(\displaystyle (d-a)=(d-b) \implies a=b \).
But, the condition at the beginning states that \(\displaystyle a \neq b \neq c \). So, this is in contradiction. Can I draw any conclusion from that?
 
  • #6
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.
 
  • #7
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 \(\displaystyle a=b \) contradicted to \(\displaystyle a \neq b \neq c \) proves that \(\displaystyle \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.
 
  • #8
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
 
  • #9
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.
 

FAQ: Proof: polynomial with integer solutions

1. What is a polynomial with integer solutions?

A polynomial with integer solutions is an algebraic expression that can be written in the form of ax^n + bx^(n-1) + ... + k, where a, b, and k are integers and n is a positive integer. This means that when the variables in the polynomial are replaced with integers, the expression will result in a whole number.

2. How do you prove that a polynomial has integer solutions?

To prove that a polynomial has integer solutions, you can use the Rational Root Theorem. This theorem states that any rational root of a polynomial must be a factor of the constant term divided by a factor of the leading coefficient. By testing all possible rational roots, you can determine if the polynomial has any integer solutions.

3. Can a polynomial have both integer and non-integer solutions?

Yes, a polynomial can have both integer and non-integer solutions. However, if a polynomial has at least one integer solution, it is said to have at least one rational solution. This is because all integers can also be written as fractions with a denominator of 1, making them rational numbers.

4. Are all polynomials with integer coefficients guaranteed to have integer solutions?

No, not all polynomials with integer coefficients will have integer solutions. For example, the polynomial x^2 + 2x + 3 has integer coefficients, but does not have any integer solutions. However, if a polynomial is of a specific form (such as a quadratic or cubic polynomial), it may have integer solutions, which can be determined using different methods.

5. What is the significance of proving a polynomial has integer solutions?

Proving that a polynomial has integer solutions can be useful in many applications, such as in number theory or in solving real-world problems. It also allows us to better understand the behavior of polynomials and their relationship to integers. In addition, it can serve as a starting point for finding more precise solutions to the polynomial, such as rational or irrational solutions.

Similar threads

MHB Polynomial with integer coefficients
Replies
1
Views
1K
MHB Polynomial challenge: Show that not all the coefficients of f(x) are integers.
Replies
3
Views
1K
MHB Prove No Integers Solve $ax^3+bx^2+cx+d=1$ for x=19,2 for x=62
Replies
3
Views
1K
MHB Compute $\sum_{n=1}^{2020} (f(n)-g(n))$
Replies
1
Views
912
MHB Expressing a polynomial P(x)=(x−a)^2(x−b)^2+1 by two other polynomials
Replies
2
Views
1K
A Variation of Catalan Conjecture
Replies
22
Views
2K
I Proof for interpolating polynomial and error approximation
Replies
6
Views
859
A Prime Number Powers of Integers and Fermat's Last Theorem
Replies
1
Views
1K
I Proof: If a Polynomial & its Derivative have Same Root
Replies
3
Views
1K
I Are there any two pairs of integers with the same result in a specific function?
Replies
7
Views
1K

Hot Threads

Recent Insights

Back
Top