1
$\begingroup$

$$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!

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

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)$.

$\endgroup$
1
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.