znaleźć 19 do minus 1 w zbiorze liczb całk. modulo 31

[karl153]

Dzień dobry,

Za pomocą metody "Blancship'a" (nazwa ze słuchu, był bym wdzięczny jakby mi ktoś przybliżył jej zapis bo w/w - fonetyczny - jest nieznany nawet google i oprócz notatek własnych nie mam innego źródła z którego mógłbym poczytać o niej szerzej. ) znaleźć \(\displaystyle{ 19^{-1}}\) w zbiorze liczb całkowitych modulo 31. To tylko rozwiązany przykład z lekcji, którego nie rozumiem do końca i chciałbym aby ktoś mi rozwinął znaczenie pierwszej i drugiej kolumny. Rozwiązanie w/w przykładu:
\(\displaystyle{ \left[\begin{array}{ccc}1&0&31\\0&1&19\end{array}\right]}\) \(\displaystyle{ w_{1} \longmapsto w_{1}-w_{2}}\)

\(\displaystyle{ \begin{bmatrix} 1&-1&12\\0&1&19\end{bmatrix}}\) \(\displaystyle{ w_{2} \longmapsto w_{2}-w_{1}}\)

\(\displaystyle{ \begin{bmatrix} 1&-1&12\\-1&2&7\end{bmatrix}}\) \(\displaystyle{ w_{1} \longmapsto w_{1}-w_{2}}\)

\(\displaystyle{ \begin{bmatrix} 2&-3&5\\-1&2&7\end{bmatrix}}\) \(\displaystyle{ w_{2} \longmapsto w_{2}-w_{1}}\)

\(\displaystyle{ \begin{bmatrix} 2&-3&5\\-3&5&2\end{bmatrix}}\) \(\displaystyle{ w_{1} \longmapsto w_{1}-2 \cdot w_{2}}\)

\(\displaystyle{ \begin{bmatrix} 8&-13&1\\...\end{bmatrix}}\)
W zasadzie to odpowiedź chyba jest taka: \(\displaystyle{ 19^{-1} = 18 mod 31}\)
Był bym naprawdę wdzięczny chociaż za nazwanie tego sposobu, albo wytłumaczenie, dzięki i pozdrawiam.

[xiikzodz]

Nazwy nie znam, ale sam algorytm jest prosty (zasadniczo jest to rozszerzony algorytm Euklidesa plus metoda Gaussa - chyba).

Żeby zrozumieć, rozważmy macierz np. z trzeciej linijki przekształceń:

\(\displaystyle{ \begin{pmatrix}1&-1&12\\-1&2&7\end{pmatrix}}\)

Koduje ona następującą równość:

\(\displaystyle{ \begin{pmatrix}1&-1\\-1&2\end{pmatrix}\begin{pmatrix}31\\19\end{pmatrix}=\begin{pmatrix}12\\7\end{pmatrix}}\).

Znaczy się każda linijka tych przekształceń koduje równość postaci:

\(\displaystyle{ A\begin{pmatrix}31\\19\end{pmatrix}=b}\)


gdzie \(\displaystyle{ b}\) jest wektorem, trzecią kolumną w przekształcanej w metodzie macierzy.

Równość zachodzi w \(\displaystyle{ \mathbb{Z}}\), gdzie wykonujemy operacje.

Wystarczy więc, operując na wierszach otrzymać \(\displaystyle{ 1}\) na jednej ze współrzędnych wektora \(\displaystyle{ b}\) i wówczas w tym samym wierszu środkowej (drugiej) kolumny stoi multiplikatywna odwrotność modulo.

[karl153]

no tak, a dlaczego na początku jest w pierwszych dwóch linijkach 1 0, 0 1 potem 1 zmienia się na -1 itd. od czego zależą te zmiany ? no i odpowiedzią w/w zadania faktycznie jest \(\displaystyle{ 19^{-1} = 18 mod 31}\)

[xiikzodz]

Wygodnie jest zacząć od jakiejś prostej równości postaci \(\displaystyle{ Av=b}\), tu \(\displaystyle{ A}\) jest dowolna macierza \(\displaystyle{ 2\times 2}\) o wspolczynnikach calkowitych, zas \(\displaystyle{ v= \begin{pmatrix}31\\19\end{pmatrix}}\), choć nie ma znaczenia od której zaczniemy, byle \(\displaystyle{ A}\) była odwracalna. Tu jest to oczywista równość:

\(\displaystyle{ \begin{pmatrix}1&0\\0&1\end{pmatrix} \begin{pmatrix}31\\19\end{pmatrix}= \begin{pmatrix}31\\19\end{pmatrix}}\)

Operujac na wierszach, to jest dbając o to, żeby w ostatniej kolumnie były coraz mniejsze co do modułu liczby całkowite, ostatecznie otrzymamy 1 i wyznaczymy szukają odwrotnosc.

Tak, \(\displaystyle{ 18 = -13}\) jest multiplikatywna odwrotnoscia \(\displaystyle{ 19}\) modulo \(\displaystyle{ 31}\).

Zmiany to operacje elementarne na wierszach:

[karl153]

to była nasza pierwsza lekcja, oprócz tego co wyniosłem z liceum nie mam dodatkowej wiedzy, tak więc, jak dotąd nie znam macierzy ani metody gaussa. Jak by dało się najprostszymi słowami opisać mechanizm na podstawie którego zachodzą zmiany w pierwszej i drugiej linijce, macierzy i skomentować jeszcze dlaczego akurat 18 jest wynikiem był bym bardzo wdzięczny.

[xiikzodz]

Obiekt, który w tym algorytmie podlega zmianom w kolejnych krokach to macierz. Macierze maja wiersze i kolumny. Operacja elementarna polega na pomnozeniu któregoś wiersza/kolumny przez jakaś liczbę, tu całkowita, i dodaniu pomnozonego wiersza/kolumny do jakiegoś innego wiersza. Stad te napisy po prawej, np. \(\displaystyle{ w_1\mapsto w_1-2w_2}\) oznacza zastąpienie pierwszego wiersza wierszem otrzymanym w wyniku pomnozenia drugiego wiersza przez 2 i odjecia rezultatu tej operacji od pierwszego wiersza. Tu jest to opisane:

[karl153]

J. Rutkowski "Algebra liniowa w zadaniach" no i wikipedia,google - tam na pewno coś znajdę, ale tego jest po prostu za dużo, chociaż takie pytanie: Odejmuje od większej mniejszą, wpisuje różnicę na jej miejsce i w tym samym wierszu 0 zmieniam na -1 - dlaczego? , i kontynuuje dalej aż do NWD,

\(\displaystyle{ \left[\begin{array}{ccc}1&0&31\\0&1&19\end{array}\right] w_{1} \longmapsto w_{1}-w_{2}

\begin{bmatrix} 1&-1&12\\0&1&19\end{bmatrix} w_{2} \longmapsto w_{2}-w_{1}}\)

[xiikzodz]

Sam algorytm jest bardzo prosty. Przy odrobinie bardziej optymistycznym i mniej roszczeniowym podejściu jego przyswojenie zajmie ci mniej czasu niż podziekownie innemu użytkownikowi forum za jego chęć pomocy. (Jeśli natomiast usilujesz zrozumieć, dlaczego algorytm działa, to mój pierwszy post opisuje niezmiennik, warunkiem stopu jest otrzymanie 1 w jednym z dwóch miejsc trzeciej kolumny, warunek stopu zostanie zrealizowany w skonczonej liczbie kroków, o ile w każdym zadbamy o to, żeby w trzeciej kolumnie były coraz mniejsze co do modulu liczby całkowite.)

[karl153]

żeby ten algorytm miał nazwę chociaż to chętnie bym poczytał na boku, ale przy próbie znalezienia zawsze wpadam na macierze albo jakieś kosmiczne twierdzenia liczby itp. wiem, że w/w przykładzie: NWD to 1 \(\displaystyle{ 1=8 \cdot 31-13 \cdot 19}\) a \(\displaystyle{ -13 \cdot 19 = 1}\) ale wskaż mi w internecie teorie o tym - dokładnie tym, algorytmie - bo ja nie potrafię zrobić przykładu na nim opartego, nie potrafię obliczyć, nie potrafię dojść do tego jak zostało obliczone i dlatego pytam się na forum bo na zajęciach nie było mowy o skomplikowanej terminologii, więc wiem że opis tych dwóch kolumn ma jasne, proste wyjaśnienie i takiego się spodziewałem, to jest tak skomplikowane żeby niemożna było wyrazić w kilku zdaniach ?.

[octahedron]

Startujemy z takimi dwoma równaniami:

\(\displaystyle{ \begin{cases} \fbox{1}\cdot 31+\fbox{0}\cdot19=\fbox{31}\\\fbox{0}\cdot 31+\fbox{1}\cdot 19=\fbox{19} \end{cases}}\)

i jak widać mamy liczby, które stoją w pierwszej tabelce, teraz odejmujemy \(\displaystyle{ II}\) równanie od \(\displaystyle{ I}\):

\(\displaystyle{ \fbox{1}\cdot 31+\fbox{0}\cdot 19 -\fbox{0}\cdot 31-\fbox{1}\cdot 19=\fbox{31}-\fbox{19}\\
\fbox{1}\cdot 31 +\fbox{-1}\cdot 19=\fbox{12}}\)

i tabelka wygląda teraz tak:

\(\displaystyle{ \begin{cases} \fbox{1}\cdot 31+\fbox{-1}\cdot19=\fbox{12}\\\fbox{0}\cdot 31+\fbox{1}\cdot 19=\fbox{19} \end{cases}}\)

no to teraz \(\displaystyle{ I}\) od \(\displaystyle{ II}\) - zawsze to z mniejszą liczbą po prawej od tego z większą

\(\displaystyle{ \fbox{0}\cdot 31+\fbox{1}\cdot 19 -\fbox{1}\cdot 31-\fbox{-1}\cdot 19=\fbox{19}-\fbox{12}\\
\fbox{-1}\cdot 31 +\fbox{2}\cdot 19=\fbox{7}}\)

i tabelka wygląda tak:

\(\displaystyle{ \begin{cases} \fbox{1}\cdot 31+\fbox{-1}\cdot19=\fbox{12}\\\fbox{-1}\cdot 31+\fbox{2}\cdot 19=\fbox{7} \end{cases}}\)

i dalej \(\displaystyle{ I-II}\):

\(\displaystyle{ \begin{cases} \fbox{2}\cdot 31+\fbox{-3}\cdot19=\fbox{5}\\\fbox{-1}\cdot 31+\fbox{2}\cdot 19=\fbox{7} \end{cases}\\ \\II-I:}\)

\(\displaystyle{ \begin{cases} \fbox{2}\cdot 31+\fbox{-3}\cdot19=\fbox{5}\\\fbox{-3}\cdot 31+\fbox{5}\cdot 19=\fbox{2} \end{cases}\\ \\I-2\cdot II:}\)

\(\displaystyle{ \begin{cases} \fbox{8}\cdot 31+\fbox{-13}\cdot19=\fbox{1}\\\fbox{-3}\cdot 31+\fbox{5}\cdot 19=\fbox{2} \end{cases}}\)

i pierwszy wiersz to szukana równość:

\(\displaystyle{ 8\cdot 31-13\cdot 19=1}\)

czyli:

\(\displaystyle{ 8\equiv 31^{-1}\pmod{19}\Rightarrow 8\cdot 31\equiv 248\equiv 13\cdot 19+1\equiv 1\pmod{19}\\
-13\equiv 19^{-1}\pmod{31}\Rightarrow -13\cdot 19\equiv -247\equiv -8\cdot 31+1\equiv 1\pmod{31}\\
-13\equiv 18\equiv 19^{-1}\pmod{31}\Rightarrow 18\cdot 19\equiv 342\equiv 11\cdot 31+1\equiv 1\pmod{31}}\)

[karl153]

Chwała Ci dobry człowieku, chylę czoła i bardzo dziękuje, taką pracę to można już pod tutorial podpisać doceniam twój wkład, jeżeli nie nadwyręży to twojej uprzejmości to mógł byś dopisać tylko dlaczego tu jest -1 przecież mamy +,-,- czyli ostatecznie powinno być +1 ? \(\displaystyle{ \fbox{1}\cdot 31+\fbox{0}\cdot 19 -\fbox{0}\cdot 31-\fbox{1}\cdot 19=\fbox{31}-\fbox{19}\\ \fbox{1}\cdot 31 +\fbox{-1}\cdot 19=\fbox{12}}\)

[octahedron]

\(\displaystyle{ 1\cdot 31+0\cdot 19-0\cdot 31-1\cdot 19=(1-0)\cdot 31+(0-1)\cdot 19=1\cdot 31+(-1)\cdot 19}\)

zresztą \(\displaystyle{ +}\) być nie może, bo \(\displaystyle{ 12=31-12}\), a nie \(\displaystyle{ 12=31+12}\)