Teoria liczb, zadanie nr 2447
ostatnie wiadomości | regulamin | latex
| Autor | Zadanie / Rozwiązanie |
| van1403 postów: 3 |  2014-06-13 18:15:41Rozwiąż kongruencje liniową 1)15x=7(mod 24) 2)15x=10(mod 25) Prosiłbym o krok po kroku jak to się robi , z góry dziękuje |
| tumor postów: 8070 | 2014-06-23 19:46:02 1) zauważamy, że $NWD(15,24)$ nie jest dzielnikiem liczby $7$, kongruencja rozwiązań nie ma. Widzimy przecież, że $15x$ jest liczbą podzielną przez $3$, dla całkowitego $x$ reszta z dzielenia $15x$ przez $24$ też musi być podzielna przez $3$ (przez $NWD(15,24)=3$). |
| tumor postów: 8070 | 2014-06-23 19:55:00 2) tu widzimy na oko rozwiązanie $x_0=-1$, pozostałe rozwiązania opierają się na tożsamości $15*5=0 (mod 25)$, zatem $x=5k-1$, gdzie $k$ jest liczbą całkowitą. --- W ogólnym przypadku metoda krok po kroku polega na użyciu algorytmu Euklidesa. Szukamy x spełniającego równanie $15x+25y=10$, gdzie $y$ jest dowolną liczbą całkowitą. W praktyce możemy więc wyznaczyć jako rozwiązanie parę $(x,y)$, a $y$ zignorować. ;) Rozszerzony algorytm Euklidesa pozwala znaleźć liczby $a,b$ dla których $15a+25b=NWD(15,25)=5$ Otrzymujemy $15*2+25(-1)=5$ Mnożąc obustronnie przez $2$ dostajemy $15*4+25(-2)=16$ Rozwiązanie $(x_0,y_0)=(4,-2)$ nie jest jedyne, ale wobec tożsamości $15*5=25*3$ mamy rozwiązanie ogólne $(x,y)=(4+5t,-2-3t)$, gdzie $t\in Z$. Rozwiązanie $4+5t$ oczywiście pokrywa się z $-1+5k$ uzyskanym wcześniej. |
| strony: 1 | |
Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj