0
$\begingroup$

In my class the exact test of the Chinese Remainder Theorem we learned stated \begin{align*} x &\equiv a_1 \pmod{n_1}\\ x &\equiv a_2 \pmod{n_2}\\ ...\\ x &\equiv a_L \pmod{n_L}. \end{align*} has a unique solution modulo the product $n_1n_2...n_L$ if all the $n$'s are pairwise relatively prime.

How does this help us solve the following question. Other sources say to use a product $M$ along with $M_1,M_2,...$ all of which are absent in the text of my CRT

Find the smallest positive integer $x$ so that \begin{align*} x &\equiv 3 \pmod{7}\\ x &\equiv 12 \pmod{11}\\ x &\equiv 5 \pmod{13}. \end{align*}

$\endgroup$
  • $\begingroup$ I find it best, usually, to go step by step. From the first, we write $x=3+7t$. Now, for the second, we want $3+7t\equiv 1 \pmod {11}$ or $4t\equiv 2 \pmod {11}$. Easy to solve that, which will tell us a class $\pmod {77}$ that passes the first two tests. Now do the third the same way. $\endgroup$ – lulu Mar 29 '17 at 0:09
1
$\begingroup$

$2\cdot 7 = 14 \equiv 1\pmod{13}\\ 3 + 2\cdot2\cdot 7 = 31\equiv 5\pmod{13}$

That gets us part way there.

Now we need to find an $n$, such that

$31+n\cdot 7\cdot 13 \equiv 12\equiv 1\pmod{11}\\ 31 \equiv 9\pmod {11}\\ 91 \equiv 3\pmod {11}\\ x=122$

$\endgroup$
  • $\begingroup$ @Dario just because I studied math doesn't mean I know how to do basic addition very well. $\endgroup$ – Doug M Mar 29 '17 at 0:28
0
$\begingroup$

Let's take it step by step:

A) $x \equiv 3 = a_7 \mod 7$ and $x \equiv 12 \equiv 1 = a_{11} \mod 11$ (um, is that a typo?)

1) Solve $7m_{3} + 11m_{11}$. You can eyeball this or use Euclid's Algorithm

$11 = 7 +4; 4 = 11 -7$

$7 = 4 + 3; 3 = 7 -4$

$4 = 3 + 1; 1= 4 -3$

$= 4 - (7-4) = 2*4-7$

$= 2*(11-7) - 7 = 2*11 - 3*7$

$m_{11} = 2; m_7 = -3$

2) I plug in the formula I have memorized $x \equiv a_7*11*m_{11} + a_{11}*7*m_7 \mod 7*11$. So $x = 3*11*2 - 1*7*3 = 45 \mod 77$ and $45 \equiv 1 \mod 11$ and $45 \equiv 3 \mod 7$.

This works because $a_7*11*m_{11} + a_{11}*7*m_7 \mod 7$

$\equiv a_7*11*m_{11} + a_7*7*m_7 + (a_{11} - a_7)*7*m_7 \mod 7$

$\equiv a_7(11*m_{11} + 7*m_7) \mod 7$

$\equiv a_7 \mod 7$. and

$a_7*11*m_{11} + a_{11}*7*m_7 \mod 11$

$\equiv a_{11}*11*m_{11} + a_{11}*7*m_7 + (a_{7} - a_{11})*11*m_{11} \mod 11$

$\equiv a_{11}(11*m_{11} + 7*m_7) \mod 11$

$\equiv a_{11} \mod 11$

B) $x \equiv 45 \mod 77$

$x \equiv 5\mod 13$

1) Solve $m_{77}77 + m_{13}13 = 1$.

$77 = 5*13 + 12;12 =77 - 5*13$

$13 = 12 + 1$ so

$1 = 13 - 12$

$= 13 - (77 - 5*13)$

$= 6*13 - 77$

2) $x = a_{77}m_{13}*13 + a_{13}m_{77}*77 = 45*6*13 - 5*77 = 3125 \mod 13*77\equiv 122 \mod 1001$ and the solution is $x =122$.

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