Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.