0
$\begingroup$

As $910= 7 \times 10 \times 13,$ I was able to come up with the following system of congruences: $$2x\equiv 1\mod(7)$$ $$9x\equiv 1\mod(10)$$ $$11x\equiv 1\mod(13)$$ However, I am unsure as to how I should proceed with using the Chinese Remainder Theorem.

$\endgroup$
2
$\begingroup$

Observe that $2x \equiv 1\ (\text {mod}\ 7)$ is equivalent to $x \equiv 4\ (\text {mod}\ 7).$ Similarly $9x \equiv 1\ (\text {mod}\ 10)$ is equivalent to $x \equiv 9\ (\text {mod}\ 10)$ and $11x \equiv 1\ (\text {mod}\ 13)$ is equivalent to $x \equiv 6\ (\text {mod}\ 13).$ So you just need to solve the following system of congruences

$$x\equiv 4\ (\text {mod}\ 7)$$ $$x\equiv 9\ (\text {mod}\ 10)$$ $$x\equiv 6\ (\text {mod}\ 13)$$

Which is easy to solve using Chinese remainder theorem.

Let $N_1 = 10 \times 13 =130, N_2 =7 \times 13 =91$ and $N_3=7 \times 10= 70.$ Then $N_i$ and $n_i$ are relatively prime to each other for $i=1,2,3.$ So by Bezout's theorem $\exists$ integers $M_i$ and $m_i$ such that $$M_iN_i+m_in_i = 1$$ for $i=1,2,3,$ where $n_1=7,n_2=10,n_3=13.$ Now try to find $M_i$'s then the required solution is $\sum\limits_{i=1}^{3} a_iM_i N_i\ (\text {mod}\ N),$ where $N=7 \times 10 \times 13 = 910$ and $a_1=4,a_2=9,a_3=6.$

EDIT $:$ Here $M_1 = 2,M_2=1,M_3=-5.$ So the required solution of the above system of congruences is $$4 \times 2 \times 130 + 9 \times 1 \times 91 + 6 \times (-5) \times 70 = -241 \equiv 669 \ (\text {mod}\ 910).$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

You need to apply the extended Euclidean algorithm anyway to apply the CRT, so why not do it right away for a direct computation of $219^{-1} \pmod {910}$?

So $$ \begin{array}{rrr|r} 910 & 1 & 0 & - \\ 219 & 0 & 1 & 4 \\ 34 & 1 & -4 & 6 \\ 15 & -6 & 25 & 2 \\ 4 & 13 & -54 & 3 \\ 3 & -45 & 187 & 1 \\ 1 & 58 & -241 & &\\ \end{array} $$

where the final line tells us that

$$1 = 58\cdot 910+ (-241)\cdot 219$$

so that the inverse of $219$ becomes $-241\equiv 669 \pmod{910}$

pro: it's a lot faster; con: no practice with CRT.

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