Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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$

share|cite|improve this answer

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.$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.