Algebra część 2 ogipierogi: Rozszerzony algorytm euklidesa... Do rozwiązania jest równanie 17x=1 mod 97 Z algorytmu euklidesa: 97=5*17+12 17=1*12+5 12=2*5+2 5=2*2+1 2=2*1+0 Dalej: Z rozszerzonego algorytmu euklidesa: 1=5−2*2=5−2(12−2*5)=... Wiem że na necie są kalkulatory do tego, ale jakoś od tego momentu nie czaję, czy jest ktoś w stanie wytłumaczyć jak dalej posłużyć się tym algorytmem, na podstawie rozwiązania?

ogipierogi: Podbijam.

ogipierogi: Podbijam

ogipierogi: podbijam

Trivial: Sprawdzam! http://www.algorytm.org/algorytmy-arytmetyczne/rozszerzony-algorytm-euklidesa.html

PW: Mniejsza o Euklidesa, poker ciekawszy.

ogipierogi: pomóżcie bo gubie się w momencie kiedy rozpisałem to co powyżej w rozszerzonym, nie wiem jak wygląda kolejny krok

Trivial: Już doczytałem. Trzeba po prostu mnożyć i zamieniać po kolei aż do końca. 1 = 5 − 2*2 = 5 − 2*(12 − 2*5) = −2*12 + 5*5 = −2*12 + 5*(17 − 1*12) = 5*17 − 7*12 = 5*17 − 7*(97 − 5*17) = 40*17 − 7*97 Zatem 17*x = 40*17 − 7*97 (mod 97) x = 40.

ogipierogi: kurde no nie rozumiem co się stało w tym momencie: −2*12 + 5*5

Trivial: Wymnożyłem i przegrupowałem czynniki. 5 − 2*2 = 5 − 2*(12 − 2*5) = 5 − 2*12 + 4*5 = 5*5 − 2*12 = −2*12 + 5*5

Mila: Witaj Trivial, liczyłam inaczej i mam wynik 42. Ogi, jaka masz odpowiedź?

Trivial: Witaj, Milu. Odpowiedź to x = 40. http://www.wolframalpha.com/input/?i=17*x+%3D+1+mod+97

ogipierogi: dzięki, wreszcie czaje o co chodzi

Mila: Dziękuję. Szukam błędu.

ogipierogi: mam w zasadzie ostatni problem mam równanie 17x=3 mod 43 doprowadziłem z rozszerzonego euklidesa 2*43−5*17 i teraz jak znaleźć rozwiązanie?

Mila: Znalazłam błąd. 17x=1(mod97) /*5 85x=5(mod97) −12x=5(mod97) /*(−1) 12x=−5 (mod97) /*8 96x=−40 (mod 97) −1x=−40 ( mod97) /*(−1) x=40 (mod 97)

Trivial: Rozważania mod 43: 17x = 3 = 3*(2*43−5*17) ≡ −3*5*17 x = −15 ≡ 28

ogipierogi: czyli po wykonaniu rozszerzonego algorytmu nie zawsze mam od razu wynik tak? mógłbyś mi jeszcze bardziej łopatoloicznie przedstawić co tam się stało bo nie za bardzo to kminie

Mila: Moje takie: 17x=3(mod43) /*3 51x=9 (mod 43) 8x=9 (mod 43) /*4 32x=36 (mod 43) −11x=36 (mod 43) 11x=−36 (mod 43) 11x=7 (mod 43) /*4 44x=28 (mod 43) x=28 (mod 43)

Trivial: Ax = B (mod M) Algorytm polega na znalezieniu takich liczb u,v że: Au + Mv = 1 Wtedy: Ax = B = B*1 = B*(Au + Mv) = ABu + BMv ≡ ABu Ax = ABu x = Bu. x jest wtedy rozwiązaniem. Ale rozwiązaniem jest też x' = x + kM, gdyż: Ax' = A(x + kM) = Ax + AkM ≡ Ax. Odnosząc to do przykładu wyżej, x = −15 jest rozwiązaniem, ale tak samo rozwiązaniem jest x = 28 (−15 + 43 = 28), a także wiele innych liczb x postaci x = 28 + k*43

Mila: Ogi przeczytaj dokładnie własności kongruencji.

ogipierogi: no mistrz, polać mu dzięki bardzo Trivial!

Trivial: Powodzenia w zrozumieniu arytmetyki modularnej! Dobranoc.