Question 34 Pre Write

34. a. Statement: Let $m_1, m_2, \cdots, m_r$ be a collection of pairwise relatively prime integers, and let $a_1, \cdots, a_r$ be integers. Then the system of congruences $x \equiv a_i (mod m_i)$ for $1 ≤ i ≤ r$, has a unique solution modulo $M = m _1· m _2· \cdots ·m_r$, which is given by $x \equiv a_{1}M_{1}y_{1}+ a_{2}M_{2}y_{2}+ \cdots + a_{r}M_{r}y_{r}(mod M)$, where $M_i= M/m_i$ and $y_i \equiv (M_i )^{-1}(mod m_i)$ for $1 ≤ i ≤ r$.
Proof: Notice that $GCD(M_i , m_i ) = 1$ for $1 ≤ i ≤ r$. Therefore, $y_i$ exists by the Euclidean Algorithm. As $M_iy_i \equiv 1(mod m_i)$, $a_iM_iy_i \equiv a_i(mod m_i)$ for $1 ≤ i ≤ r$. If $a_iM_iy_i \equiv 0(mod m_j)$ then $j \neq i$ as $m_j | M_i$. Thus, $x \equiv a_i(mod m_i)$ for $1 ≤ i ≤ r$.
b Statement: Find the smallest possible x that satisfies $x \equiv 3mod17, x \equiv 10mod16, x \equiv 4mod11, x \equiv 0mod7$.
Proof:
$x \equiv 3mod17$ and $x \equiv 0mod7$:
$3+17k = 0+7l$
$17k-7l = -3$
As 17 and 7 are relatively prime, we can use that fact that $GCD(17,7)=1$.
$17\widetilde{k}+7\widetilde{l}=1$
$17 = 2 · 7 +3$
$7 = 2 · 3 +1$
$1 = 7-2 · 3= 7-2(17-2 · 7) = 5 · 7 - (2 · 17)$
$l =(3)\widetilde{l} = 3 · 5 = 16$
$x=0+15 · 7 =105$
$x \equiv 105mod119$
$x \equiv 10mod16$ and $x \equiv 4mod11$:
$10+16k = 4+11l$
$16k-11l = -6$
As 16 and 11 are relatively prime, we can use that fact that $GCD(16,11)=1$.
$16\widetilde{k}+11\widetilde{l}=1$
$16 = 1 · 11 + 5$
$11 = 2 · 5 +1$
$1 = 11-2 · 5= 11-2(16-1 · 11) = -2 · 16 +3 · 11$
$k =-(6)\widetilde{k} = -6 · -2 = 12$
$x=4+18 · 11 =202$
$x \equiv 202mod176$
$x \equiv 26mod176$
$x \equiv 26mod176$ and $x \equiv 105mod119$:
$26+176k = 105+119l$
$176k-119l = 79$
As 176 and 119 are relatively prime, we can use that fact that $GCD(176,119)=1$.
$176\widetilde{k}+119\widetilde{l}=1$
$176 = 1 · 119 + 57$
$119 = 2 · 57 + 5$
$57 = 11 · 5 + 2$
$5 = 2 · 2 + 1$
$1 = 5-2 · 2= 5-2· (119-2 · 57) = 5-2· (57-11·(119-2·(176-1·119)))$
$x \equiv 2842mod20944$
The minimum number of coins the bandits could have started with is 2842.