What is the smallest number that when divided by 31 leaves a remainder of 9, and when divided by 41 leaves a remainder of 39? Thanks for help.
LCM 31, 41 =31 x 41 =1,271
31r + 9 =41s + 39, solve for r, s
r=38, s=28
The smallest number n =
31 x 38 + 9 =1,187, and the general form of n=
1,271(LCM)*C + 1,187 =n. When C=0, 1, 2......etc., we have:
n=1,187
n=2,458
n=3,729........etc.
+26387 What is the smallest number that
when divided by 31 leaves a remainder of 9, and
when divided by 41 leaves a remainder of 39?
\(\begin{array}{|rcll|} \hline n \equiv {\color{red}9} \pmod {{\color{green}31}} \\ n \equiv {\color{red}39} \pmod {{\color{green}41}} \\ m=31\cdot 41=1271 \\ \hline \end{array} \)
Because 31 and 41 are relatively prim ( gcd(31,41) = 1! ) we can go on:
\(\begin{array}{rcll} n &=& {\color{red}9} \cdot {\color{green}41} \cdot [ \frac{1}{\color{green}41}\pmod {{\color{green}31}} ] + {\color{red}39} \cdot {\color{green}31} \cdot [ \frac{1}{\color{green}31}\pmod {{\color{green}41}} ] + {\color{green}31}\cdot {\color{green}41} \cdot k \quad & | \quad k\in Z\\ \end{array}\)
\(\begin{array}{rcll} && [ \frac{1}{\color{green}41}\pmod {{\color{green}31}} ] \quad &| \quad \text { modular inverse } 41\cdot \frac{1}{41} \equiv 1 \pmod {31} \\ &=& {\color{green}41}^{\varphi({\color{green}31})-1} \pmod {{\color{green}31}} \quad & | \quad \text{ Euler's totient function } \varphi(n) \quad \varphi(p) = p-1 \\ &=& 41^{30-1} \pmod {31} \\ &=& 41^{29} \pmod {31} \quad & | \quad 41 \pmod {31} = 10 \\ &=& 10^{29} \pmod {31} \\ &=& 28 \\\\ && [ \frac{1}{\color{green}31}\pmod {{\color{green}41}} ] \quad &| \quad \text { modular inverse } 31\cdot \frac{1}{31} \equiv 1 \pmod {41} \\ &=& {\color{green}31}^{\varphi({\color{green}41})-1} \pmod {{\color{green}41}} \quad & | \quad \text{ Euler's totient function } \varphi(n)\quad \varphi(p) = p-1 \\ &=& 31^{40-1} \pmod {41} \\ &=& 31^{39} \pmod {41} \\ &=& 4 \\ \end{array} \)
\(\begin{array}{|rcll|} \hline n &=& {\color{red}9} \cdot {\color{green}41} \cdot 28 + {\color{red}39} \cdot {\color{green}31} \cdot 4 + {\color{green}31}\cdot {\color{green}41} \cdot k \\ n &=& 10332 + 4836 + 1271 \cdot k \\ n &=& 15168 + 1271 \cdot k \quad & | \quad k\in Z \\ \hline \end{array}\)
\(\begin{array}{|rcll|} \hline n_{min} &=& 15168 \pmod {1271 } \\ n_{min} &=& 1187 \\\\ n &=& 1187 + 1271 \cdot k \quad & | \quad k\in Z \\ \hline \end{array}\)
The smallest number is 1187
