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.

$\endgroup$
1
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Milo Wielondek Apr 19 '12 at 21:07
  • $\begingroup$ If $\rm\ p\ |\ a + b\ $ then $\rm\ mod\ p\!:\ a+b\equiv 0\ \Rightarrow\ a\equiv -b\quad$ $\endgroup$ – Bill Dubuque Apr 19 '12 at 21:12
  • $\begingroup$ Thanks for clearing it up! $\endgroup$ – Milo Wielondek Apr 19 '12 at 21:13

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.