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