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