Reverse CRT to compute modulus

98 Views Asked by At

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

1

There are 1 best solutions below

5
On BEST 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.