Modulo a composite number same as modulo individual factors?

529 Views Asked by At

Can somebody please give me a hint why the following holds (or doesn't it?):

if $r^2 \equiv a \mod n$ and $n = p * q$,

then $r^2 \equiv a \mod p$

and $r^2 \equiv a \mod q$.

I tried it with different examples, it seems to hold but I don't have an idea why. Also, if it holds, does a rule exist for it? The name of the rule would be enough, so I can do further research on it.

Example: $r = 23$, $p = 7$, $q = 11$, then:

$23^2 \equiv -10 \mod 77$

$23^2 \equiv 1 \mod 11 \equiv -10 \mod 11$

$23^2 \equiv 4 \mod 7 \equiv -10 \mod 7$

1

There are 1 best solutions below

0
On

If $r^2 = kn + a$ for some $k\in\Bbb Z$, then $$r^2 = \left(kq\right)p+a = \left(kp\right)q + a$$