Linear equations modulo different prime through CRT

87 Views Asked by At

Given prime $p$ and equations $$a_1x+b_1y+c_1z=d_1\bmod p \\ a_2x+b_2y+c_2z=d_2\bmod p \\ a_3x+b_3y+c_3z=d_3\bmod p$$

where $a_i,b_i,c_i,d_i\in\Bbb Z_p$, we can solve for $x,y,z\in\Bbb Z_p$.

Now suppose given primes $p_1,p_2,p_3$ and equations $$a_1x+b_1y+c_1z=d_1\bmod p_1\\ a_2x+b_2y+c_2z=d_2\bmod p_2\\ a_3x+b_3y+c_3z=d_3\bmod p_3$$

where $a_i,b_i,c_i,d_i\in\Bbb Z_{p_i}$, can we solve for $x,y,z\in\Bbb Z$ such that each $a_ix+b_iy+c_iz=d_i\bmod p_i$ is satisfied by $x\bmod p_i,y\bmod p_i$ and $z\bmod p_i$?

Assume $p_1p_2,p_2p_3,p_3p_1<x,y,z<p_1p_2p_3$


I do not follow Gerry Myerson's comments completely. Could someone elucidate further?