heureka

avatar
Benutzernameheureka
Punkte26387
Membership
Stats
Fragen 17
Antworten 5678

 #3
avatar+26387 
+5

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

 

laugh

13.02.2017
 #13
avatar+26387 
+10

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

 

laugh

13.02.2017