# Where is the Contradiction? Elementary Number Theory Proof : No natural numbers x, y such that $x^2 - y^2 = 2s$ where s odd integer.

Let $m$ be a positive integer of the form $m = 2s$, where $s$ is an odd integer. Prove that there do not exist positive integers $x$ and $y$ such that $x^2 - y^2 = m.$

Proclaimed Solution via Proof by Contradiction: Assume, to the contrary, that there exist positive integers $x$ and $y$ such that $(x - y)(x + y)= m = 2s \quad \text{ where$s$is an odd integer.} \tag{*}$ We consider two cases, according to whether $x$ and $y$ are of the same parity or of opposite parity. $\boxed{\text{Case 1:}}$ If $x$ and $y$ are of the same parity, then both $x - y$ and $x + y$ are even.
$\boxed{\text{Case 2:}}$ If $x$ and $y$ are of opposite parity, then both $x - y$ and $x + y$ are odd. Produce a contradiction in each case.

$\Large{1.}$ The product of two even numbers is always even. Thus, $(x - y)(x + y)$ is even. Then $(*)$ becomes: $\text{even = 2(odd)}$. Where is the contradiction?

The analogous solution works for Case 2? The product of two odds is always odd. Then $(*)$ becomes: $\text{odd = ($2s$= even)}$. Contradiction.

$\Large{2.}$ What is the motivation behind considering "whether $x$ and $y$ are of the same parity or of opposite parity"?

Source: Exercise 5.22, P124 of Mathematical Proofs, 2nd ed. by Chartrand et al

-

1. Suppose that $x+y$ and $x-y$ are both even; then there are integers $k$ and $\ell$ such that $x+y=2k$ and $x-y=2\ell$. But then $2s= (x+y)(x-y)=4k\ell=2(2k\ell)$, so $m=2k\ell$, and $s$ is therefore even, contradicting the hypothesis that $s$ is odd.

2. The two cases need to be considered separately, because each requires a different argument. Are you also asking how you might realize that if confronted with the problem? That’s largely a matter experience and partly a matter of recognizing that when the hypotheses specifically involve parity ($m$ is odd), parity may play a rôle in the proof.

-
$m$ is meant to be even - I believe you mean that $2s = 4 kl \implies s = 2kl$, contradicting that $s$ is odd. – user61527 Sep 6 '13 at 5:58
@T.Bongers: Yep; I mentally interchanged $m$ and $s$. Thanks. – Brian M. Scott Sep 6 '13 at 6:01
@BrianM.Scott: Many thanks. Yes, I was asking how I would foreknow/prevision the master step here of "whether $x$ and $y$ are of the same parity or of opposite parity"? Is T. Bongers's explanation (For which I upvoted) analogous to yours? Or are there other ways? – LePressentiment Sep 6 '13 at 8:53
@LePressentiment: T. Bonger’s explanation goes a little deeper than mine. Mine was intended to explain why you might think about parity in the first place; his actually deals more with how you might see the contradiction that arises if $x+y$ and $x-y$ have opposite parity. I can’t offhand think of another really likely way to approach the problem. – Brian M. Scott Sep 6 '13 at 8:57
@BrianM.Scott: Thank you again for your help. I would've liked to choose both answers. I have voted for yours for now because I didn't see anything in the question that involved divisiblity of 4 and so I wouldn't have reckoned divisibility by 4 which underlies T. Bonger's answer. – LePressentiment Sep 6 '13 at 9:07

Regarding case 1: If $x - y$ and $x + y$ are both even, then $(x - y)(x + y)$ is divisible by $4$, and so $s$ cannot be odd.

As far as motivation, the technique is somewhat suggested by considering that the right hand side is divisible by $2$ exactly once - so the left side must be divisible by $2$ exactly once, so $x - y$ and $x + y$ must have opposite parity.

-
Thank you very much. I value your answer to my Q2 the most. Sadly, only one best answer is allowed, so I've upvoted at the moment. I hope that you will not mind my choice. Would you be able to explicate how and why one would divine/suspect that it is the divisibility by 4 which begets the contradiction? Only because I still don't apprehend this do I feel Prof Scott's solution is more natural. If this could please be unriddled and Prof Scott does not mind, I'll be happy to change the Accepted Answer. – LePressentiment Sep 6 '13 at 9:21

For the first case, the contradiction lies in the fact that both $\left(x-y\right)$ and $\left(x+y\right)$ are even. This means that \begin{eqnarray*} \left(x-y\right)\left(x+y\right) & = & \left(2x\right)\left(2y\right)\\ & = & 4xy. \end{eqnarray*} If a number is $2s=2\left(2k+1\right)=4k+2$, then it is not a multiple of four. That's the contradiction.

-
You've used $x$ and $y$ twice to mean two different things in your first set of equations. – user61527 Sep 6 '13 at 5:57

1) The contradiction is that $(x-y)(x+y)$ is divisible by $4$, but $2$(odd) is not.

2) The motivation is that it exhausts all possibilities. If x and y are not of the same parity, we have the contradiction that $(x+y)(x-y)$ is odd, but $2s$ isn't.

-