logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Algebra, zadanie nr 3771

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

ania16177
postów: 49
2015-11-07 12:54:45

Proszę o obliczenie, oraz jesli można z wytłumaczeniem równania
$17x\equiv1\cdot mod3840$

Z góry dziękuję

Wiadomość była modyfikowana 2015-11-07 13:04:02 przez ania16177

tumor
postów: 8070
2015-11-08 23:47:13

a co znaczy ta kropeczka przed mod?

$NWD(17,3840)=1$, zatem ma rozwiązanie równanie
$17x+3840y=1$
i w praktyce szukamy właśnie tego rozwiązania.
Możemy do rozwiązania użyć rozszerzonego algorytmu Euklidesa.
Nagłówek opisuje, która kolumna dotyczy x, która y. Pierwsze dwa wiersze mówią tylko tyle, że jeśli x jest 1 a y 0, to suma jest 17, natomiast jeśli y=1 oraz x=0, to sumą jest 3840. Nieskomplikowane. Natomiast następne wiersze to odejmowanie. Odejmujemy od drugiego wiersza tyle razy pierwszy wiersz, ile razy 17 mieści się w 3840.
$\begin{matrix} & x&y \\
17 & 1 & 0\\
3840& 0& 1\\
15&-225&1
\end{matrix}$

Następnie odejmujemy od pierwszego wiersza wiersz trzeci
$\begin{matrix} & x&y \\
17 & 1 & 0\\
3840& 0& 1\\
15&-225&1\\
2&226&-1

\end{matrix}$
Następnie odejmujemy od trzeciego wiersza czwarty tyle razy, ile razy 2 się mieści w 15.
$\begin{matrix} & x&y \\
17 & 1 & 0\\
3840& 0& 1\\
15&-225&1\\
2&226&-1\\
1&-1807&8
\end{matrix}$
Ostatni wiersz mówi, że $-1807*17+8*3840=1$
to oznacza
$-1807*17 \equiv 1 mod (3840)$
czyli $x=-1807+k*3840$

Przy takim zapisie lewa kolumna zawsze stanowi sumę 17x+3840y, gdy x i y zmieniają się odpowiednio (jak to zapisujemy w kolumnach x i y).
Gdy odejmujemy wierszami tak, by lewa kolumna zbliżała się do NWD(17,3840), to kolumny x i y ostatecznie dają rozwiązanie równania. Jest to bardzo dobra metoda, do stosowania także w skomplikowanych pierścieniach.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt online: 62 drukuj