2
$\begingroup$

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.

2 Answers 2

1

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$

2

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

  • 0
    Thanks for clearing it up!2012-04-19