Hitta minsta positiva lösning till kongruenssystemet

Find the least nonnegative solution of the system of congruences below.

$\{\begin{cases} x \equiv 2 (m o d 3) \\ \begin{array}{l} x \equiv 1 (m o d 5) \\ x \equiv 4 (m o d 7) \end{array} \end{cases}$

Lösning:

$\{\begin{cases} x \equiv 2 (m o d 3) \\ \begin{array}{l} x \equiv 1 (m o d 5) \\ x \equiv 4 (m o d 7) \end{array} \end{cases} \Rightarrow \{\begin{cases} \begin{matrix} M = 3 * 5 * 7 = 105 \\ M_{1} = 5 * 7 = 35 \\ M_{2} = 3 * 7 = 21 \end{matrix} \\ M_{3} = 3 * 5 = 15 \end{cases} \Rightarrow \{\begin{cases} M_{1} x_{1} = 35 x_{1} \equiv 2 (m o d 3) \\ \begin{array}{l} M_{2} x_{2} = 21 x_{2} \equiv 1 (m o d 5) \\ M_{3} x_{3} = 15 x_{3} \equiv 4 (m o d 7) \end{array} \end{cases} \Leftrightarrow \Leftrightarrow \{\begin{cases} 2 x_{1} \equiv 2 (m o d 3) \\ \begin{array}{l} x_{2} \equiv 1 (m o d 5) \\ x_{3} \equiv 4 (m o d 7) \end{array} \end{cases} \Rightarrow \{\begin{cases} x_{1} \equiv 1 (m o d 3) \\ \begin{array}{l} x_{2} \equiv 1 (m o d 5) \\ x_{3} \equiv 4 (m o d 7) \end{array} \end{cases} \Rightarrow \{\begin{cases} x_{1} = 1 \\ \begin{array}{l} x_{2} = 1 \\ x_{3} = 4 \end{array} \end{cases} \Rightarrow \Rightarrow 2 * M_{1} * x_{1} + 1 * M_{2} * x_{2} + 4 * M_{3} * x_{3} = 2 * 35 * 1 + 1 * 21 * 1 + 4 * 15 * 4 = 70 + 21 + 240 = 331 \equiv 16 (m o d 105)$

Facit säger dock 11 istället för 16. Men jag kan inte se var jag gör fel.

Jag antar att du använder metoden som kan användas för att bevisa Kinesiska restsatsen. Det finns däremot bättre sätt att beräkna detta om man bara är ute efter lösningen. Man gör så här, ekvationen

$x \equiv 2 (m o d 3)$

innebär att $x = 3 k_{0} + 2$ för något heltal $k_0$ . Då får man sen att

$x \equiv 1 (m o d 5) \Rightarrow 3 k_{0} + 2 \equiv 1 (m o d 5) \Rightarrow k_{0} \equiv 3 (m o d 5)$

Så därför är $k_0 = 5k_1 + 3$ för något heltal $k_1$ . Så då får man att $x = 3k_0 + 2 = 3(5k_1 + 3) + 2 = 15k_1 + 11$ . Sen får man

$x \equiv 4 (m o d 7) \Rightarrow 15 k_{1} + 11 \equiv 4 (m o d 7) \Rightarrow k_{1} \equiv 0 (m o d 7)$

Därför får man att $k_1 = 7k_2$ vilket ger att $x = 15k_1 + 11 = 15\cdot 7k_2 + 11 = 105k_2 + 11$ . Därför får man att minsta positiva lösningen är $x = 11$ .

Svara Avbryt