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$
$\begingroup$
$\endgroup$
5
-
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$– luluCommented Oct 13, 2016 at 14:23
-
$\begingroup$ yes,, <- this implication $\endgroup$– Andrew NewCommented Oct 13, 2016 at 14:26
-
$\begingroup$ @AndrewNew Oh, but $\to$ is even more trvial ... $\endgroup$– Hagen von EitzenCommented Oct 13, 2016 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$– luluCommented Oct 13, 2016 at 14:29
-
$\begingroup$ @lulu I feel like this is the most friendly way to welcome newcomers! almost spit in their faces. $\endgroup$– Skeleton BowCommented Oct 13, 2016 at 14:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.Commented Oct 15, 2016 at 12:27