Mam takie zadanie
Oblicz \(\displaystyle{ -69 ^{-1} mod 1313}\)
Jak to rozwiązać? Domyślam się, że jest na to jakaś sztuczka. To zadanie jest na liście zadań z kongruencji, ale nie wiem jak to może mi pomóc.
Z góry dziękuję za odpowiedź!
Jak policzyć taką resztę z dzielenia?
-
- Użytkownik
- Posty: 78
- Rejestracja: 24 lis 2009, o 17:22
- Płeć: Mężczyzna
- Podziękował: 4 razy
Jak policzyć taką resztę z dzielenia?
Ostatnio zmieniony 1 lis 2014, o 15:37 przez Ponewor, łącznie zmieniany 1 raz.
Powód: Teoria liczb będzie odpowiedniejszym miejscem.
Powód: Teoria liczb będzie odpowiedniejszym miejscem.
- Premislav
- Użytkownik
- Posty: 15685
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 195 razy
- Pomógł: 5219 razy
Jak policzyć taką resztę z dzielenia?
W sensie chodzi o taką liczbę \(\displaystyle{ m}\), że \(\displaystyle{ -69m\equiv 1 \pmod{1313}}\)? Bo na to wygląda.
No to to jest równoważne\(\displaystyle{ 1244m\equiv 1\pmod{1313}}\).
Zrób z Euklidesa (tj. zastosuj rozszerzony algorytm Euklidesa dla \(\displaystyle{ 1244}\) i \(\displaystyle{ 1313)}\).
Może istnieje sprytniejsza metoda, ale takiej na razie nie widzę.
No to to jest równoważne\(\displaystyle{ 1244m\equiv 1\pmod{1313}}\).
Zrób z Euklidesa (tj. zastosuj rozszerzony algorytm Euklidesa dla \(\displaystyle{ 1244}\) i \(\displaystyle{ 1313)}\).
Może istnieje sprytniejsza metoda, ale takiej na razie nie widzę.
- 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
Jak policzyć taką resztę z dzielenia?
No cóż istnieje pewna raczej mało uniwersalna metoda na uniknięcie algorytmu Euklidesa:
Mamy kongruencję \(\displaystyle{ -69m \equiv 1 \pmod{1313}}\)
Rozbijamy ją sobie na dwie:
\(\displaystyle{ -69m \equiv 1 \pmod{13} \Leftrightarrow -4m \equiv 1 \pmod{13}}\)
i możemy teraz nietrudno odgadnąć, że \(\displaystyle{ m \equiv 3 \pmod{13}}\), a jak nie, to mnożymy ostatnie przystawanie razy \(\displaystyle{ 17}\) i dostajemy \(\displaystyle{ -68m \equiv 17 \pmod{13}}\) - to jak odejmiemy od tego pierwszą, to mamy \(\displaystyle{ m \equiv 16 \equiv 3 \pmod{13}}\).
Mamy też jeszcze kongruencję \(\displaystyle{ -69m \equiv 101 \pmod{101} \Leftrightarrow 32m \equiv 1 \pmod{101}}\), skąd dalej \(\displaystyle{ 96m \equiv 3 \pmod{101}}\) i \(\displaystyle{ 5m \equiv -3 \pmod{101}}\) (tu już można się pokusić o odganięcie wyniku - \(\displaystyle{ 60}\), a jak nie to patrz dalej) i teraz \(\displaystyle{ 95m \equiv -3 \cdot 19 \equiv -57 \pmod{101}}\), więc ostatecznie \(\displaystyle{ m\equiv 3 - \left(-57\right)\equiv 60 \pmod{101}}\).
Teraz trzeba to zebrać w całość - \(\displaystyle{ 101k +60 = 13l+3}\) co daje nam równoważnie \(\displaystyle{ 101k+57 \equiv 0 \pmod{13}}\) czyli\(\displaystyle{ 10k + 5 \equiv 0 \pmod{13}}\) - znów, jak nie umiemy odgadnąć jakie jest \(\displaystyle{ k}\), to robimy z tego \(\displaystyle{ 100k+50 \equiv 0 \pmod{13}}\) i ostatecznie \(\displaystyle{ k+7 \equiv 0 \pmod{13} \Leftrightarrow k \equiv 6 \pmod{13}}\)[/latex]
No to bierzemy \(\displaystyle{ k=6}\) i nasz wynik to\(\displaystyle{ 101k+60}\).
Mamy kongruencję \(\displaystyle{ -69m \equiv 1 \pmod{1313}}\)
Rozbijamy ją sobie na dwie:
\(\displaystyle{ -69m \equiv 1 \pmod{13} \Leftrightarrow -4m \equiv 1 \pmod{13}}\)
i możemy teraz nietrudno odgadnąć, że \(\displaystyle{ m \equiv 3 \pmod{13}}\), a jak nie, to mnożymy ostatnie przystawanie razy \(\displaystyle{ 17}\) i dostajemy \(\displaystyle{ -68m \equiv 17 \pmod{13}}\) - to jak odejmiemy od tego pierwszą, to mamy \(\displaystyle{ m \equiv 16 \equiv 3 \pmod{13}}\).
Mamy też jeszcze kongruencję \(\displaystyle{ -69m \equiv 101 \pmod{101} \Leftrightarrow 32m \equiv 1 \pmod{101}}\), skąd dalej \(\displaystyle{ 96m \equiv 3 \pmod{101}}\) i \(\displaystyle{ 5m \equiv -3 \pmod{101}}\) (tu już można się pokusić o odganięcie wyniku - \(\displaystyle{ 60}\), a jak nie to patrz dalej) i teraz \(\displaystyle{ 95m \equiv -3 \cdot 19 \equiv -57 \pmod{101}}\), więc ostatecznie \(\displaystyle{ m\equiv 3 - \left(-57\right)\equiv 60 \pmod{101}}\).
Teraz trzeba to zebrać w całość - \(\displaystyle{ 101k +60 = 13l+3}\) co daje nam równoważnie \(\displaystyle{ 101k+57 \equiv 0 \pmod{13}}\) czyli\(\displaystyle{ 10k + 5 \equiv 0 \pmod{13}}\) - znów, jak nie umiemy odgadnąć jakie jest \(\displaystyle{ k}\), to robimy z tego \(\displaystyle{ 100k+50 \equiv 0 \pmod{13}}\) i ostatecznie \(\displaystyle{ k+7 \equiv 0 \pmod{13} \Leftrightarrow k \equiv 6 \pmod{13}}\)[/latex]
No to bierzemy \(\displaystyle{ k=6}\) i nasz wynik to\(\displaystyle{ 101k+60}\).