Obliczyć

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
gollum
Stały bywalec
Stały bywalec
Posty: 432
Rejestracja: 10 mar 2010, 14:05
Podziękowania: 339 razy

Obliczyć

Post autor: gollum » 25 sty 2015, 23:35

Oliczyć \(10^{-1} mod 67\) może ktoś mi powiedzieć po kolei co zrobić?

sebnorth
Stały bywalec
Stały bywalec
Posty: 871
Rejestracja: 11 gru 2010, 18:46
Lokalizacja: Puck i Trójmiasto
Otrzymane podziękowania: 413 razy
Płeć:

Post autor: sebnorth » 25 sty 2015, 23:43

\(67 = 6 \cdot 10 + 7 \\

10 = 1 \cdot 7 + 3 \\

7 = 2 \cdot 3 + 1\)


czyli:

\(1 = 7 - 2 \cdot 3 = 67 - 6\cdot 10 - 2 \cdot (10 - 1 \cdot 7 ) = 67 - 8\cdot 10 + 2 \cdot ( 67 - 6\cdot 10) = \\

= 3\cdot 67 - 20 \cdot 10\)


modulo \(67\):

\(1 = (- 20) \cdot 10 = 47 \cdot 10\)

czyli \(10^{-1} = 47\)

gollum
Stały bywalec
Stały bywalec
Posty: 432
Rejestracja: 10 mar 2010, 14:05
Podziękowania: 339 razy

Re: Obliczyć

Post autor: gollum » 25 sty 2015, 23:48

jest jakiś wzór na to? :)

sebnorth
Stały bywalec
Stały bywalec
Posty: 871
Rejestracja: 11 gru 2010, 18:46
Lokalizacja: Puck i Trójmiasto
Otrzymane podziękowania: 413 razy
Płeć:

Post autor: sebnorth » 25 sty 2015, 23:56

nie bardzo, raczej algorytm Euklidesa, chodzi o to, żeby znaleźć całkowite \(x,y\) takie, że \(ax + by = NWD(a,b)\)

w tym zadaniu \(NWD(a,b) = 1\)

gollum
Stały bywalec
Stały bywalec
Posty: 432
Rejestracja: 10 mar 2010, 14:05
Podziękowania: 339 razy

Post autor: gollum » 26 sty 2015, 00:08

zakładając że a=19, b=67?

sebnorth
Stały bywalec
Stały bywalec
Posty: 871
Rejestracja: 11 gru 2010, 18:46
Lokalizacja: Puck i Trójmiasto
Otrzymane podziękowania: 413 razy
Płeć:

Post autor: sebnorth » 26 sty 2015, 00:09

w poście na początku było \(10\) nie \(19\)

gollum
Stały bywalec
Stały bywalec
Posty: 432
Rejestracja: 10 mar 2010, 14:05
Podziękowania: 339 razy

Post autor: gollum » 26 sty 2015, 00:13

tak tak, pomyliło mi się z innym przykładem. oczywiście chodziło mi o 10

sebnorth
Stały bywalec
Stały bywalec
Posty: 871
Rejestracja: 11 gru 2010, 18:46
Lokalizacja: Puck i Trójmiasto
Otrzymane podziękowania: 413 razy
Płeć:

Post autor: sebnorth » 26 sty 2015, 00:14

tak, wtedy \(a = 19, b = 67\) albo \(a = 67, b = 19\)