Thursday, November 12, 2015

modular arithmetic - Solving simultaneous congruences



Trying to figure out how to solve linear congruence by following through the sample solution to the following problem:





$x \equiv 3$ (mod $7$)
$x \equiv 2$ (mod $5$)
$x \equiv 1$
(mod $3$)




Let:
$n_1$ = 7
$n_2 = 5$
$n_3 = 3$



$N = n_1 \cdot n_2 \cdot n_3 = 105$



$m_1 = \frac{N}{n_1} = 15$

$m_2 = \frac{N}{n_2} = 21$

$m_3 = \frac{N}{n_3} = 35$




$gcd(m_1,n_1)$ = $gcd(15,7) = 1 = 15 \times 1 - 7 \times 2$ so $y_1 = 1$ and $x_1 = 15$
$gcd(m_2,n_2)$ = $gcd(21,5) = 1 = 21 \times 1 - 5 \times 4$ so $y_2 = 1$ and $x_2 = 21$
$gcd(m_3,n_3)$ = $gcd(35,3) = 1 = -35 \times 1 + 3 \times 12$ so $y_3 = -1$ and $x_3 = -35$



I understand up to this point, but the next line I don't get:



So $x = 15 \times 3 + 21 \times 2 - 35 \times 1 \equiv 52$ (mod $105$)



Where is the $\times 3$, $\times 2$, $\times 1$ from? Is it just because there are 3 terms, so it starts from 3 then 2 then 1? And where is the 52 coming from?


Answer



Although Bill Cook's answer is completely, 100% correct (and based on the proof of the Chinese Remainder Theorem), one can also work with the congruences successively; we know from the CRT that a solution exists.




Starting from $x\equiv 3\pmod{7}$, this means that $x$ is of the form $x=7k+3$ for some integer $k$. Substituting into the second congruence, we get
$$7k+3 \equiv 2\pmod{5}.$$
Since $7\equiv 2\pmod{5}$, and $3\equiv -2\pmod{5}$, this is equivalent to $2k-2\equiv 2\pmod{5}$. Dividing through by $2$ (which we can do since $\gcd(2,5)=1$) we get $k-1\equiv 1\pmod{5}$, or $k\equiv 2\pmod{5}$. That is, $k$ is of the form $k=5r+2$ for some integer $r$.



Plugging this into $x=7k+3$ we have $x=7(5r+2)+3 = 35r + 17$.



Then plugging this into the third (and last) congruence, we get
$$35r + 17\equiv 1\pmod{3}.$$
Now, $35\equiv -1\pmod{3}$, $17\equiv -1\pmod{3}$, so this is the same as $-r-1\equiv 1\pmod{3}$, or $r\equiv -2\equiv 1\pmod{3}$. That is, $r$ is of the form $3t+1$. Plugging that into $x$ we get

$$x = 35r+17 = 35(3t+1)+17 = 105t + 52,$$
so that means that $x$ is of the form $x=52+105t$ for some integer $t$; that is, $x\equiv 52\pmod{105}$ is the unique solution modulo $3\times5\times 7$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...