Jak zabrać się do obliczenia zadania:
\(\displaystyle{ 10^{-1} \mod 111}\) ?
Mógłby mi ktoś udzielić jakiś wskazówek?
obliczenia z modulo
-
- Użytkownik
- Posty: 3568
- Rejestracja: 7 mar 2011, o 22:16
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 910 razy
obliczenia z modulo
Rozszerzony algorytm Euklidesa:
\(\displaystyle{ \begin{array}{c|c||c}1&0&111\\\hline 0&1&10\end{array}\quad w_1-11w_2\\
\begin{array}{c|c||c}1&-11&1\\\hline 0&1&10\end{array}\Rightarrow 111-11\cdot 10=1 \Rightarrow -11\equiv 10^{-1}\pmod{111}\\}\)
\(\displaystyle{ \begin{array}{c|c||c}1&0&111\\\hline 0&1&10\end{array}\quad w_1-11w_2\\
\begin{array}{c|c||c}1&-11&1\\\hline 0&1&10\end{array}\Rightarrow 111-11\cdot 10=1 \Rightarrow -11\equiv 10^{-1}\pmod{111}\\}\)
-
- Użytkownik
- Posty: 385
- Rejestracja: 2 lut 2011, o 14:01
- Płeć: Kobieta
- Lokalizacja: Www
- Podziękował: 15 razy
- Pomógł: 3 razy
obliczenia z modulo
Hmm, mieliśmy na wykładzie algorytm Euklidesa, ale rozszerzonego już nie, a co za tym idzie nie bardzo rozumiem powyższy zapis... Mogłabym prosić jeszcze o jakiś komentarz?
-
- Użytkownik
- Posty: 3568
- Rejestracja: 7 mar 2011, o 22:16
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 910 razy
obliczenia z modulo
Szukamy takich liczb \(\displaystyle{ x,y}\), że:
\(\displaystyle{ 10x+111y=1}\)
wtedy
\(\displaystyle{ 10x+111y\equiv 1\pmod{111}\\
10x\equiv 1\pmod{111}}\)
czyli
\(\displaystyle{ x=10^{-1}\pmod{111}}\)
a ten zapis
\(\displaystyle{ \begin{array}{c|c||c}1&0&111\\\hline 0&1&10\end{array}}\)
to po prostu układ równań:
\(\displaystyle{ \begin{cases}{\red 1}\cdot 111+{\red 0}\cdot 10={\red 111}\\{\red 0}\cdot 111+{\red 1}\cdot 10={\red 10}\end{cases}}\)
\(\displaystyle{ 10x+111y=1}\)
wtedy
\(\displaystyle{ 10x+111y\equiv 1\pmod{111}\\
10x\equiv 1\pmod{111}}\)
czyli
\(\displaystyle{ x=10^{-1}\pmod{111}}\)
a ten zapis
\(\displaystyle{ \begin{array}{c|c||c}1&0&111\\\hline 0&1&10\end{array}}\)
to po prostu układ równań:
\(\displaystyle{ \begin{cases}{\red 1}\cdot 111+{\red 0}\cdot 10={\red 111}\\{\red 0}\cdot 111+{\red 1}\cdot 10={\red 10}\end{cases}}\)
-
- Użytkownik
- Posty: 385
- Rejestracja: 2 lut 2011, o 14:01
- Płeć: Kobieta
- Lokalizacja: Www
- Podziękował: 15 razy
- Pomógł: 3 razy
obliczenia z modulo
chyba nie bardzo rozumiem. Mamy obliczyć \(\displaystyle{ 10^{-1}mod 111}\) a w Twoim rozwiązaniu dochodzimy do tego, że \(\displaystyle{ x=10^{-1}mod111}\). Co więc jest rozwiązaniem zadania?
-
- Użytkownik
- Posty: 3568
- Rejestracja: 7 mar 2011, o 22:16
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 910 razy
obliczenia z modulo
no i znaleźliśmy:octahedron pisze:Szukamy takich liczb \(\displaystyle{ x,y}\), że:
\(\displaystyle{ 10x+111y=1}\)
\(\displaystyle{ -11\cdot 10+1\cdot 111=1}\)
czyli
\(\displaystyle{ x=-11}\)
zatem
\(\displaystyle{ -11\equiv 10^{-1}\pmod{111}}\)