Algebra, zadanie nr 3771
ostatnie wiadomości | regulamin | latex
| Autor | Zadanie / Rozwiązanie |
| ania16177 postów: 49 |  2015-11-07 12:54:45Proszę 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