10
$\begingroup$

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?

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

4 Answers 4

9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ because if this was the case, x would not even be an integer $\endgroup$ Jan 17, 2015 at 1:43
  • $\begingroup$ @committedandroider Yes, $7$ is not a perfect square. $\endgroup$
    – egreg
    Jan 17, 2015 at 10:41
  • $\begingroup$ 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. $\endgroup$ Jan 27, 2015 at 19:59
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ For possible values of $y$, couldn't you eliminate all integers $n$ where $|n|>1$? $\endgroup$
    – graydad
    Jan 16, 2015 at 23:53
  • $\begingroup$ @graydad: Yep; thanks. (No, of course not: $n^2=n$ for all $n\in\Bbb Z$! :-)) $\endgroup$ Jan 16, 2015 at 23:57
  • $\begingroup$ No sweat, I think the edited version of your answer is more thought provoking :) $\endgroup$
    – graydad
    Jan 16, 2015 at 23:59
  • $\begingroup$ Also, $ y $ must be even, since $ 2x^2 $ and $ 14 $ are both even. $\endgroup$
    – gamma
    Jan 17, 2015 at 0:04
  • $\begingroup$ 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 $\endgroup$
    – Mzn
    Jan 17, 2015 at 19:55
1
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ Nice appoarch. X squared mod 10 is one of {0,1,4,5,6,9}? Would you please provide proof or reasoning? $\endgroup$
    – Mzn
    Jan 17, 2015 at 8:19
  • 1
    $\begingroup$ 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 $ $\endgroup$
    – Joffan
    Jan 17, 2015 at 8:24
  • $\begingroup$ I see. Proof by induction. Thanks $\endgroup$
    – Mzn
    Jan 17, 2015 at 11:55
  • $\begingroup$ 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$ :-) $\endgroup$
    – Joffan
    Jan 17, 2015 at 17:37
  • $\begingroup$ Do you know of any introductory source on this topic? en.wikipedia.org/wiki/Quadratic_residue seems advanced to me :) $\endgroup$
    – Mzn
    Jan 17, 2015 at 19:06
1
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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