which whole numbers between 2 and 40 can be divided by 4 with a remainder of 2 and also be divided by 5 with a remainder of 1
which whole numbers between 2 and 40 can be divided by 4 with a remainder of 2
and also be divided by 5 with a remainder of 1
\(\begin{array}{rcll} n &\equiv& {\color{red}2} \pmod {{\color{green}4}} \\ n &\equiv& {\color{red}1} \pmod {{\color{green}5}} \\ \text{Let } m &=& 4\cdot 5 = 20 \\ \end{array} \)
Because 4 and 5 are relatively prim ( gcd(4,5) = 1 ) we can go on:
\(\begin{array}{rcll} x &=& {\color{red}2} \cdot {\color{green}5} \cdot [ \frac{1}{ {\color{green}5} } \pmod{{\color{green}4}} ] +{\color{red}1} \cdot {\color{green}4} \cdot [ \frac{1}{ {\color{green}4} } \pmod{{\color{green}5}} ] +4\cdot 5 \cdot n \quad & | \quad n \in Z \\\\ && [ \frac{1}{ {\color{green}5} } \pmod{{\color{green}4}} ] \\ &=& [ {\color{green}5}^{\varphi({\color{green}4})-1} \pmod {{\color{green}4}} ] \quad & | \quad \varphi({\color{green}4})=4\cdot(1-\frac12)=2 \\ &=& [ {\color{green}5}^{2-1} \pmod {{\color{green}4}} ] \\ &=& [ {\color{green}5}^{1} \pmod {{\color{green}4}} ] \\ &=& [ {\color{green}1} \pmod {{\color{green}4}} ] \\ &=& [ 1] \\\\ && [ \frac{1}{ {\color{green}4} } \pmod{{\color{green}5}} ] \\ &=& [ {\color{green}4}^{\varphi({\color{green}5})-1} \pmod {{\color{green}5}} ] \quad & | \quad \varphi({\color{green}5})=5\cdot(1-\frac15)=4 \\ &=& [ {\color{green}4}^{4-1} \pmod {{\color{green}5}} ] \\ &=& [ {\color{green}4}^{3} \pmod {{\color{green}5}} ] \\ &=& [ {\color{green}4} \pmod {{\color{green}5}} ] \\ &=& [ 4 ] \\\\ x &=& {\color{red}2} \cdot {\color{green}5} \cdot [ 1] + {\color{red}1} \cdot {\color{green}4} \cdot [4] +4\cdot 5 \cdot n \quad & | \quad n \in Z \\\\ x &=& 10+16+20\cdot n \\ x &=& 26 + 20\cdot n \quad & | \quad x_{\text{min}} = 26 \pmod {m} \\ && & | \quad = 26 \pmod {20} = 6 \pmod {20} \\ x &=& 6 + 20\cdot n \quad & | \quad n \in Z \\\\ x_1 &=& 6 + 20\cdot 0 \quad & | \quad n=0 \\ x_1 &=& 6\checkmark \quad & | \quad 2\le x\le40 \\\\ x_2 &=& 6 + 20\cdot 1 \quad & | \quad n=1 \\ x_2 &=& 26\checkmark \quad & | \quad 2\le x\le40 \\ \end{array}\)