4
$\begingroup$

I'm trying to get the least x from a system of congruences by applying the Chinese Remainder Theorem. Keep running into issues.

System of congruences: $$ x \equiv 0 (_{mod} 7) \\ x \equiv 5 (_{mod} 6) \\ x \equiv 4 (_{mod} 5) \\ x \equiv 3 (_{mod} 4) \\ x \equiv 2 (_{mod} 3) \\ x \equiv 1 (_{mod} 2) $$

I made the moduli relatively prime by removing 2nd and 6th congruence:

$1(_{mod} 2)$ is just a special case of $3 (_{mod} 4)$

and the 6th congruence because

$5 (_{mod} 6)$ splits into $2 (_{mod} 3)$ and $1 (_{mod} 2)$, both of which are already represented in the system.

Product of moduli $m = 7 . 5 . 4 . 3 = 420$

Each respective $M_n$ $$ M_1 = 420/7 = 60 \\ M_2 = 420/5 = 84 \\ M_3 = 420/4 = 105 \\ M_3 = 420/3 = 140 \\ $$

Each respective modular inverse $y_n$ $$ y_1 = 0 \\ y_2 = 4 \\ y_3 = 3 \\ y_4 = 2 \\ $$

Trying to find solutions via CRT, I get

$x \equiv a_1 M_1 . y_1 + a_2 M_2 . y_2 + a_3 M_3 . y_3 + a_4 M_4 . y_4$

Plugging in the values:

$$ x \equiv 0 + 4 . 84 . 4 + 3 . 105 . 3 + 2 . 140 . 2 = 2849 \\ \equiv 329 (mod 42) $$

And the "least" value being #329$ .

However, 329 doesn't satisfy the equation $329 (_{mod} 4) \equiv 3$.

What / where am I messing up?

$\endgroup$
2
  • $\begingroup$ The usual notation is $x\equiv0\pmod 7$ etc. Does "$329({}_{mod}4)\equiv 3$" mean $329\equiv3\pmod 4$? Anyway, in your original system, you have both $x\equiv5\pmod 6$ and $x\equiv3\pmod3$ which are incompatible. $\endgroup$ Jan 23, 2018 at 6:49
  • $\begingroup$ Yes. I meant $320 \equiv 3 (mod 4)$ $\endgroup$
    – MNav
    Jan 23, 2018 at 14:46

4 Answers 4

4
$\begingroup$

$$ x+1 \equiv 1 (_{mod} 7) \\ x+1 \equiv 0 (_{mod} 6) \\ x+1 \equiv 0 (_{mod} 5) \\ x+1 \equiv 0 (_{mod} 4) \\ x+1 \equiv 0 (_{mod} 3) \\ x+1 \equiv 0 (_{mod} 2) $$ Hense $$ x+1 \equiv 1 (_{mod} 7) \\ x+1 \equiv 0 (_{mod} 60) $$ Then from 60, 120, 180, 240, 300 and 360 you can find $120 \equiv 1 (_{mod} 7)$ so $x=119+420k, k\in Z$ is a solution of system.

$\endgroup$
3
$\begingroup$

The first condition tells you that $x=7y$, so the system becomes \begin{align} 7y&\equiv 5\pmod{6} && (\textit{redundant})\\ 7y&\equiv 4\pmod{5}\\ 7y&\equiv 3\pmod{4}\\ 7y&\equiv 2\pmod{3}\\ 7y&\equiv 1\pmod{2} && (\textit{redundant}) \end{align}

There is no modular inverse of $0$. On the other hand, $7$ has a modular inverse modulo $k$, for $2\le k<7$.

I left the redundant equations just for completeness.

The three relations become then \begin{align} y&\equiv2\pmod{5}\\ y&\equiv1\pmod{3}\\ y&\equiv1\pmod{2} \end{align} that yields $y\equiv17\pmod{30}$.

$\endgroup$
3
  • $\begingroup$ I'm not sure I follow why we'd need a modular inverse of 7. The system of equations above leads me to $7y \equiv 47 (mod 60)$, buy again I get stuck. Sorry if it's overly obvious but I'm not getting it. $\endgroup$
    – MNav
    Jan 23, 2018 at 15:52
  • $\begingroup$ @MNav You are mentioning $y_1=0$ as a modular inverse, which it can't be. By the way, I get $y\equiv 17\pmod{30}$. Note that $17\cdot 7=119$, which is the same as in the other answers. $\endgroup$
    – egreg
    Jan 23, 2018 at 16:15
  • $\begingroup$ Aha! What the relationships become really helped. Thanks! $\endgroup$
    – MNav
    Jan 23, 2018 at 18:28
1
$\begingroup$

This is very similar to aid78's solution. \begin{align} x &\equiv 0 \pmod 7 \\ x &\equiv 5 \pmod 6 \\ x &\equiv 4 \pmod 5 \\ x &\equiv 3 \pmod 4 \\ x &\equiv 2 \pmod 3 \\ x &\equiv 1 \pmod 2 \end{align}

can be rewritten as

\begin{align} x &\equiv \phantom{-}0 \pmod 7 \\ x &\equiv -1 \pmod 6 \\ x &\equiv -1 \pmod 5 \\ x &\equiv -1 \pmod 4 \\ x &\equiv -1 \pmod 3 \\ x &\equiv -1 \pmod 2 \end{align}

Since $\operatorname{lcm}(2,3,4,5,6)=60$, then the last five congruences are equivalent to $x \equiv -1 \pmod{60}$ So now you have to solve

\begin{align} x &\equiv \phantom{-}0 \pmod 7 \\ x &\equiv -1 \pmod{60} \end{align}

$x \equiv -1 \pmod{60}$ is equivalent to saying $x = 60n -1$ for some integer $n$.

This is one way to finish the problem.

\begin{align} x &\equiv 0 \pmod{7} \\ 60n - 1 &\equiv 0 \pmod{7} &\text{(Note $60\equiv 4 \pmod 7$)} \\ 4n &\equiv 1 \pmod 7 \\ 8n &\equiv 2 \pmod 7 \\ n &\equiv 2 \pmod 7 \\ n &= 7m + 2 \\ x &= 60n - 1 \\ x &= 60(7m + 2) - 1 \\ x &= 420m + 119 \\ x &\equiv 119 \pmod{420} \end{align}

$\endgroup$
0
$\begingroup$

I know this is bad method, but the number you want must be multiple of 7, it should be odd number, last digit must end in 9(why?!!) quickly you will find that smallest such number is 119.

$\endgroup$
2
  • $\begingroup$ I really like this method (an excellent one for checking answers for sure)! Unfortunately I'm in a discrete math course and the final answer isn't as important as the methodology applied. $\endgroup$
    – MNav
    Jan 23, 2018 at 15:18
  • 1
    $\begingroup$ I understand. It's just to get the answer quickly and verify. And a must have trick in your toolbox $\endgroup$
    – jnyan
    Jan 23, 2018 at 15:51

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.