I am a number less than 3000.
If you divide me by 32 you will get a remainder 30.
If you divide me by 54 , you will get a remainder 44.
What number am I?
I am 638 or 1502 or 2366
\(\begin{array}{rcll} n \equiv {\color{red}30} \pmod {{\color{green}32}} \\ n \equiv {\color{red}44} \pmod {{\color{green}54}} \\\\ \text{or }\quad \begin{array}{rcll} n-30 = 32 r \\ n-44 = 54 s \\ \end{array} \end{array}\)
Because 32r or 54s is even
so n-30 or n-44 is even so n is even
We can set: \(m = \frac{n}{2}\) and m is an integer.
\(\begin{array}{|rcll|} \hline n-30 = 32 r \quad & | \quad :2 \\ \frac{n}{2}-15 = 16 r \\ m-15 = 16 r \\\\ n-44 = 54 s \quad & | \quad :2 \\ \frac{n}{2}-22 = 27 s \\ m-22 = 27 s \\\\ && \text{or }\quad \begin{array}{rcll} m \equiv {\color{red}15} \pmod {{\color{green}16}} \\ m \equiv {\color{red}22} \pmod {{\color{green}27}} \\ \end{array} \\ && \quad \text{ with } n=2m \text{ and } 16\cdot 27 = 432 \\ \hline \end{array} \)
Because 16 and 27 are relatively prim ( gcd(16,27) = 1! ) we can go on:
\(\begin{array}{rcll} m &=& {\color{red}15} \cdot {\color{green}27} \cdot [ \frac{1}{\color{green}27}\pmod {{\color{green}16}} ] + {\color{red}22} \cdot {\color{green}16} \cdot [ \frac{1}{\color{green}16}\pmod {{\color{green}27}} ] \\ \end{array}\)
\(\begin{array}{rcll} && [ \frac{1}{\color{green}27}\pmod {{\color{green}16}} ] \\ &=& {\color{green}27}^{\varphi({\color{green}16})-1} \pmod {{\color{green}16}} \\ &=& 27^{8-1} \mod {16} \\ &=& 27^{7} \mod {16} \\ &=& 3 \\\\ && [ \frac{1}{\color{green}16}\pmod {{\color{green}27}} ] \\ &=& {\color{green}16}^{\varphi({\color{green}27})-1} \pmod {{\color{green}27}} \\ &=& 16^{18-1} \mod {27} \\ &=& 16^{17} \mod {27} \\ &=& 22 \\ \end{array}\)
\(\begin{array}{rcll} m &=& {\color{red}15} \cdot {\color{green}27} \cdot 3 + {\color{red}22} \cdot {\color{green}16} \cdot 22 \\ m &=& 8959 + k\cdot 432 \quad & | \quad k \in Z \\\\ n &=& 2m \\ n &=& 2\cdot(8959 + k\cdot 432 ) \\ n &=& 17918 + k\cdot 864 \\\\ n_{min} &=& 17918 \pmod {864 } \\ n_{min} &=& 638 \\ \mathbf{n} &\mathbf{=}& \mathbf{638 + k\cdot 864} \quad & | \quad k \in Z \\ \end{array} \)
\(\begin{array}{|lrcll|} \hline k=0: & \mathbf{n} &\mathbf{=}& \mathbf{638} \\ k=1: & n &=& 638+1\cdot 864 \\ & \mathbf{n} &\mathbf{=}& \mathbf{1502} \\ k=2: & n &=& 638+2\cdot 864 \\ & \mathbf{n} &\mathbf{=}& \mathbf{2366} \\ \hline \end{array}\)