What is the smallest number under 16,000 that
when divided by 127 leaves a remainder of 14,
and when divided by 131 leaves a ramainder of 66.
\(\begin{array}{|rcll|} \hline n \equiv {\color{red}14} \pmod {{\color{green}127}} \\ n \equiv {\color{red}66} \pmod {{\color{green}131}} \\ m=127\cdot 131=16637 \\ \hline \end{array} \)
Because 127 and 131 are relatively prim ( gcd(127,131) = 1! ) we can go on:
\(\begin{array}{rcll} n &=& {\color{red}14} \cdot {\color{green}131} \cdot [ \frac{1}{\color{green}131}\pmod {{\color{green}127}} ] + {\color{red}66} \cdot {\color{green}127} \cdot [ \frac{1}{\color{green}127}\pmod {{\color{green}131}} ] + {\color{green}127}\cdot {\color{green}131} \cdot k \quad & | \quad k\in Z\\ \end{array} \)
\(\begin{array}{rcll} && [ \frac{1}{\color{green}131}\pmod {{\color{green}127}} ] \quad &| \quad \text { modular inverse } 131\cdot \frac{1}{131} \equiv 1 \pmod {127} \\ &=& {\color{green}131}^{\varphi({\color{green}127})-1} \pmod {{\color{green}127}} \quad & | \quad \text{ Euler's totient function } \varphi(n) \quad \varphi(p) = p-1 \\ &=& 131^{126-1} \mod {127} \\ &=& 131^{125} \mod {127} \\ &=& 32 \\\\ && [ \frac{1}{\color{green}127}\pmod {{\color{green}131}} ] \quad &| \quad \text { modular inverse } 127\cdot \frac{1}{127} \equiv 1 \pmod {131} \\ &=& {\color{green}127}^{\varphi({\color{green}131})-1} \pmod {{\color{green}131}} \quad & | \quad \text{ Euler's totient function } \varphi(n)\quad \varphi(p) = p-1 \\ &=& 127^{130-1} \mod {131} \\ &=& 127^{129} \mod {131} \\ &=& 98 \\ \end{array}\)
\(\begin{array}{|rcll|} \hline n &=& {\color{red}14} \cdot {\color{green}131} \cdot 32 + {\color{red}66} \cdot {\color{green}127} \cdot 98 + {\color{green}127}\cdot {\color{green}131} \cdot k \\ n &=& 58688 + 821436 + 16637 \cdot k \\ n &=& 880124 + 16637 \cdot k \quad & | \quad k\in Z \\ \hline \end{array} \)
\(\begin{array}{|rcll|} \hline n_{min} &=& 880124 \pmod {16637 } \\ n_{min} &=& 15000 \\\\ n &=& 15000 + 16637 \cdot k \quad & | \quad k\in Z \\ \hline \end{array} \)
\(\begin{array}{|lrcll|} \hline k=0: & \mathbf{n} &\mathbf{=}& \mathbf{15000} \\ \hline \end{array} \)
The smallest number is 15000