1

I found the converse here, although that's not what I want.

I have thought of a proof by contradiction and by contraposition, although I can't seem to figure out a way to finish a direct proof.

$mn = 2a + 1 $

If $a = 2kj + (k+j)$ for integers $k$ and $j$, which I got out of my crystal ball, then $mn = 4kj + 2(k+j) + 1$ and $mn = (2k + 1)(2j + 1)$, but then I have to prove that it's possible to write any integer $a$ as $2kj + (k + j)$, which I don't know how.

Any help would be appreciated.

Community
  • 1
Artur Marzano
  • 11
  • I believe you are overthinking this problem. Try stating the contrapositive of the statement. Also, for future reference, please include the problem statement in the body of your Questions, not relying wholly on the title for this important information. – hardmath Apr 25 '16 at 03:22
  • 2
    Why must you have a direct proof? Proof by contraposition is far and away the easiest way to go. – Daniel W. Farlow Apr 25 '16 at 03:22
  • I don't think showing that $a=2kj+(k+j)$ will really help; you would then be saying that since $mn=(2k+1)(2j+1)$, then $m=2k+1$ and $n=2j+1$, which is not necessarily true. ... I'm not really sure that a direct proof is possible. – Christopher Carl Heckman Apr 25 '16 at 03:23
  • @DanielW.Farlow : This might be a homework assignment, where a direct proof must be done. – Christopher Carl Heckman Apr 25 '16 at 03:24
  • The proof by contraposition can easily be turned into a direct proof. Just divide $m$ by $2$ with remainder: $m = 2q + r$, where $r \in \left{0,1\right}$. Now distinguish between the cases $r=0$ (easy to derive a contradiction from) and $r=1$ (win). – darij grinberg Apr 25 '16 at 03:26
  • It was on a test I had a few weeks ago. I can't believe how easy the answer was. (!) – Artur Marzano Apr 25 '16 at 09:17

1 Answers1

5

Write $m=2k+a$, where $a=0$ or $1$.

Write $n=2l+b$, where $b=0$ or $1$.

$mn=(2k+a)(2l+b)=4kl+2kb+2al+ab$

Since $mn$ is odd, $ab=1$, which means $a=1$ and $b=1$.

yoyostein
  • 19,608