obliczenia z modulo

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
KasienkaG
Użytkownik
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

Post autor: KasienkaG »

Jak zabrać się do obliczenia zadania:
\(\displaystyle{ 10^{-1} \mod 111}\) ?
Mógłby mi ktoś udzielić jakiś wskazówek?
octahedron
Użytkownik
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

Post autor: octahedron »

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}\\}\)
KasienkaG
Użytkownik
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

Post autor: KasienkaG »

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?
octahedron
Użytkownik
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

Post autor: octahedron »

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}}\)
KasienkaG
Użytkownik
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

Post autor: KasienkaG »

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?
octahedron
Użytkownik
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

Post autor: octahedron »

octahedron pisze:Szukamy takich liczb \(\displaystyle{ x,y}\), że:
\(\displaystyle{ 10x+111y=1}\)
no i znaleźliśmy:

\(\displaystyle{ -11\cdot 10+1\cdot 111=1}\)

czyli

\(\displaystyle{ x=-11}\)

zatem

\(\displaystyle{ -11\equiv 10^{-1}\pmod{111}}\)
ODPOWIEDZ