0
$\begingroup$

Is it possible to apply Chinese Remainder Theorem to the follow system of congruences?
$$\begin{align}x&\equiv1\mod 15\\ x&\equiv2\mod 21\\ x&\equiv3 \mod 35\end{align}$$ $15, 21$ aren't coprime
$21$ and $35$ aren't coprime
Is CRT applicable to this problem?

$\endgroup$
1
$\begingroup$

The system doesn't have a solution, You can apply CRT to $x \equiv 1 \bmod 15$ to get $x \equiv 1 \bmod 3$ and $x \equiv 1 \bmod 5$, and since $5$ and $21$ are coprime, you can combine $x \equiv 1 \bmod 5$ and $x \equiv 2 \bmod 21$ to get $x \equiv 86 \bmod 105$, which is incompatible with $x \equiv 3 \bmod 35$.

$\endgroup$
  • 1
    $\begingroup$ Isnt it simpler ? $3$ divides $15$ and $21$ so $1\equiv 2(\mod 3)$. $\endgroup$ – Rene Schipperus May 7 '18 at 1:18
  • $\begingroup$ Is there a quick way to see if a system does not have a solution? Do I just check to see if the modulus are coprime or not? $\endgroup$ – Juan May 7 '18 at 1:18
  • $\begingroup$ @ReneSchipperus that is a faster method, you're right $\endgroup$ – Connor Harris May 7 '18 at 1:18
  • $\begingroup$ @Juan systems with non-coprime moduli can have solutions, but they don't have to. For example, $x \equiv 2 \bmod 4, x \equiv 4 \bmod 6$ has a solution, but not (say) $x \equiv 2 \bmod 4, x \equiv 3 \bmod 6$. The simple method is to apply CRT to break every congruence into a system of congruences modulo powers of primes, and then check whether the resulting system is inconsistent. $\endgroup$ – Connor Harris May 7 '18 at 1:20
  • $\begingroup$ What exactly do you mean by inconsistent? $\endgroup$ – Juan May 7 '18 at 1:22
1
$\begingroup$

$$x \equiv 1 \pmod{15} \iff \begin{array}{c} x \equiv 1 \pmod 3 \\ x \equiv 1 \pmod 5 \end{array} $$

$$x \equiv 2 \pmod{21} \iff \begin{array}{c} x \equiv 2 \pmod 3 \\ x \equiv 2 \pmod 7 \end{array} $$

$$x \equiv 3 \pmod{35} \iff \begin{array}{c} x \equiv 3 \pmod 5 \\ x \equiv 3 \pmod 7 \end{array} $$

Note that there are contradictions with the values of $x \pmod 3, x \pmod 5, \ \text{and} \ x \pmod 7$.

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