Similar Congruences

1. Similar Congruences

Consider solutions to the simultaneous congruences:

\begin{array}{r} (1) & x \equiv a_{1} \mod n^{p} \\ (2) & x \equiv a_{2} \mod n^{q} \end{array}

with $p >= q$ . Now from (1):

\begin{aligned} x - a_{1} = λ n^{p} & For some λ \in Z . \\ \Rightarrow x \equiv a_{1} \mod n^{q} & using n^{q} | n^{p} \\ \Rightarrow a_{1} \equiv a_{2} \mod n^{q} \end{aligned}

Hence $a_{1} = a_{2} \mod n^{q}$ is a necessary condition for solutions to exist. Suppose this is true, ie:

\begin{array}{r} (3) & x \equiv a_{1} \mod n^{p} \\ (4) & x \equiv a_{1} \mod n^{q} \end{array}

Then the set of solutions to (3) are a subset of the set of solutions to (4), hence we need only consider $x \equiv a_{1} \mod n^{p}$ .