Analiza matematyczna, zadanie nr 3529
ostatnie wiadomości | regulamin | latex
Autor | Zadanie / Rozwiązanie |
mistergol postów: 21 | 2015-06-20 18:12:42 Obliczyć x takie, że x = 5 mod 89, x = 7 mod 61 Proszę przede wszystkim o wyjaśnienie rozwiązania :) Pozdrawiam. |
tumor postów: 8070 | 2015-06-20 20:51:32 $\left\{\begin{matrix} x\equiv 5 mod 89 \\ x \equiv 7 mod 61 \end{matrix}\right. $ Przy tym 61 i 89 są pierwsze Równanie $x\equiv 5 mod 89$ mówi, że x daje resztę 5 przy dzieleniu przez 89, czyli $x=89k+5$ dla pewnego k. Możemy zatem podstawić do drugiego $89k+5\equiv 7 mod 61$ przenosi się na drugą stronę jak w równaniach, tylko działania wykonujemy teraz mod 61 $ 28k \equiv 2 mod 61$ chcielibyśmy mieć po lewej k, a nie 28k. Normalnie byśmy dzielili przez 28, tu postąpimy podobnie. Dzielenie przez 28 to mnożenie przez element odwrotny do 28. Elementu odwrotnego szuka się z algorytmu Euklidesa $28a+61b=1$ (zauważmy, że liczba a będzie spełniać ten warunek, że $a*28 \equiv 1 mod 61$, czyli a będzie odwrotnością 28) Po rozwiązaniu z alg. Euklidesa mamy a=24 (oraz b=-11), bo $24*28-11*61=1$ Zatem równanie $ 28k \equiv 2 mod 61$ mnożymy obustronnie przez $24 (mod 61)$, stąd $ k \equiv 48 mod 61$ czyli $k=61n+48$, wobec tego $x=89k+5=89(61n+48)+5=89*61n+89*48+5= 89*61n+4277$ dla n całkowitego. |
strony: 1 |
Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj