6
$\begingroup$

Prove or disprove the following statment: For all integers b, c,and d, if x is a rational number such that $x^2+bx+c=d$, then x is an integer.

This is a homework question from the book Discrete Mathematics for Computer Scientists by Stein, Drysdale and Bogart.

I since x is rational I thought I could start off with:

${(\frac{m}{n})}^2+b\frac{m}{n}=d-c$

But I don't know where to go from here.

Or I could try using the quadratic formula

$x=\frac{1}{2}\left(\pm\sqrt{b^{2}-4c+4d}-b\right)$

but I am very weak with elementary number theory that I don't know where to go. I am thinking that regardless of if $\sqrt{b^{2}-4c+4d}$ is an integer or not, the fact that I have

$x=\frac{1}{2}*\pm$ SomeNumber

means that x is not an integer.

I am new to writing proofs, and unfortunately, I don't really know how to prove this. Any hints would be appreciated.

Thank you.

Edit: By plugging in simple numbers, for example x=1, b=1, c=1 and d=3 I can see that x is probably an integer, for all integers b,c,and d - so that means my thinking about the quadratic formula is not correct. I will still work on this.

2nd Edit: Now I plug in more numbers and don't get integers. For example $x^2+2x+3=4$. I am also new to this site, so I am not sure if I should continue to edit the post or write in the comments sections anytime I think of something new. Please advise.

3rd Edit: I think I know what to do. The last section of the book covered universal quantifiers. I believe the authors are are trying to get me to realize that they are saying $\forall b, c, d \in Z$ and I only need to give one one example for which the assertion is untrue. And in my previous edit, b=2, c=3, and d=4 did not result in x being an integer.

  • 0
    $x^2 + 2x + 3 = 4$ does not provide a counterexample since the solutions to that equation are not rational anyways.2011-03-12

2 Answers 2

4

This is simply the monic quadratic case of the Rational Root Test. You could specialize that proof, or else proceed similarly to various irrationality proofs for square-roots. $\: $ E.g. $\:$ below is a proof that I discovered in high-school. First I present the proof for square-roots - where the idea is clearer.

THEOREM $\ $ For $\rm\: c\in \mathbb Z\:,\:$ any rational root $\rm\:r\:$ of $\rm\ x^2 = c\ $ is integral.

Proof $\ $ Put $\rm\ r = m/n\ $ with $\rm\:(m,n) = 1\:.\:$ Then $\rm\ j\ m-k\ n \;=\; 1\;$ for some $\:\rm j,k \in \mathbb{Z}\;\;$ by Bezout.

Hence $\;\;\:\rm 0\: =\: (m-n\:r)\:(k+j\:r) \:=\: mk-njc + (j\ m-k\ n)\ r \ \Rightarrow\ r = -mk+njc \ \in\ \mathbb{Z}\quad$ QED

This proof easily extends to the root of a general monic quadratic as follows.

THEOREM $\ $ For $\rm\:b,c\in\mathbb Z\:,\:$ any rational root $\rm\:r\:$ of $\rm\ x^2 = b\ x + c\ $ is integral.

Proof $\ $ Put $\rm\ r = m/n,\ (m,n)=1\:.\ $ Then $\rm\:(m-nb,n)=1\ $ so $\rm\ \exists\ j,k\in \mathbb Z\: :\ 1 = j\ (m-nb)-k\ n $

Hence $\rm\ 0 = (m-n\:r)\:(k+j\:r)\ =mk + (jm-kn)\:r-nj\:(br+c) = mk-njc + (j\ (m-nb)-k\ n)\ r$

But the coefficient of $\rm\:r\:$ in the prior term is $1\:,\ $ so we deduce $\rm\ r \:=\: -mk+njc \ \in\ \mathbb Z\quad$ QED

If you learn about denominator ideals then you'll see that the above proof simply says that the denominator ideal of $\rm\:r\:$ contains $\rm\:n\:$ and $\rm\:n\:r = m\:,\:$ so it contains their gcd $\rm\:(n,m) = 1\:,\ $ so $\rm\ r\in \mathbb Z\:.$ Using Dedekind's notion of conductor ideal, the proof easily generalizes to higher degree monic polynomials, yielding that PIDs are integrally closed.

  • 0
    @garrett: In the initial version of the proof $\rm\:x\:$ could be read to denote either a rational number or an indeterminate. Either interpretation works. In the latter case one concludes that every root $\rm\:r\:$ of $\rm\ x^2 = c\ $ is also a root of $\rm\ x = d,\ d\in \mathbb Z\ $ so $\rm\ r = d\in \mathbb Z\:.\:$ To avoid any further confusion I've replaced $\rm\:x\:$ by $\rm\:r\:$ in the proof. I think you'll find that clearer. Also in my above comment I mean to say that $\rm\ (m-nr)(k+jr)\ $ is a product of rationals, not integers (the first factor is zero, the second a rational).2011-03-13
2

Hint: First, you can combine $c$ and $d$ as you only care about their difference. There is the theorem that the square root of a positive integer is either integer or irrational. You are right that one example disproves the assertion "for all b,c, and d".

Added: If you look at the quadratic formula, the only threat to x being integral (if it is rational) is the division by 2. But if the square root is integral, it must have the same parity as b.