# How can I complete this proof by contradiction?

This problem is from Discrete Mathematics and its Applications:

Prove that there are no solutions in integers $$x$$ and $$y$$ to the equation $$2x^2 + 5y^2 = 14$$.

I am trying to use proof by contradiction, which is described by the book as

Suppose we want to prove that a statement $$p$$ is true. Furthermore, suppose that we can find a contradiction $$q$$ such that $$\lnot p \implies q$$ is true. Because $$q$$ is false, but $$\lnot p \implies q$$ is true, we can conclude that $$\lnot p$$ is false, which means that $$p$$ is true. How can we find a contradiction $$q$$ that might help us prove that $$p$$ is true in this way?

Because the statement $$r \land \lnot r$$ is a contradiction whenever $$r$$ is a proposition, we can prove that $$p$$ is true if we can show that $$\lnot p \implies (r \land \lnot r)$$ is true for some proposition $$r$$. Proofs of this type are called proofs by contradiction. Because a proof by contradiction does not prove a result directly, it is another type of indirect proof.

Here is my work/thought process:

My initial proposition, $$p$$, is that there are no solutions in integers $$x$$ and $$y$$ to the equation $$2x^2 + 5y^2 = 14$$. I know that by proof by contradiction, I have to assume that the proposition isn't true, $$\lnot p$$, meaning there is a solution to $$x$$ and $$y$$ in the equation and show that assuming this leads to a contradiction (something that always evaluates to false, no matter the input values).

First, I recognized that for the sum be even, $$14$$, the two components, $$2x^2$$ and $$5y^2$$ have to be even as well.

I am able to show that $$2x^2$$ is even from the definition of even, that is, there is some integer $$k$$ such that $$2x^2 = 2k$$. $$k$$ would be $$x^2$$. However I have a hard time showing that $$5y^2$$ cannot be even. I first tried the same definition, meaning $$k = (5/2) y^2$$ but this wouldn't be an integer. However it is possible for $$5y^2$$ to be even, say $$y = 10$$. Am I going about this the right way? Is the even + even justification appropriate for this situation?

• +1 I love this question. You're fully engaged with the question you're studying. Jan 17, 2015 at 0:05

Yes, a proof by contradiction can be given. Suppose you have found a pair $(x,y)$ satisfying the equation.

Since $14$ and $2x^2$ are even, also $5y^2$ must be even as well. Therefore $y$ is even and so $y=2z$ for some integer $z$.

This implies $2x^2+20z^2=14$ that simplifies to $x^2+10z^2=7$. But $10z^2>7$ if $z\ne0$, so we must have $z=0$ and so $x^2=7$, a contradiction.

About your argument, there's a glitch. Since $14$ is even, two integers that sum to $14$ are either both even or both odd. However, since $2x^2$ is clearly even, you can conclude (as I did above) that also $5y^2$ must be even.

• because if this was the case, x would not even be an integer Jan 17, 2015 at 1:43
• @committedandroider Yes, $7$ is not a perfect square. Jan 17, 2015 at 10:41
• In summary, the conclusion from this would - Let's assume there are positive integers x and y such such that 2x^2 + 5y^2 = 14. Then integer x must be equal to the square root of 7 which itself is a contradiction because no integer x can be equal to the square root of 7(all inputs evaluate to false). Therefore by proof by contradiction, there are no such integers x and y. Jan 27, 2015 at 19:59

HINT: You’ll have a very hard time proving it this way. I recommend a different approach altogether. Note that $x^2$ and $y^2$ are non-negative, so $2x^2$ and $5y^2$ are at most $14$. Thus, if $y$ is an integer, then $y$ must be one of three integers; what are they? And what do they force $2x^2$ to be?

Added: And you can use your observation that $y$ must be even to reduce the possibilities still further.

• For possible values of $y$, couldn't you eliminate all integers $n$ where $|n|>1$? Jan 16, 2015 at 23:53
• @graydad: Yep; thanks. (No, of course not: $n^2=n$ for all $n\in\Bbb Z$! :-)) Jan 16, 2015 at 23:57
• No sweat, I think the edited version of your answer is more thought provoking :) Jan 16, 2015 at 23:59
• Also, $y$ must be even, since $2x^2$ and $14$ are both even. Jan 17, 2015 at 0:04
• Are at most 14? They can be arbitrarily large. I think you meant "almost 14" which restricts how big y and x can be: nice thinking
– Mzn
Jan 17, 2015 at 19:55

Roundabout proof (not the one you should use :-) ):

$x^2 \equiv \{0,1,4,5,6,9\}\mod 10$

$\Rightarrow 2x^2 \equiv \{0,2,8,10,12,18\}\mod 20$

$y^2 \equiv \{0,1\}\mod 4$

$\Rightarrow 5y^2 \equiv \{0,5\}\mod 20$

$\Rightarrow 2x^2+5y^2 \equiv \{0,2,3,5,7,8,10,12,13,15,17,18\}\mod 20$

$\Rightarrow 2x^2+5y^2 \not\equiv 14\mod 20$

$\Rightarrow 2x^2+5y^2 \neq 14$

• Nice appoarch. X squared mod 10 is one of {0,1,4,5,6,9}? Would you please provide proof or reasoning?
– Mzn
Jan 17, 2015 at 8:19
• Those are the quadratic residues mod 10. Examination of the first ten squares gives you these: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100. After that $(x+10)^2 = x^2+20x+10^2 \equiv x^2 \mod 10$ Jan 17, 2015 at 8:24
• I see. Proof by induction. Thanks
– Mzn
Jan 17, 2015 at 11:55
• Well, could be, or I could been less lazy and said $(x+10k)^2 = x^2+20kx+10^2k^2 \equiv x^2 \mod 10$ :-) Jan 17, 2015 at 17:37
• Do you know of any introductory source on this topic? en.wikipedia.org/wiki/Quadratic_residue seems advanced to me :)
– Mzn
Jan 17, 2015 at 19:06

If you want to make your proof work, first note that $y = 0$ is not an option because then you would have $x^2 = 7$. As you noted, $5y^2$ must be even, so $y$ must be even, hence $y^2$ is at least 4. This gives a sum which is too big. (at least 20 when your target is 14)