# Does this system of congruences have a solution even if they are not relatively prime at first?

$$x \equiv 4\ (\textrm{mod}\ 15) \ \ \ \ \land\ \ \ \ \ x\ \equiv 6\ (\textrm{mod}\ 33)$$

Does this system of congruences have a solution even if they are not relatively prime at first?

If I try to break the congruences into smaller ones, for instance:

$$x \equiv 4\ (\textrm{mod}\ 15) \rightarrow \ \ \ \ x \equiv 4\ (\textrm{mod}\ 5) \ \ \ \ \ \ \ \land \ \ \ \ x \equiv 1\ (\textrm{mod}\ 3)$$

$$x \equiv 6\ (\textrm{mod}\ 33) \rightarrow \ \ \ \ x \equiv 6\ (\textrm{mod}\ 11) \ \ \ \ \land \ \ \ \ x \equiv 0\ (\textrm{mod}\ 3)$$

I can see that they are still not relatively primes as there is a $gcd(3,3) \neq 1$

But i'm not sure if my reasoning is correct or if there is another way around for the system of congruences to have a solution.

Thanks!

• So, we need $x\equiv1\pmod 3$ and $x\equiv0\pmod 3$ together . Is it plausible? – lab bhattacharjee Jun 21 '13 at 14:37

Suppose $x$ is a solution of your system, then you'd get: $15k+4=33m+6$ for suitable $m,k \in \mathbb{Z}$, but this means that $15k-33m=2$:impossible mod3. A system of the form $x\equiv a$ (mod w) $\wedge \ x \equiv b$ (mod k) has a solution iff $gcd(w,k)| (b-a)$.
It is not difficult to see that if a system \begin{cases} x \equiv a \pmod{m}\\ x \equiv b \pmod{n} \end{cases} has a solution $x$, then $a \equiv b \pmod{\gcd(m, n)}$. The converse also holds, and requires Euclid's algorithm.