# Let k be an integer. Disprove: “The equation $x^2 − x − k = 0$ has no integer solution if and only if $k$ is odd.”

My problem is I keep ending up proving the statement true, instead of disproving it. I was getting it mixed up in my mind so I broke it down into very explicit steps but now I'm wondering if I'm overthinking it?

I started out proving that if there is no integer solution, then k is even (one negation of the statement, $$P$$ and not $$Q$$ where $$P = \text{ no integer solution and } Q = k \text{ is odd}$$). By contrapositive I try to prove that if $$k$$ is odd then there is an integer solution (I quickly recognized this is the same as the other negation, $$Q$$ and not $$P$$, so this is the only thing I need to prove).

So $$k = 2n + 1$$ for any integer $$n$$. Then $$x^2-x -(2n+1) = 0$$. So $$x^2-x=2n+1$$. But if $$x$$ is an integer then $$x^2-x$$ must always be even, and cannot equal an odd integer $$2n+1$$. So this has led to a contradiction, which means I just proved that if k is odd then there is no integer solution.

Is my logic off somewhere, or should I be approaching it differently? Sorry if this has an obvious answer, I only started doing proofs this quarter. Thanks

• You proved in the end that ($k$ is odd) $\implies$ (no integer solutions). Now you still have to prove the sufficient condition and that is if there is (no integer solutions) $\implies$ ($k$ is odd), which is equivalent to proving ($k$ is not odd) $\implies$ (there exist an integer solution). I think you didn't prove this, am I right? – Fareed Abi Farraj Jan 23 at 7:34
• If k is negative (say -2) then there are clearly no real solutions at all as x^2-x is never smaller than -1/4. – RemcoGerlich Jan 23 at 10:58

You seem to be struggling with the logic involved here. The statement is $$k\text{ is odd}\iff x^2-x-k=0\text{ has no integer solutions}$$ Yes, it seems that making $$k$$ odd makes the equation have no integer solutions (in other words, the $$\implies$$ direction is true). Your proof of this looks fine.

However, the statement also claims that if there are no integer solutions, then $$k$$ is odd (the $$\Longleftarrow$$ direction). The contrapositive of this claim is that making $$k$$ even will always result in an integer solution. This is disproven by providing a single counterexample.

Hint:

$$x^2-x-k=0 \Rightarrow x=\frac{1 \pm \sqrt{4k+1}}{2}$$

So $$x$$ can only be an integer if $$4k+1$$ is the square of an odd number.

This is true when $$k=2$$, in which case $$\sqrt{4k+1}=3$$, and when $$k=6$$, in which case $$\sqrt{4k+1}=5$$.

But what about when $$k=4$$ ?

Lets assume that equation has integer solutions, so $$x \in Z$$

$$x^2-x = k$$

$$x (x-1) = k$$

$$x-1$$ and $$x$$ are two consecutive integer numbers, their product is even $$\Rightarrow k$$ is even

• I like this approach. What would make it complete is a quick listing of products of consecutive integers: $2\cdot 3=6,\ 3\cdot 4=12,\ 4\cdot 5=20$ etc. That would illustrate that there are many even values of $k$ ($8,10,14, 16,18,\dots$) that are not solutions. It is necessary that $k$ be even, but not sufficient for the equation to have integer solutions. – Keith Backman Jan 23 at 18:03