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