# Proof of a divisibility rule

I'm trying to find a proof for the following result.

Consider a sum $a+b=c$. If $p$ divides $c$ then either

a) both $a$ and $b$ are divisible by $p$
b) both $a$ and $b$ are not divisible by $p$

Another case that seems to be a occurrence of the same rule (?) is

two things that are congruent modulo $c$ are either both divisible by $c$ or both not

I wasn't able to find any proof nor a lemma that would incorporate this rule.

-

I will prove that if $a$ is divisible by $p$, then so is $b$. Together with the converse (if $b$ is divisible by $p$, so is $a$), this will imply that either a) or b) holds. To get from this proof to the converse, just reverse the roles of $a$ and $b$.

Suppose $a$ is divisible by $p$. Write $a=px$ and $c=py$.

$px+b=py$, so $b=py-px=p(y-x)$, hence $b$ is divisible by $p$.

As for "two things that are congruent modulo $c$ are either both divisible by $c$ or both not:" Being divisible module $c$ is the same as having no remainder when divided by $c$. ie. $a$ is divisible by $c$ if and only if $a\equiv 0 \mod c$. If $a\equiv b$, then either $a\equiv b \equiv 0$ or $a\equiv b \not\equiv 0$

-

Hint $\:$ It's a modular form of: the points $\rm (x,y)$ on the line $\rm\: y = -x\:$ satisfy $\rm\: x=0\!\iff\! y=0.\:$

Namely, mod $\rm\:p,\:$ your equation is nothing but the line $\rm\:b\equiv -a,\:$ therefore $\rm\: a\equiv 0\!\iff\!b\equiv 0.$

Alternatively, if you don't know modular arithmetic, then you can proceed as follows.

Suppose $\rm\ p\ |\ a+b.\:$ Then $\rm\ p\ |\ b\ \Rightarrow \ p\ |\ a = (a+b)-b.\:$ Symmetrically $\rm\ p\ |\ a\ \Rightarrow\ p\ |\ b.$

Notice that the essence of the matter is simply that $\rm\: -0\:\equiv\: 0.$

-
I'm sorry, I don't see how the first premise is true. PS. It's not homework; a full answer instead of a hint would be far more appreciated. –  Milosz Wielondek Apr 19 '12 at 21:07
If $\rm\ p\ |\ a + b\$ then $\rm\ mod\ p\!:\ a+b\equiv 0\ \Rightarrow\ a\equiv -b\quad$ –  Bill Dubuque Apr 19 '12 at 21:12
Thanks for clearing it up! –  Milosz Wielondek Apr 19 '12 at 21:13