3
$\begingroup$

Let $p_1$ and $p_2$ are prime numbers, $a,b <p_1p_2$. I need to find $ab \pmod{p_1p_2}$. But for some reason I cant find $ab$, it will be too large number. How can I find it without calculating $ab$? Maybe a formula using modulus by $p_1$ and $p_2$.

$\endgroup$
2
$\begingroup$

If you can find $c$ and $d$ so $ab \equiv c \mod p_1$ and $ab \equiv d \mod p_2$, you want to find $e$ so $e \equiv c \mod p_1$ and $e \equiv d \mod p_2$. In fact, you can take $e = c + q p_1$ where $q \equiv (d-c) p_1^{-1} \mod p_2$.

$\endgroup$
5
$\begingroup$

Try the Chinese remainder theorem. That is, assuming $p_1\neq p_2$, the problem $$ x \equiv ab \pmod{p_1p_2} $$ Can be solved by breaking it up into the system of equations $$ x\equiv [ab]_{p_1} \pmod{p_1}\\ x\equiv [ab]_{p_2} \pmod{p_2} $$ Where $[ab]_{p_i}$ is the modulus of $ab$ by $p_i$. We find the solution to the first equation to be $$ x \equiv [ab]_{p_1}p_2[p_2^{-1}]_{p_1} + [ab]_{p_2}p_1[p_1^{-1}]_{p_2} \pmod{p_1p_2} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.