1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user29418 Jun 25 '18 at 21:27
  • 5
    $\begingroup$ $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). $\endgroup$ – lulu Jun 25 '18 at 21:27
  • $\begingroup$ 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? $\endgroup$ – lulu Jun 25 '18 at 21:58
  • $\begingroup$ @lulu yes! i mistyped. It's supposed to be the difference of two squares. $\endgroup$ – Mister_J Jun 25 '18 at 21:59
  • $\begingroup$ 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. $\endgroup$ – lulu Jun 25 '18 at 22:00
0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mister_J Jun 25 '18 at 22:36
  • $\begingroup$ @Mister_J It's not arbitrary: it is $x-b$ and is obviously a natural number. $\endgroup$ – egreg Jun 25 '18 at 22:38
  • $\begingroup$ @egreg How is it obvious? $\endgroup$ – Graham Kemp Jun 25 '18 at 23:40
  • $\begingroup$ 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$. $\endgroup$ – fleablood Jun 26 '18 at 0:08
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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