0

The question is to prove that if $a,b\in\mathbb{Z}$, $\ a\mid b$, and $a+b$ is odd, then $a$ is odd.

I started by considering a direct proof. $$\text{Assume }\ a+b\text{ is odd. Then }a+b=2k+1,\text{ where } k\in\mathbb{Z}.$$ I've considered using the fact that the sum of an even and an odd integer is odd, and the given fact that $a\mid b$, but I've encountered a mental block. Any guidance towards the right direction would be wonderful.

Bernard
  • 175,478
Robert Schwartz
  • 41
  • Looks OK so far. Now $a|b$ means that $b$ can be written as $na$ for some integer $n$. –  Jul 08 '19 at 05:57
  • Can you show the contrapositive: assuming $a|b$, if $a$ is even then $a+b$ is even? – J. W. Tanner Jul 08 '19 at 05:58
  • Since $a+b$ is odd, you know that one of $a$ and $b$ must be odd and the other even (you can check what happens when both are odd and both are even if you're unsure). So: now suppose $a$ is even. Since $a | b$ what does that tell you about $b$? – postmortes Jul 08 '19 at 05:58
  • 1
    @postmortes thank you, I think I know where to go from here – Robert Schwartz Jul 08 '19 at 05:59

6 Answers6

1

To give an odd sum, the parity must be opposite. So one is odd and the other is even. If $a$ were even it cannot divide odd $b$ (because $b=ka$ would imply even $b$). So $a$ is odd.

Deepak
  • 26,801
1

Assume $a|b$. If $a$ is even, then $b$ must be even, so $a+b$ must be even.

Therefore also the contrapositive: if $a+b$ is odd, then $a$ is odd.

J. W. Tanner
  • 60,406
1

$a|b$ so $a|a+b$, which is odd, so $a$ must be odd.

Amit Rajaraman
  • 3,248
0

Assume $a$ is even;

Since $a+b$ is odd, $b$ is odd.

Then $a \not |$ b$, a contradiction.

Peter Szilas
  • 20,344
  • 2
  • 17
  • 28
0

Continuing your line of thought.

$$a+b=2k+1-\text{odd} \\ a\mid b\Rightarrow b=am, \ \text{so:}\\ a+am=2k+1 \Rightarrow a=\frac{2k+1}{m+1} -\text{odd, because the numerator is odd}.$$

farruhota
  • 31,482
0

Since $a + b$ is odd, then exactly one of $a$, $b$ is odd.

Furthermore, since $a|b$, then $a$ cannot be even (for an even integer cannot divide an odd).

Therefore, $a$ must be odd.

DDS
  • 3,199
  • 1
  • 8
  • 31