Matematyka.pl

Wyznaczyc najmniejsza dodatnia liczbe naturalna , ktora jest rozwiazaniem ukadu rownan

\(\displaystyle{ x \equiv 12 (\mod 11)}\)
\(\displaystyle{ x \equiv 33 (\mod 23)}\)
\(\displaystyle{ x \equiv 76 (\mod 31)}\)

Korzystam z Chińskiego twierdzenie o resztach

\(\displaystyle{ a_1{}=12}\)
\(\displaystyle{ m_1{}=11}\)
\(\displaystyle{ a_2{}=33}\)
\(\displaystyle{ m_2{}=23}\)
\(\displaystyle{ a_3{}=76}\)
\(\displaystyle{ m_3{}=31}\)

\(\displaystyle{ m_1{}, m_2{}, m_3{},}\) sa wzglednie pierwsze, wiec uklad kongruencji ma jednoznaczne rozwiazanie modulo \(\displaystyle{ m_1{}m_2{}m_3{},}\)

Wprowadzmy nastepujace oznaczenia:
\(\displaystyle{ M=m_1{}m_2{}m_3{}}\)
\(\displaystyle{ M_i{}= \frac M{m_i}}\)
\(\displaystyle{ x_i{}= {M_i}^{-1} \mod m_i{}}\)
\(\displaystyle{ x=a_1{}M_1{}x_1{}+a_2{}M_2{}x_2{}+a_3{}M_3{}x_3{}}\)

Obliczenia:
\(\displaystyle{ M=11 \cdot 23 \cdot 31=7843}\)
\(\displaystyle{ {M_1}=713}\)
\(\displaystyle{ {M_2}=341}\)
\(\displaystyle{ {M_3}=253}\)

\(\displaystyle{ {x_1}=9}\)
\(\displaystyle{ {x_2}=19}\)
\(\displaystyle{ {x_3}=5}\)

\(\displaystyle{ x=77004+2013807+96140(\mod 7843)}\)
\(\displaystyle{ x=386951(\mod 7843)}\)
\(\displaystyle{ x=2644(\mod 7843)}\)

Lecz \(\displaystyle{ x=2644}\) jest zla odpowiedzia, poniewaz gdy podstawiam
\(\displaystyle{ 2644 \mod 11 = 4}\) (a powinno byc \(\displaystyle{ 12}\))
\(\displaystyle{ 2644 \mod 23 = 22}\) (a powinno byc \(\displaystyle{ 33}\))
\(\displaystyle{ 2644 \mod 31 = 9}\) (a powinno byc \(\displaystyle{ 76}\))

Co robie zle ?
Wydaje mi sie ze blednie wyznaczam \(\displaystyle{ x_i{}}\)
Ja wyznaczam go jako modulo \(\displaystyle{ \frac {M_i} {m_i}}\)-- 25 maja 2014, o 15:52 --

No źle wyznaczasz. Nie interesuje nas reszta z dzielenia \(\displaystyle{ M_{i}}\) przez \(\displaystyle{ m_{i}}\), tylko reszta z dzielenia \(\displaystyle{ M_{i}^{-1}}\) przez \(\displaystyle{ m_{i}}\). Innymi słowy szukamy takiej liczby całkowitej \(\displaystyle{ x_{i}}\), że \(\displaystyle{ x_{i}M_{i} \equiv 1 \pmod{m_{i}}}\).