Thursday 9 April 2015

modular arithmetic - How to compute $a pmod{m_1}$ given that $a equiv c pmod{m_2}$?



Given $m_1, m_2$ and we know that
$$a \equiv c \pmod{m_1}$$
Is there a way to directly compute
$$a \pmod{m_2}$$



Answer



If $m_2$ divides $m_1$ we can. Otherwise we cannot. The reason is that unless $m_2$ divides $m_1$, there will be more than one number $x$ such that $0\le x\lt m_2$ and $x\equiv c\pmod{m_2}$.



Remark: In connection with your question, we should mention the Chinese Remainder Theorem. If $m_1$ and $m_2$ are relatively prime, then for any $d$ we like, there will be an $a$ such that $a\equiv c\pmod{m_1}$ and $x\equiv d\pmod{m_2}$. Thus in the relatively prime case, knowing $c$ gives absolutely no information about the remainder when $a$ is divided by $m_2$.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...