Q: Proving Existence

Question

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.

Answer 1

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?

Answer 2

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$.

Answer 3

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.)