Thursday, 24 October 2013

abstract algebra - Reverse CRT to compute modulus



Very commonly we have a system as the one below, and if we know a and b, then we can easily use CRT to solve for c.



\begin{align} x &\equiv a \pmod p \\ x &\equiv b \pmod q \\ x &\equiv c \pmod{pq} \\ % &gcd(p, q) = 1 \end{align}



However, suppose we instead know a and c, but not b.




What is the arithmetic way to solve this without directly doing reduction mod q?
Is this possible to compute using just +,\ -,\ *, mod pq and mod p?




Clarification: I am interested in finding b in addition to x.


Answer



If you know c then you have
x=c+kpq
for some k\in\mathbb{Z} hence we also have
x\equiv c\mod{p}
x\equiv c\mod{q}
by taking the modulus of p or q on both sides of the above equality.


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