Finding X for Mod? If I have this:


*

*$x \pmod p = 1$

*$x \pmod q = 0$
Is there any way I can find a possible natural number for $x$ that satisfies both equations. I know it has something to do with the Chinese Reminder Theorem; however, I have been unable to solve it.

$x\equiv 0\pmod{\!q}\!\iff\! q\mid x\!\iff\! x = qn,\ $ so $\bmod p\!:\ qn = x\equiv 1\!\iff\!\!\!\!\!\!\!\!\!\overbrace{ n\equiv q^{-1}}^{\large{\rm exists} \iff (q,p)=1}$
If so $\, x \equiv q(q^{-1}\bmod p)\, \pmod{\! pq}.\,$  Inverses van be computed via Extended Euclidean algorithm
It's a special case of CRT = Chinese Remainder Theorem (but we don't need that generality here)
