Thursday, 9 April 2015

modular arithmetic - How to compute apmodm1 given that aequivcpmodm2?



Given m1,m2 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}...