Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that if $a \in \mathbb{Z_{\geq 0}}$, then the following proposition holds:

$a \mid [b {\pmod{a}}+c \pmod {a}] \iff a \mid b+c$.

I've been trying to prove it, but I am blocked. I tried using definitions, but I reached non conclusive results. I know that it's easy, but I need help.

thank you

share|improve this question
    
The vertical bar and the $\equiv$ symbol are each verbs, so this sentence appears to have three verbs. Could you please clarify? –  vadim123 Apr 30 '13 at 3:06
    
I think it reads as follows: a divides [ b modulo a + c modulo a] is congruent to a divides b + c although i don't like the use of the parentheses in this so i may edit it. –  Ahmed Masud Apr 30 '13 at 3:15
    
That's how I read it too, @Ahmed, but I don't know how to parse a sentence with three verbs. –  vadim123 Apr 30 '13 at 3:18
    
More generally, suppose $\rm b\equiv \bar{b}$ and $\rm c\equiv\bar{c}$ mod $\rm a$ for any integers $\rm b,\bar{b},c,\bar{c}$ (in particular, I assume you want e.g. "$b\pmod a$" to mean specifically the least residue of $\rm b$ modulo $\rm a$, but this specificity is unnecessary). Then we have an arithmetic congruence $\rm b+c\equiv\bar{b}+\bar{c}\bmod a$. So in particular $\rm b+c\equiv 0\iff \bar{b}+\bar{c}\equiv 0$, another way of phrasing this is $\rm a\mid (b+c)\iff a\mid (\bar{b}+\bar{c})$. –  anon Apr 30 '13 at 3:34
    
I am assuming my interpretation of your question is correct, though. You should endeavor to be clearer in the future. For instance, if you are using $\equiv$ for logical equivalence, this is a bad choice since it is also used to mean "congruent to" in modular arithmetic. It took me more effort to figure out what you were asking than to think of how to answer it (this is a pet peeve of mine). –  anon Apr 30 '13 at 3:36
show 2 more comments

1 Answer

up vote 1 down vote accepted

We have $b\pmod{a}=b+ak$, for some $k\in\mathbb{Z}$. Similarly, $c\pmod a=c+aj$, for some $j\in\mathbb{Z}$. Because $a|a(k+j)$, we have $a|(b+c)$ if and only if $a|(b+c)+a(k+j)$, which rearranges to $a| [b\pmod{a} + c\pmod{a}]$.

share|improve this answer
add comment

Your Answer

 
discard

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.