What is wrong with my proof here?

Question

Prove that if $\forall a,b,c \in \Bbb Z$, if $a|b$ and $a \nmid c$ then $a \nmid (b+c)$.

My proof was:

Let's look at 2 cases: 1) Assume $a|b$ is true and a is even. That means for $k\in \Bbb Z$, $2k|b$ which means b has to be even. And for $2k \nmid c$, that means c has to be odd. So $a \nmid (2k+2k+1)$ -> $a\nmid (4k+1)$ -> $2k \nmid 2(2k)+1$. That means even + odd = odd, and even|odd. So true when a is even.

2) When a is odd, assume a|b and $a \nmid c$ is true. Let $k \in \Bbb Z$. $2k+1|b$ and $2k+1 \nmid c$. Now let $m \in \Bbb Z$. $m(2k+1) = b$ and $m(2k+1) \neq c$. That means $m(2k+1) \neq m(2k+1)$ which doesn't make sense so that means the hypothesis is false, and F -> T = T.

Since all cases are true, statement is true QED.

I got a 0/3 on this question, and I'm not sure why, the part in case 1 where I said "$2k \nmid c$, that means c has to be odd." was underlined but that's all the feedback I got.

Answer 1

HINT

As noticed $2k\nmid c \not \Rightarrow c$ is odd.

To prove the result, let us use proof by contradiction

$$a|(b+c)\implies b+c=ka.$$

Answer 2

Another proof uses the division algorithm with an addition:

For any positive integers $u$ and $v$, there are non-negative integers $p$ and $q$ such that $u = pv+q$ where $0 \le q \le v-1$; in addition $v | u$ if and only if $q = 0$.

To use this to solve your problem:

$a | b \implies b = ka$; $a \not\mid c \implies c = ja+i$ with $1 \le i \le a-1$.

Therefore $b+c = ka+ja+i =(k+j)a+i$ which means that $a \not\mid b+c$.

Answer 3

"Let's look at 2 cases: 1) Assume a|b is true and a is even. That means for k∈Z, 2k|b"

Actually that means that for some $k$ we have $a=2k$ and $2k|b$. It certainly does not mean that for every $k$ that $2k|b$.

which means b has to be even. And for 2k∤c, that means c has to be odd.

So if $a=6$ and $b = 18$ and $c = 10$ then $6|18$ and $6\not \mid 10$ we can conclude that because $2*3\not \mid 10$ that $10$ is odd.

It's not just the $2$ that determines that $2k \not \mid c$. It is possible that it is the $k\not \mid c$. One or the other. Either $2\not \mid c$ or $k\not \mid c$. But we don't know which one.

Assuming $a$ is even didn't help us at all.

So a∤(2k+2k+1) -> a∤(4k+1) -> 2k∤2(2k)+1

You are assuming that because $b$ is odd that $b = 2k+1$. But $a = 2k$ for some $k$ and $b$ is odd that most certainly does not mean $b = 2k + 1$ for the same $k$. After all if $a = 8; a = 2k; k = 4$ then $a$ is even. And $b = 27$ is odd. But that certainly does not mean $b = 2*4 + 1 = 9$

Instead if you had concluded that $b$ is odd (which you can not conclude) you would have $a = 2k$ for some $k$ and $b = 2j + 1$ for some $j$ but you have no reason to think the $k$ and $j$ are the same numbers.

2) When a is odd, assume a|b and a∤c is true. Let k∈Z. 2k+1|b and 2k+1∤c.

Okay, but you should said let $a = 2k + 1$. The $k$ is a specific $k$. Not any $k$.

Now let m∈Z. m(2k+1)=b and m(2k+1)≠c. That means m(2k+1)≠m(2k+1)

What??? Why does it mean that? That means $b \ne c$, sure, and $m(2k+1) = b \ne c$ but as $c$ has nothing to do with $m(2k+1)$ you can not say that means $m(2k+1) = b \ne c = m(2k+1)$.

which doesn't make sense so that means the hypothesis is false, and F -> T = T.

The hypothesis being false would mean $a|b$ where $b$ is odd and $a\not \mid c$ is always false.

But clearly we can have $a|b$ where $b$ is odd. (Ex: $a= 3$ and $b = 15$). And clearly we can have $c$ where $a \not \mid c$ (Ex: $c = 7$; $3 \not \mid 7$).

So $3|15$ an $15$ is odd and $3\not \mid 7$ is ... TRUE!

So the hypothesis is certainly not false.

.....

1) can be fixed (although it shouldn't be) but 2) is simply a mess.

We can say if $a$ is even then there is a specific $k$ so that $a = 2k$ and that $2k|b$ and so $b$ is even.

$2k\not \mid c$ and so either $2 \not \mid c$ or $k \not \mid c$. If $2 \not \mid c$ then $c$ is odd and so $b + c$ is odd and even $a$ can't divide into odd $b + c$.

But if $k \not \mid c$ then what what do we have. We have $k|b$ but $k\not \mid c$ so can we say $k\not \mid b+ c$.

We would have to prove that ... but.. but that would be the exact same thing we were asked to prove in the beginning! (We just replace $a$ with $k$.) So assumeing $a$ was even did us no good at all and just wasted our time.

So we have to do this from the start.

We have $a|b$ so $b = k*a$ for some $k$. And we have $a\not \mid c$ so $c\ne j*a$ for any $j$. Well, we can't do any calculations on what things don't equal.

We have two options.

1) A proof by contradiction:

Assume $a|b+c$. that means there is some $j$ so that $b+c =a*j$. And $b = a*k$ so $a*k + c = a*j$.

Can you finish this by getting a contradiction? (Hint: the contradiction would be $a|c$.)

2) direct:

If $c \ne a*j$ for any $j$ then what does $c$ equal in terms of $a$?

By the division algorithem $c = j*a + r$ where $r$ is the remainder That is $0 \le r < a$. But because $a\not \mid c$ we know $r \ne 0$.

Co $b + c = (a*k) + (j*a +r) = ????$

Can you finish this to show that $a\not \mid b+c$? (Hint: what remainder do you get if you divide $b+c$ by $a$?)

Answer 4

Always use the definitions. What does $a|b$ mean? It means that $b=na$ for some $n\in \Bbb Z.$

So if $a|b$ and $a|(b+c)$ then there exist $n_1,n_2\in \Bbb Z$ with $b=n_1a$ and $ b+c=n_2a.$ These imply that $$c=(b+c)-b=n_2a-n_1a=(n_2-n_1)a.$$ But then $c=n_3 a$ where $n_3$ is the integer $n_2-n_1,$ so $a|c$ according to the definition of $a|c.$

So the assertion $[a|b \land a\not |c \land a|(b+c)]$ is false. So if the first 2/3 of this assertion, namely $[a|b\land a\not |c\,]$, is true, then the last 1/3, namely $a|(b+c),$ must be false.