Jak policzyć taką resztę z dzielenia?

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
szymonides
Użytkownik
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?

Post autor: szymonides »

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ź!
Ostatnio zmieniony 1 lis 2014, o 15:37 przez Ponewor, łącznie zmieniany 1 raz.
Powód: Teoria liczb będzie odpowiedniejszym miejscem.
miodzio1988

Jak policzyć taką resztę z dzielenia?

Post autor: miodzio1988 »

znajdz element odwrotny do \(\displaystyle{ -69}\) najpierw
Awatar użytkownika
Premislav
Użytkownik
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?

Post autor: Premislav »

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ę.
Awatar użytkownika
Ponewor
Moderator
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?

Post autor: Ponewor »

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}\).
ODPOWIEDZ