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?

| cite | improve this question | |
$\endgroup$
  • $\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$ – Angina Seng Jan 23 '18 at 6:49
  • $\begingroup$ Yes. I meant $320 \equiv 3 (mod 4)$ $\endgroup$ – MNav Jan 23 '18 at 14:46
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}$.

| cite | improve this answer | |
$\endgroup$
  • $\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 '18 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 '18 at 16:15
  • $\begingroup$ Aha! What the relationships become really helped. Thanks! $\endgroup$ – MNav Jan 23 '18 at 18:28
3
$\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.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\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 '18 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 '18 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.