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 --
Chińskie twierdzenie o resztach
-
- Użytkownik
- Posty: 62
- Rejestracja: 2 gru 2013, o 09:51
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 18 razy
Chińskie twierdzenie o resztach
Ostatnio zmieniony 24 maja 2014, o 13:56 przez lukasz1804, łącznie zmieniany 1 raz.
Powód: Symbol działania modulo to \mod . Symbol mnożenia to \cdot.
Powód: Symbol działania modulo to \mod . Symbol mnożenia to \cdot.
- Ponewor
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
Chińskie twierdzenie o resztach
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}}}\).