Rozwiązać w systemie reszt Z107 równanie 43x=90.
Mam pytanie czy jest na to jakiś formalny sposób bo ja zrobiłam to tak x=90*43 do -1=90*5=22 Tą 5 to wykombinowałam
równanie
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
octahedron
- Expert
- Posty: 6762
- Rejestracja: 19 mar 2011, 00:22
- Otrzymane podziękowania: 3034 razy
- Płeć:
Re: równanie
\(43x\equiv 90\pmod{107}\)
Szukamy odwrotności \(43^{-1}\), czyli takiej liczby \(y\), że \(43y\equiv 1\pmod{107}\). Stosujemy rozszerzony algorytm Euklidesa:
\(\begin{array}{r|r|r}1&0&107\\\hline 0&1&43\end{array}\ w_1-2w_2
\begin{array}{r|r|r}1&-2&21\\\hline 0&1&43\end{array}\ w_2-2w_1
\begin{array}{r|r|r}1&-2&21\\\hline -2&5&1\end{array}\ w_2-2w_1\)
i z ostatniego wiersza mamy \(43^{-1}\equiv 5\pmod{107}\), więc:
\(5\cdot 43x\equiv 5\cdot 90\pmod{107}
215x\equiv 450\pmod{107}
x\equiv 22\pmod{107}
x=22+107k,\ k\in C\)
Szukamy odwrotności \(43^{-1}\), czyli takiej liczby \(y\), że \(43y\equiv 1\pmod{107}\). Stosujemy rozszerzony algorytm Euklidesa:
\(\begin{array}{r|r|r}1&0&107\\\hline 0&1&43\end{array}\ w_1-2w_2
\begin{array}{r|r|r}1&-2&21\\\hline 0&1&43\end{array}\ w_2-2w_1
\begin{array}{r|r|r}1&-2&21\\\hline -2&5&1\end{array}\ w_2-2w_1\)
i z ostatniego wiersza mamy \(43^{-1}\equiv 5\pmod{107}\), więc:
\(5\cdot 43x\equiv 5\cdot 90\pmod{107}
215x\equiv 450\pmod{107}
x\equiv 22\pmod{107}
x=22+107k,\ k\in C\)