szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 kwi 2012, o 21:16 
Użytkownik

Posty: 16
Lokalizacja: Mielec
Witam
Potrzebuję małej pomocy z równościami modularnymi.
Chciałbym się nauczyć jak wyciagnąć resztę z dzielenia ułamków przez liczby całkowite, np. \frac{1}{23} mod 120 = ?. Inną formą jest 23^{-1} mod 120.
W tym wypadku wynikiem jest 47, i nie potrafię znaleźć odpowiedzi dlaczego akurat 47. Będę wdzięczny za pomoc.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2012, o 21:20 
Użytkownik

Posty: 3558
Lokalizacja: Wrocław
A skąd wiesz, że to 47?
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2012, o 21:32 
Użytkownik

Posty: 16
Lokalizacja: Mielec
Wolframalpha.com ;-)
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2012, o 21:47 
Użytkownik

Posty: 622
Lokalizacja: PL
23\cdot 23^{-1}=1 - zawsze

23\cdot 47=1081=1 \mod 120

stąd 23^{-1} =47 \mod 120
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2012, o 22:13 
Użytkownik

Posty: 16
Lokalizacja: Mielec
Dziękuję, ale rozumiem co to jest modulo :D
Potrzebuję sposobu, żeby obliczyć to dla dowolnej pary liczb, np ile wynosi reszta z dzielenia X^{-1} mod Y = ?
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2012, o 22:20 
Użytkownik

Posty: 622
Lokalizacja: PL
\mod to reszta z dzielenia

czyli 1081=1 \mod 120 bo
1081:120=9 r 1

a jak szukać dowolnie. ja znam tylko sposób na piechote lub jak ktoś woli zgaduj zgadula która pasu:)
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2012, o 22:24 
Użytkownik

Posty: 16
Lokalizacja: Mielec
Chyba muszę sie przeprosić z algorytmem Euklidesa, bo chyba inaczej się nie da...
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2012, o 22:32 
Użytkownik
Avatar użytkownika

Posty: 2911
Lokalizacja: Biała Podlaska / Warszawa / Zurych
Rozszerzony algorytm Euklidesa:

\begin{cases} 120\cdot 1 + 23\cdot 0 = 120\\ 120\cdot 0 + 23\cdot 1 = 23 \end{cases}

Odejmujemy od 1 równania 2 przemnożone przez \lfloor \frac{120}{23} \rfloor = 5:

\begin{cases} 120\cdot 0 + 23\cdot 1 = 23\\ 120\cdot 1 + 23\cdot (-5) = 5 \end{cases}

I tak samo:

\begin{cases} 120\cdot 1 + 23\cdot (-5) = 5 \\ 120\cdot (-4)+23\cdot 21 = 3 \end{cases} \\ \\  \begin{cases} 120\cdot (-4) + 23\cdot 21 = 3\\ 120\cdot 5 + 23\cdot (-26) = 2 \end{cases} \\ \\  \begin{cases} 120\cdot 5 + 23\cdot (-26) = 2\\ 120\cdot (-9) + 23\cdot 47 = 1 \end{cases}

Czyli 23^{-1} \equiv 47 \pmod{120}

(Dane rozumowanie przeprowadzamy dopóki któreś wyrażenie nie będzie równe 1)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba pierwsza i dzielenie z resztą  Arst  11
 Zapisywanie dzielenia z resztą, jaki błąd popełniam?  Xiaos  1
 reszta z dzielenia - zadanie 63  aska0  12
 Wyznacz reszte z dzielenia liczby przez 2  katarzynkaaa90  1
 reszta z dzielenia - zadanie 86  fuzzgun  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl