simultaneous linear congruences question

Question

I am trying to solve a problem of the following form

Ax≡B(mod C) A'x≡B'(mod C') A''x≡B''(mod C'') where A, B C are just integers. I know how to solve these problems when there is no coef on X, by changing them into linear Diophantine equations, but its not apparent to me how to go about this type of problem. Is there a way to simply the congruences to get rid of the coef, or do i need to look for a new method to solve this. Thanks

Answer 1

It comes down to the standard congruences.Explicitly, let $D=\gcd(A,C)$, $A_1=\dfrac AD$, $C_1=\dfrac CD$.

Obviously, the congruence $AX\equiv B \mod C$ implies $B\equiv 0\mod D$. So we have two cases:

• If $D\not\mid B$, the congruence has no solution.
• If $D\mid B$, let $B_1=\dfrac BD$. The initial congruence is equivalent to $$A_1x\equiv B_1\mod C_1,$$ and now, $\gcd(A_1,C_1)=1$, so $A_1$ is a unit mod. $C_1$. The inverse of $A_1$ is the coefficient of $A_1$ in a Bézout's relation $$U_1A_1+V_1C_1=1,$$ and the solution is obtained multiplying both sides of the congruence by $U_1$: $$x\equiv U_1B_1\mod C_1.$$ A value for $U_1$ is found with the Extended Euclidean algorithm.