0
$\begingroup$

I have the following system

$ x \equiv 2 (mod 4)$

$ x \equiv 2 (mod 6) $

$ x \equiv 2 (mod 7) $

And I can't apply the Chinese remainder Theorem.

I tried applying the Chinese remainder Theorem to the last 2 congruences, which gave me that the set of solutions of that 2 congruences is $ 2 + 42 \cdot \beta $ with $\beta$ belonging to $\Bbb Z$.

Then I solved the set of solutions of the first congruence, which is $ 6 + 4 \cdot \alpha $ with $\alpha$ belonging to $\Bbb Z$.

A common solution would be the one that satisfies $ 2 + 42 \cdot \beta = 6 + 4 \cdot \alpha$, equivalently, the one that satisfies $ 42 \cdot \beta + 4 \cdot \alpha = 4$, and this (because of Bezout Identity) have solution only if $mcd(42,4)=4$ which is not true. So this would mean this system have no solution, which is incorrect (I think).

Then, what can I do?

$\endgroup$
6
  • 1
    $\begingroup$ $x=2$ is a solution (so solutions exist). $\endgroup$ – lulu Sep 5 '17 at 17:08
  • $\begingroup$ In general, the first two should be resolved $\pmod {12}$. They are compatible (as it happens) and you can easily deduce that $x\equiv 2 \pmod {12}$ Once you have that, the problem is straight forward. In principle, though you could have had a conflict between the first two. $\endgroup$ – lulu Sep 5 '17 at 17:11
  • $\begingroup$ @lulu Could you explain me why does the solutions of the first two congruences can be achieved just by combining them into the same congruence $(mod 12)$ ? $\endgroup$ – puradrogasincortar Sep 5 '17 at 17:20
  • $\begingroup$ $x\equiv 2 \pmod 6$ is the same as the pair $x \equiv 0 \pmod 2$ and $x\equiv 2 \pmod 3$. Now the first congruence is redundant here (as we already know $x\equiv 2 \pmod 4$. Thus I really just have to solve $x\equiv 2 \pmod 4$ and $x\equiv 2 \pmod 3$. That's a standard CRT problem. $\endgroup$ – lulu Sep 5 '17 at 17:25
  • 1
    $\begingroup$ Just to be clear, you could have had a conflict. If, say, I replace your second line with $x\equiv 1 \pmod 6$ then the first line would say $x$ was even but the second would say it was odd, so there would be no solutions. $\endgroup$ – lulu Sep 5 '17 at 17:26
2
$\begingroup$

First of all you have that the solution of the first relations are given by $4\alpha + 2$. Then this will give you the relation:

$$2 + 4\alpha = 2 + 42\beta \iff 42 \beta = 4 \alpha \iff 21 \beta = 2 \alpha$$

And certainly this one have solution. In fact the Bezout Lemma says that $xa + by = m$ has a solution iff $\operatorname{gcd}(x,y) \mid m$. It doesn't have to be equal.

$\endgroup$
2
  • $\begingroup$ The congruences come from this exercise: A mother have 3 daughters of 20, 22 and 23 years old. They want to leave home when the mother achieves an age such that the remainder of the age divided by each of the daughters years when the little one was 4 is 2. The questions are: -At what age do the daughters leave? -What's the mother age in that moment? By using what you say, how the solution of the system can give me the answers? $\endgroup$ – puradrogasincortar Sep 5 '17 at 17:31
  • 1
    $\begingroup$ Find the smallest solution for either $\alpha$ or $\beta$. That should be 21 or 2, respectively. Then plug in the general form of the solution to get that the mother's age should be 86 $\endgroup$ – Stefan4024 Sep 5 '17 at 18:25
2
$\begingroup$

In a system of congruences $x\equiv a_i\pmod {n_i}$, the Chinese theorem applies when all $n_i$ are relatively prime.

When this is not the case, there is an additional condition to know if there are solutions, which is :

$\forall (i,j)\mid a_i\equiv a_j\pmod{\gcd(n_i,n_j)}$

In that case, the solutions are to be computed modulo the LCM of all $n_i$.

Here since all $a_i$ are equal the criterion is trivially met and $2$ is a trivial solution

$x\equiv 2\pmod{\operatorname{lcm}(4,6,7)}\equiv 2\pmod {84}$


In general to solve such system you have to find $n'_i$ such that $\begin{cases} n'_i\mid n_i\\ \operatorname{lcm}\limits_{i=1..N}(n'_i)=\operatorname{lcm}\limits_{i=1..N}(n_i)\\ \gcd(n'_i,n'_j)=1\end{cases}$

Here we have $n_1=4,n_2=6,n_3=7$ whose LCM is $84$.

The equivalent system while be $n'_1=4,n'_2=3,n'_3=7$ with the same LCM.

The remainders are then recomputed with these new $n'_i\quad:\ x\equiv a_i\pmod{n'_i}$

$\begin{cases} x\equiv 2\pmod{4}\\ x\equiv 2\pmod{6}\\ x\equiv 2\pmod{7} \end{cases} \implies \begin{cases} x\equiv 2\pmod{4}\\ x\equiv 2\pmod{3}\\ x\equiv 2\pmod{7} \end{cases}$

Now we can apply Chinese theorem and $x\equiv 2\pmod{84}$ as previously.

$\endgroup$
4
  • $\begingroup$ $2 \pmod{4}$ would imply $2 \pmod{84}$ $\endgroup$ – user1329514 Sep 5 '17 at 17:41
  • $\begingroup$ 6 is not 2 mod 84. $\endgroup$ – zwim Sep 5 '17 at 17:44
  • $\begingroup$ $LCM(4,6,7) = 2^2 * 3 * 7 = 84$ ... $ \{ 2 \pmod {42} \} \cap \{ 2 \pmod{4} \} = \{ 2 \pmod{84} \} $ $\endgroup$ – user1329514 Sep 5 '17 at 23:59
  • $\begingroup$ lol, silly me, I didn't even noticed my lcm was wrong. corrected. $\endgroup$ – zwim Sep 6 '17 at 0:03
1
$\begingroup$

Hint $\,\ 4,6,7\mid x\!-\!2\iff {\rm lcm}(4,6,7)\mid x\!-\!2$

For more see here on CCRT = Constant case optimization of CRT = Chinese Remainder Theorem.

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