b'_\pi,\quad c_\pi,\quad d_\pi$$ as the multiplicities of $\pi$ in the prime factorizations of $p$, $p'$, $q$, $q'$, $r$, $n$, respectively. We first prove this technical result.

\[=&gt;&lt;-lem\] Assume that $${\mathrm{GCD}}(p,n) = {\mathrm{GCD}}(p',n)
  \qquad\text{and}\qquad
  {\mathrm{GCD}}(q,n) = {\mathrm{GCD}}(q',n).$$ Then there exists an integer $x$ such that for all primes $\pi$ dividing $rn$, the following three-part condition holds: $$\begin{cases} \begin{aligned}
\textrm{ If $a_{\pi}=a'_{\pi}$ then }\qquad&  x\equiv 0 &&\modu \pi^{a_{\pi}+1})\\
\textrm{ If $a_{\pi}>a'_{\pi}$ then }\qquad&x\equiv\pi^{a'_{\pi}-d_{\pi}}&&\modu \pi^{a'_{\pi}-d_{\pi}+1}) \\
\textrm{ If $a_{\pi}<a'_{\pi}$ then }\qquad&\tfrac{rn}{pq}x+\tfrac{r}{q}\equiv \pi^{c_{\pi}-b'_{\pi}}&&\modu \pi^{c_{\pi}-b'_{\pi}+1}).
\end{aligned}
\end{cases}$$

By the Chinese remainder theorem it suffices to verify that for each prime $\pi$ dividing $rn$, there exists $x \in {\mathbb{Z}}$ satisfying the relevant congruence. If $a_\pi = a_\pi'$ then such an integer $x$ clearly exists. If $a_\pi > a'_\pi$ then ${\mathrm{GCD}}(p,n) = {\mathrm{GCD}}(p',n)$ implies $d_\pi \leq a_\pi'$, so the second congruence is well-defined, and it too clearly has a solution.

If $a_\pi < a_\pi'$ then $pq=p'q'$ implies $b_\pi' < b_\pi$ and ${\mathrm{GCD}}(p,n) = {\mathrm{GCD}}(p',n)$ implies $d_\pi \leq a_\pi$ and the fact that $q'$ divides $r$ implies $b_\pi' \leq c_\pi$. Thus the corresponding congruence is at least well-defined. To show that it has a solution, it is enough to check that ${\mathrm{GCD}}(\pi^{c_{\pi}-b'_{\pi}+1},\frac{rn}{pq})$ divides $\pi^{c_{\pi}-b'_{\pi}}-\frac{r}{q}$. This is equivalent to 