Saturday, June 8, 2019

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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...