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!

  • 3
    $\begingroup$ 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. $\endgroup$ – Arturo Magidin Jan 14 at 23:14
  • 2
    $\begingroup$ 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. $\endgroup$ – Dietrich Burde Jan 14 at 23:14
  • 2
    $\begingroup$ 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. $\endgroup$ – Mark Jan 14 at 23:16
  • $\begingroup$ 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. $\endgroup$ – greycatbird Jan 14 at 23:23

Your number theory proof is correct, but your proposed equivalence in propositioal logic is (in general) not correct, so you can't use it to proof what you want just with your initial knowledge and "propositional magic", you need actual number theory for that.

To see that the propositional formula is generally incorrect, set for example

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

Of course, I may have misunderstood what you wanted to achieve with your propositional formula. If that's true, please explain.

  • $\begingroup$ Thank you for the answer. I was intimidated by the simplicity of the proof. 'If it's too good to be true, it probably is.' I will remember to brush up on my propositional logic. $\endgroup$ – greycatbird Jan 14 at 23:27

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.