# What is the proof for: $a\mid b,a\mid c\implies a\mid b\pm c$

In my spare time, I'm working my way a book "mathematical introduction to cryptography" in which the following proposition is given:

If $a\mid b$ and $a\mid c$, then $a\mid (b+c)$ and $a\mid (b-c)$

It is left to the reader to show the proof, however, my maths skills have almost disappeared over the last 15 years since leaving uni.

-
Remember the definition: $a|b$ means that there exists some integer $x$ such that $ax=b$. Now apply this definition to $a|c$ too... – Henning Makholm Apr 11 '13 at 18:52
If you knew that $\mathbb{Z}_a$ is a group, that would be straightforward. Take a look at modular arithmetic, if you're interested. – 1015 Apr 11 '13 at 18:56
@vonbrand What is it exactly that you have against >? Just curious. – 1015 Apr 11 '13 at 18:57
@julien, the funny background? [I understand this is to be used for quotes, not my own text.] – vonbrand Apr 11 '13 at 18:59
@vonbrand: Sure looks to me like that line is a quote from the book the OP is reading. – Henning Makholm Apr 11 '13 at 19:03

If $c=ka$ and $b=ja$ then $b+c=\cdots \; ?$, $b-c=\cdots \; ?$

In words, if $a$ is a factor of $c$ and a factor of $b$, the distributive laws mean it is a factor of both $a+b$ and $a-b$.

Example $\;\; 6=\color{red}{2}\times 3, 12=\color{red}{2}\times 6$ so $6+12=\color{red}{2}\times(3+6)$ and $6-12=\color{red}{2}\times(3-6)$

-

Hint $\rm\,\ a\mid b,c\ \Rightarrow\ \dfrac{b}a,\,\dfrac{c}a\in\Bbb Z\ \Rightarrow\ \dfrac{b\pm c}{a}\, =\, \dfrac{b}a \pm \dfrac{c}a\in \Bbb Z\ \Rightarrow\ a\mid b\pm c$

Remark $\$ So we see that this divisibility law is a consequence of $\rm\,\Bbb Z\,$ being closed under addition and subtraction.

-

It would be obvious if you translated the problem into the language of modular arithmetic rather than that of divisibility.

Alternatively, it would be useful to introduce new variables: e.g. let $d$ be the* integer such that $b = ad$, and so forth. then work from there.

*: In the special case that $a = 0$, there isn't a unique choice for $d$. But we can treat this case specially. Or just let $d$ be any integer with that property.

-
In order for the language of modular arithmetic to be useful - that is, to say that since $b\equiv 0\bmod a$ and $c\equiv 0\bmod a$ we must have $b+c\equiv0+0\bmod a$ - we have to work at the machine-language level to show these sorts of deductions are justified in the first place. In other words, we'd have to prove $a\mid b,c\implies a\mid (b+c)$ to begin with. So I think the idea in the first sentence is putting the cart before the horse. – anon Apr 11 '13 at 19:03
@anon: Even if so, the derivation of the properties of modular arithmetic is only done once (if at all). Given that the OP is studying a specialized application rather than taking an elementary number theory course, he could very well be willing to accept whatever basic tools as given, and just needs to know how to apply them. And even if he is going through a "machine-language level" derivation now, it will be useful in the future for him to be aware that the question becomes trivial when in the form of modular arithmetic. – Hurkyl Apr 11 '13 at 19:29
@anon It need not be circular, e.g. the OP might already know the Congruence Addition Rule $\rm\ b\equiv \hat b,\ c\equiv \hat c\:\Rightarrow b\pm c\equiv \hat b \pm \hat c.\:$ The exercise follows from the special case $\rm\:\hat b \equiv 0\equiv \hat c.\:$ Of course the addition rule needs to be proved from scratch too (as does everything, eventually). To the downvoter: why? It seems a bit harsh. – Math Gems Apr 11 '13 at 23:05

If $a\mid b$ and $a\mid c$ then $a\mid b\pm c$

Show: $$a\mid b \Longrightarrow\exists k\in\mathbb{N}\;\text{such that}\;b=a\cdot k$$$$a\mid c \Longrightarrow\exists k'\in\mathbb{N}\;\text{such that}\;c=a\cdot k'$$$$b\pm c=a\cdot k\pm a\cdot k'=a(k\pm k')\Longrightarrow a\mid b\pm c\;\;\;\;\;\Box$$Remember that in case $b-c$; $b>c$

-