Get $n_1,n_2,...,n_r$ positive integers such that $\gcd(n_i,n_j)=1$ always that $i\neq j$ and get $a,b$ two arbitrary integers..

Show that $$a\equiv b \pmod{n_1n_2...n_r}$$ if and only if $$a \equiv b \pmod{n_i}$$ for all $i = 1, 2,. . . , r$

  • 1
    $\begingroup$ Welcome to the site! So you are aware, this is not a homework site. People here don't like to respond to questions that show no effort. What have you tried? Can you, for example show one of the two implications? (that is, can you prove either "if" or "only if"? $\endgroup$
    – lulu
    Oct 13 '16 at 14:23
  • $\begingroup$ yes,, <- this implication $\endgroup$
    – Andrew New
    Oct 13 '16 at 14:26
  • $\begingroup$ @AndrewNew Oh, but $\to$ is even more trvial ... $\endgroup$ Oct 13 '16 at 14:26
  • $\begingroup$ I agree with @HagenvonEitzen...$\Rightarrow$ is a lot easier. Can you edit your post to show your argument for $\Leftarrow$? $\endgroup$
    – lulu
    Oct 13 '16 at 14:29
  • $\begingroup$ @lulu I feel like this is the most friendly way to welcome newcomers! almost spit in their faces. $\endgroup$ Oct 13 '16 at 14:35

if $a\equiv b \mod n_1\dots n_r$, then $a=b+k\cdot n_1\dots n_r$, and so $a\equiv b\mod n_i,\quad\forall i$.

If $a\equiv b\mod n_i,\quad\forall i$, then $a=b+k_1n_1=\dots=k_rn_r$. However as $\gcd(n_i,n_j)=1$ for $i\ne j$, each $k_i$ must be divisible by all the other $n_j$, and so $a\equiv b \mod n_1\dots n_r$.

  • $\begingroup$ I'll ping you here, since I have no other way to reach you. I have noticed a flurry of tag edits from you recently. Some of them are useful, but a significant number of them are not, and I have seen myself forced to reject them. What's happening, how come you've got fixated on tags? It looks like you are after the "Research Assistent" badge; now imagine - what if we all began editing the same tag descriptions in order to get this badge? It would be total chaos, no edit would live more than a few days, being superseded by another one... $\endgroup$
    – Alex M.
    Oct 15 '16 at 12:27

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.