# Elementary Number Theory Divisibility Question

Let $$a, b, c \in \mathbb Z$$. I know that if $$c|a$$ and $$c|b$$, then $$c|a \pm b$$. I was working on some elementary number theory and I began to wonder if the following were true:$$\text{if }c|a \text{ and } c|a+b \text{, then } c|b$$

I managed a very simple proof:

Suppose $$c|a$$ and $$c|a+b$$. It follows that $$a=c \cdot d$$ and $$a+b=c \cdot d'$$, where $$d, d' \in \mathbb Z$$. Note that if $$a=c \cdot d$$, then $$c \cdot d +b=c \cdot d'$$. Hence $$b=c \cdot d' -c \cdot d$$, or $$b=c(d-d')$$. Letting $$d''=d-d' \in \mathbb Z$$, we have $$b=c \cdot d''$$, or $$c|b$$, as desired.

However, while trying to prove this the good ol' fashioned way (using propositional logic), I'm hitting a barrier that has me second-guessing if my above proof is correct or not. For the life of me, I cannot fathom how $$(P \land Q) \Rightarrow R \equiv (P \land R) \Rightarrow Q$$ for $$P:=c|a$$, $$Q:=c|b$$ and $$R:=c|a+b$$.

Sorry for the silly question. My propositional logic is a little rusty and I'm probably just overlooking something. Any insight would be greatly appreciated!

• You can't prove this from propositional logic alone, because the proof requires the semantics of what you are trying to prove (the meaning of the statements). This is not a tautology. The proposition $(P\wedge Q)\Rightarrow R$ is not equivalent to the proposition $(P\wedge R)\Rightarrow Q$. The former is true when $P$ and $R$ are true and $Q$ false, but the latter is false in that case. – Arturo Magidin Jan 14 at 23:14
• So the question is not about elementary number theory. Of course, $c\mid a$ and $c\mid a+b$ imply $c\mid b$. Your proof is correct. – Dietrich Burde Jan 14 at 23:14
• Your proof is correct, but it is really much better to avoid writing so many letters if possible. You could simply write $b=(a+b)-a$ and use the part which as you wrote in the beginning you already know. – Mark Jan 14 at 23:16
• Thank you guys for the response. The proof 'felt' correct, but it seemed strange to me that I've never come across that property before (simple although it may be). That's why I decided to delve deeper using propositional logic. – greycatbird Jan 14 at 23:23

$$P:=2|x, Q:=4|x, R=2|x$$