szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 kwi 2012, o 20: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.
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2012, o 20:20 
Użytkownik

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

Posty: 16
Lokalizacja: Mielec
Wolframalpha.com ;-)
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2012, o 20: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 21: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 21: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 21: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 21:32 
Użytkownik
Avatar użytkownika

Posty: 2909
Lokalizacja: Biała Podlaska / Warszawa
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 
 Reszta z dzielenia, kongruencje  Moniak137  1
 Oblicz reszte z dzielenia - zadanie 8  ak2  1
 Zamiana ułamkw zwykłych i liczb mieszanych na ułamki dzie  Worm_Ted  3
 Reszta z dzielenia - zadanie 105  saweh  5
 Trzy zadania :podzielność, reszta z dzielenia i NWD  crewlbn  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl