# Q: Proving Existence

I'm currently stuck on a problem right now for my Intro to Proofs Class. The problem says:

Let $a,b ∈ ℕ$. Prove that if $a+b$ is even, then there exists nonnegative integers $x$ and $y$ such that $x^2-y^2= ab$.

So far I've tried it directly, and by contrapositive and came to a similar road block.

Direct:
Assume $a,b ∈ ℕ$, and that $a+b$ is even.
$a+b$ being even $\implies$ $a+b=k_1$, such that $k_1 ∈ \mathbb{Z}$.
$a+b=k_1$ $\implies$ $a=k_1-b$.
Multiplying both sides of $a$ by $b$ we get: $ab= b(k_1-b)=bk_1-b^2$.
observing the conclusion $x^2-y^2=(x+y)(x-y)=ab$

It's at this point I'm at a road block. I'm not sure if direct is the way to go. I've also tried contrapositive, and contradiction, but i've also hit a roadblock for both of those as well.

• you need to use the definition of even: a + b is even, therefore a and b are both either even or odd. a = 2k, b = 2m and a=2k+1, b=2m+1. – user29418 Jun 25 '18 at 21:27
• $3+7$ is even but $21$ is not the sum of two squares. (similarly $15=3\times 5$ is not the sum of two squares). – lulu Jun 25 '18 at 21:27
• Alternative theory: perhaps you mistyped and you were asked to prove that $ab$ could be written as the difference of two squares instead of the sum? – lulu Jun 25 '18 at 21:58
• @lulu yes! i mistyped. It's supposed to be the difference of two squares. – Mister_J Jun 25 '18 at 21:59
• Ah, ok. Please edit your post to reflect that. For that problem, Hint: suppose that $a≥b$ and try to solve $x+y=a, x-y=b$ in integers. – lulu Jun 25 '18 at 22:00

If $a+b$ is even, you can write $a+b=2x$, with $x$ a natural number. Then, assuming $a\ge b$, which is not restrictive, you have $$a-b=a+b-2b=2x-2b=2(x-b)$$ so also $a-b$ is even; set $x-b=y$, so that $$a+b=2x \qquad a-b=2y$$ Summing these up we obtain $2a=2x+2y$, hence $a=x+y$.

Can you finish?

• Thank you @egreg! I just have a question on the part where we let x-b=y. Are we saying that y is an arbitrary natural number since we're trying to prove that there exist nonnegative integers x and y? – Mister_J Jun 25 '18 at 22:36
• @Mister_J It's not arbitrary: it is $x-b$ and is obviously a natural number. – egreg Jun 25 '18 at 22:38
• @egreg How is it obvious? – Graham Kemp Jun 25 '18 at 23:40
• It's "obvious" because $2x = a+ b \ge b+b = 2b$ so $x \ge b$ and as $a+b$ is even $x = \frac {a+b}2$ is an integer. So $x - b \ge b-b =0$. It's only not natural if $a = b = x$ and $x - b = 0$. – fleablood Jun 26 '18 at 0:08

If $a+b=2k$ for some $k\in\mathbb{Z}_{>0}$, then $a$ and $b$ are both either even or both odd. Say both even with $a=2m$, $b=2n$, for some $m$, $n\in\mathbb{Z}_{\ge0}$. Then we require $$x^2-y^2=(x-y)(x+y)= ab=4mn$$ If we let $2m=x-y$ and $2n=x+y$, then solving this gives $x=m+n$ and $y=n-m$.

Say both odd with $a=2r+1$, $b=2s+1$, for some $r$, $s\in\mathbb{Z}_{\ge0}$. Then we require $$x^2-y^2=(x-y)(x+y)= ab=(2r+1)(2s+1)=2(2rs+(r+s))+1$$ If we let $2r+1=x-y$ and $2s+1=x+y$, then solving this gives $x=r+s+1$ and $y=s-r$.

Well, brainstorm first.

$x^2 - y^2 = ab$

$(x - y)(x + y) = ab$. Can I say $x - y = a$ and $x+y = b$? Why or why not? Well, first off $x - y$ would have to equal the smaller of $a$ or $b$ and $x + y$ would have to be the larger. But we can assume without loss of generality that $a \le b$. So can we say that $x, y$ exist where $x-y = a$ or $x + y = b$?

That would mean $x$ is the midpoint of $a, b$ or that $x = \frac {a + b}2$. And that $y =$ the distance from the midpoint to either of the extreme $a$ or $b$ $= |\frac {a+b}2 - a| =|b - \frac {a+b}2|=|\frac {b-a}2|$.

And that is possible because $a+b$ is even!

So:

Pf: Let $x = \frac {a+b}2; y =|\frac {b-a}2|=$

Then ... (well, let's just push the throttle down and see what happens... we know it must work so ... let's go with it....)

then $x^2 - y^2 = (\frac {a+b}2)^2 - (\frac {b-a}2)^2 =$

$\frac {a^2 + 2ab + b^2}4 - (\frac {b^2 -2ab + a^2}4)=$

$\frac {4ab}4 = ab$.

======

Note: we did get lucky. There are probably other answers where $x-y \ne \min (a,b)$ and $x+y \ne \max (a,b)$ but those worked.

===

Alternatively... once we see that $x-y$ and $x + y$ can be extreme points of a segment we can say: Let $m = x+y$ and $d= x-y$. Now $d= m -2y$ so $m$ and $d$ are both even or both odd.

So we can solve for $m,d$ and set $x = \frac {m+d}2$ and $y = \frac {m-d}2$.

$x^2 - y^2 = md = ab$. So $m,d$ can be any complimentary factors of $ab$ BUT with the only stipulation that $m \ge d$ and that $m$ and $d$ are both the same parity.

As $a + b$ is even $a$ and $b$ are the same parity two such factors will always exists.

(We can always chose $m = \max (a,b)$ and $d = \min (a,b)$ if we want. But if we want another solution and if $a$ nor $b$ are primes. We can choose any complimentary factors provided they are both even or both odd.)