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