problem z CRT
-
- Użytkownik
- Posty: 113
- Rejestracja: 8 lis 2014, o 15:33
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 2 razy
- Pomógł: 4 razy
problem z CRT
Witam.
Mam problem z chińskim twierdzeniem o resztach, co zrobiłem nie tak.
\(\displaystyle{ x\equiv 1 \pmod {11}}\)
\(\displaystyle{ x\equiv 2 \pmod {23}}\)
\(\displaystyle{ x\equiv 3 \pmod {5}}\)
wyliczyłem że:
\(\displaystyle{ x=1 \cdot 115 \cdot 5 + 2 \cdot 55 \cdot 9 +3 \cdot 253 \cdot 3 \pmod {1265}}\)
\(\displaystyle{ x= 47}\)
co nijak nie pasuje, gdzie popełniłem błąd?
Mam problem z chińskim twierdzeniem o resztach, co zrobiłem nie tak.
\(\displaystyle{ x\equiv 1 \pmod {11}}\)
\(\displaystyle{ x\equiv 2 \pmod {23}}\)
\(\displaystyle{ x\equiv 3 \pmod {5}}\)
wyliczyłem że:
\(\displaystyle{ x=1 \cdot 115 \cdot 5 + 2 \cdot 55 \cdot 9 +3 \cdot 253 \cdot 3 \pmod {1265}}\)
\(\displaystyle{ x= 47}\)
co nijak nie pasuje, gdzie popełniłem błąd?
-
- Administrator
- Posty: 34239
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
problem z CRT
Nie rozumiem sposobu liczenia(może nie znam jakiejś dziwnej metody?)
Poniżej rozwiązanie, nie sprawdzaj go od razu, później sobie z nim wynik możesz sprawdzić
Pokaż obliczenia, będzie nam łatwiej pomóc
Poniżej rozwiązanie, nie sprawdzaj go od razu, później sobie z nim wynik możesz sprawdzić
Ukryta treść:
Ostatnio zmieniony 26 sty 2017, o 23:49 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
-
- Użytkownik
- Posty: 113
- Rejestracja: 8 lis 2014, o 15:33
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 2 razy
- Pomógł: 4 razy
problem z CRT
skorzystałem ze wzoru Sun Zi ( chiński matematyk), z książki Teoria Liczb w Informatyce.
W najbliższym czasie podam jak to liczyłem.
-- 27 sty 2017, o 00:56 --
wzór:
\(\displaystyle{ x\equiv\sum_{i=1}^{n}a_{i}M_{i}M^{'}_{i} \pmod{m}}\)
gdzie:
\(\displaystyle{ m=m_{1}m_{2} \cdot \cdot \cdot m_{3}}\)
\(\displaystyle{ M_{i}= \frac{m}{m_{i}}}\)
\(\displaystyle{ M^{'}_{i}= M^{-1}_{i} \pmod{m_{i}}}\)
\(\displaystyle{ i=1,2,....,n}\)
poniżej jak liczyłem:
\(\displaystyle{ m=m_{1}m_{2}m_{3}= 11 \cdot 23 \cdot 5 =1265}\)
\(\displaystyle{ M_{1}= \frac{m}{m_{1}}= \frac{1265}{11}= 115}\)
\(\displaystyle{ M^{'}_{1}=M^{-1}_{1} \pmod{m_{1}} = 115^{-1}\pmod{11}= 5}\)
\(\displaystyle{ M_{2}= \frac{m}{m_{2}}= \frac{1265}{23}= 55}\)
\(\displaystyle{ M^{'}_{2}=M^{-1}_{2} \pmod{m_{2}} = 55^{-1}\pmod{23}= 9}\)
\(\displaystyle{ M_{3}= \frac{m}{m_{3}}= \frac{1265}{5}= 253}\)
\(\displaystyle{ M^{'}_{3}=M^{-1}_{3} \pmod{m_{3}} = 253^{-1}\pmod{5}= 3}\)
stąd:
\(\displaystyle{ x=a_{1}M_{1}M^{'}_{1}+a_{2}M_{2}M^{'}_{2}+a_{3}M_{3}M^{'}_{3} \pmod{m}}\)
\(\displaystyle{ x=1 \cdot 115 \cdot 5+2 \cdot 55 \cdot 9+3 \cdot 253 \cdot 3 \pmod{1265}= 47}\)
wynik wyszedł tylko że źle.
W najbliższym czasie podam jak to liczyłem.
-- 27 sty 2017, o 00:56 --
wzór:
\(\displaystyle{ x\equiv\sum_{i=1}^{n}a_{i}M_{i}M^{'}_{i} \pmod{m}}\)
gdzie:
\(\displaystyle{ m=m_{1}m_{2} \cdot \cdot \cdot m_{3}}\)
\(\displaystyle{ M_{i}= \frac{m}{m_{i}}}\)
\(\displaystyle{ M^{'}_{i}= M^{-1}_{i} \pmod{m_{i}}}\)
\(\displaystyle{ i=1,2,....,n}\)
poniżej jak liczyłem:
\(\displaystyle{ m=m_{1}m_{2}m_{3}= 11 \cdot 23 \cdot 5 =1265}\)
\(\displaystyle{ M_{1}= \frac{m}{m_{1}}= \frac{1265}{11}= 115}\)
\(\displaystyle{ M^{'}_{1}=M^{-1}_{1} \pmod{m_{1}} = 115^{-1}\pmod{11}= 5}\)
\(\displaystyle{ M_{2}= \frac{m}{m_{2}}= \frac{1265}{23}= 55}\)
\(\displaystyle{ M^{'}_{2}=M^{-1}_{2} \pmod{m_{2}} = 55^{-1}\pmod{23}= 9}\)
\(\displaystyle{ M_{3}= \frac{m}{m_{3}}= \frac{1265}{5}= 253}\)
\(\displaystyle{ M^{'}_{3}=M^{-1}_{3} \pmod{m_{3}} = 253^{-1}\pmod{5}= 3}\)
stąd:
\(\displaystyle{ x=a_{1}M_{1}M^{'}_{1}+a_{2}M_{2}M^{'}_{2}+a_{3}M_{3}M^{'}_{3} \pmod{m}}\)
\(\displaystyle{ x=1 \cdot 115 \cdot 5+2 \cdot 55 \cdot 9+3 \cdot 253 \cdot 3 \pmod{1265}= 47}\)
wynik wyszedł tylko że źle.
Ostatnio zmieniony 27 sty 2017, o 11:20 przez Kera, łącznie zmieniany 1 raz.
- Chewbacca97
- Użytkownik
- Posty: 464
- Rejestracja: 9 lis 2013, o 22:09
- Płeć: Mężczyzna
- Podziękował: 33 razy
- Pomógł: 120 razy
-
- Użytkownik
- Posty: 113
- Rejestracja: 8 lis 2014, o 15:33
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 2 razy
- Pomógł: 4 razy
problem z CRT
Chewbacca97nie mam pojęcia jak zgodnie ze wzorem wynikiem jest \(\displaystyle{ 9}\)
możesz go rozpisać?
\(\displaystyle{ M^{'}_{1}=M^{-1}_{1} \pmod{m_{1}} = 115^{-1}\pmod{11}= 9}\)
możesz go rozpisać?
\(\displaystyle{ M^{'}_{1}=M^{-1}_{1} \pmod{m_{1}} = 115^{-1}\pmod{11}= 9}\)
-
- Administrator
- Posty: 34239
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
problem z CRT
Ja bym się raczej zapytał, skąd wytrzasnąłeś
\(\displaystyle{ 115^{-1}\pmod{11}= \red 5}\)...
Bo podejrzewam, że pomyliłeś mnożenie z dodawaniem.
JK
\(\displaystyle{ 115^{-1}\pmod{11}= \red 5}\)...
Bo podejrzewam, że pomyliłeś mnożenie z dodawaniem.
JK
- Chewbacca97
- Użytkownik
- Posty: 464
- Rejestracja: 9 lis 2013, o 22:09
- Płeć: Mężczyzna
- Podziękował: 33 razy
- Pomógł: 120 razy
-
- Administrator
- Posty: 34239
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
problem z CRT
Kera podał ten wzór, ale niepoprawnie go zastosował, bo niepoprawnie wyznaczał elementy odwrotne.
JK
JK
-
- Użytkownik
- Posty: 113
- Rejestracja: 8 lis 2014, o 15:33
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 2 razy
- Pomógł: 4 razy
problem z CRT
Matematyka nigdy mnie nie lubiła, ale czy ten post https://www.matematyka.pl/78980.htm
jest odpowiedzią na temat wyznaczania elementów odwrotnych?
Wybrałem Teorię Liczb bo jest najbardziej interesującą, a że traktuję ją jako hobby to pytam zamiast błądzić.
jest odpowiedzią na temat wyznaczania elementów odwrotnych?
Wybrałem Teorię Liczb bo jest najbardziej interesującą, a że traktuję ją jako hobby to pytam zamiast błądzić.
-
- Administrator
- Posty: 34239
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
problem z CRT
Może być.Kera pisze:Matematyka nigdy mnie nie lubiła, ale czy ten post https://www.matematyka.pl/78980.htm
jest odpowiedzią na temat wyznaczania elementów odwrotnych?
Po prostu algorytm Euklidesa i odwrotny algorytm Euklidesa. Z tym, że do CRT nie jest to niezbędne - Twój wzór może ładnie wygląda, ale rozwiązania nie skraca. Szybciej jest to zrobić wprost.
JK