# For all integers b, c, and d, if x is rational such that x^2+bx+c=d, then x is an integer

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.

-
Be careful: x = 1/2 * (some number) does not mean that x is not an integer since (some number) could be a multiple of 2. –  Eric O. Korman Mar 12 '11 at 2:43
@Eric Thanks for pointing that out, your absolutely correct. –  garrett Mar 12 '11 at 2:50
Your quadratic formula should be $x=\frac{1}{2}\left(\pm\sqrt{b^{2}-4c+4d}-b\right)$ –  Henry Mar 12 '11 at 3:14
Thanks @Henry, I made the change. –  garrett Mar 12 '11 at 3:28
$x^2 + 2x + 3 = 4$ does not provide a counterexample since the solutions to that equation are not rational anyways. –  Eric O. Korman Mar 12 '11 at 3:42

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.

-
Thanks for answering. I understand most of this proof except $(m-nx)(k+jx)$. If you have time, would you please explain what $(m-nx)(k+jx)$ means? –  garrett Mar 12 '11 at 14:29
It's just the product of those two integers. Perhaps you are confusing this bracketing use of parentheses with their above use as gcd-as-tuple notation $\rm\ (m,n) := gcd(m,n)\$ Or perhaps you are asking if their is some deeper meaning behind that product. The idea is to find a smaller coefficient of $\rm\:x\:,\:$ i.e. a smaller denominator for it - see the links. –  Bill Dubuque Mar 12 '11 at 17:29
I get that $x^2=c$ and that we want to set $x=m/n$. I also understand that we want $m$ and $n$ to be relatively prime, so $gcd(m,n)=1$. Also $jm-kn=1$, I just learned that by studying the Extended Euclidean algorithm. What I don't understand is the very next part: Hence $0=(m-nx)(k+jx)$. I know the algebra afterwards, just not where $0=(m-nx)(k+jx)$ came from. It seems I am missing some elementary steps to make the leap to $0=(m-nx)(k+jx)$. –  garrett Mar 12 '11 at 21:16
$\rm (x = m/n)\$ times $\rm\:n\ \to\ n\ x = m\$ so $\rm\ m - n\ x\ =\ 0\ \$ –  Bill Dubuque Mar 12 '11 at 22:20
@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). –  Bill Dubuque Mar 13 '11 at 18:53

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.

-