Monday, 14 December 2015

elementary number theory - Modular arithmetic r = c (mod a), s = c (mod b), find (mod a)



Assume that a,bN and that a|b. Let r \equiv c \pmod a and s \equiv c \pmod b. What is s \pmod a?



So I know the following:
r \equiv c \mod a
s \equiv c\mod b



Which implies by rule a \equiv b \pmod m is the same as b \equiv a \pmod m,
c \equiv r \pmod a
c \equiv s \pmod b




Which implies that
r \pmod a = s \pmod b



However after that I do not know how to prove s \pmod a from here. Am I overlooking a modular arithmetic rule or should I solve it differently?


Answer



Well, this may help you. Since a|b and b|s-c we get a|s-c, i.e., s\equiv c \pmod a, but c\equiv r \pmod a. So by transitivity we deduce that s\equiv r\pmod a.


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}...