Wyznaczyć element odwrotny do
\(\displaystyle{ 7}\) w ciele \(\displaystyle{ \mathcal{Z}_{17}}\).
Problem w tym, że na ćwiczeniach mieliśmy tylko jeden taki przykład i w ogóle nie mam pojęcia co się z czego wzięło. Było wyznaczyć element odwrotny do \(\displaystyle{ 13}\) w ciele \(\displaystyle{ \mathcal{Z}_{23}}\) i nasz kochany wykładowca napisał sobie:
\(\displaystyle{ 13x=1 \ mod 23 \\
1=3-2*1 \\
3-2*(10-3*3) \\
7*3-2*10 \\
7(13-10)-2*10 \\
7*13-9*10 \\
7*13-9(23-13) \\
16*13-9*23 \\
1=16*13-9*23 \ /mod 23 \\
1=16*13}\)
No więc nie wiem skąd się te liczby wzięły i nie widzę tu żadnej zasady, tak więc prosiłbym o wyjaśnienie. Mam jeszcze dwa takie zadania, ale jak zrozumiem to jedno, to już dam sobie radę.
Wyznacz element odwrotny
- Psiaczek
- Użytkownik
- Posty: 1502
- Rejestracja: 22 lis 2010, o 09:53
- Płeć: Mężczyzna
- Lokalizacja: Polska, Warmia, Olsztyn :)
- Podziękował: 1 raz
- Pomógł: 475 razy
Wyznacz element odwrotny
Znasz algorytm Euklidesa? Można tak:Kanodelo pisze:No dobra, ale co mi to daje? Bo na prawdę nic z tego nie rozumiem.pipol pisze:\(\displaystyle{ 7^{-1}=5}\)
\(\displaystyle{ 17=2 \cdot 7+3, 7=2 \cdot 3+1}\) i teraz od tyłu : \(\displaystyle{ 1=7-2 \cdot 3, 1=7-2(17-2 \cdot 7),1=5 \cdot 7-2 \cdot 17}\) i otrzymaliśmy przy 7 współczynnik 5 tak jak ci kolega podał.
-
- Użytkownik
- Posty: 1267
- Rejestracja: 1 kwie 2011, o 11:37
- Płeć: Mężczyzna
- Lokalizacja: Malbork
- Podziękował: 419 razy
- Pomógł: 114 razy
Wyznacz element odwrotny
Szczerze mówiąc, nie mam pojęcia co to jest algorytm euklidesa, ale zaraz to poszukam na wikipedii, bo wypadałoby skumać.
Ale w każdym razie dzięki za naprowadzenie.-- 4 kwi 2011, o 08:42 --\(\displaystyle{ 7x=1 mod 17}\)
stosuje rozszerzony algorytm euklidesa:
\(\displaystyle{ 17 \ 7 \ 2 \ resta \ 3 \\
7 \ 3 \ 2 \ reszta \ 1 \\
3 \ 1 \ 3 \ reszta 0}\)
\(\displaystyle{ 3=1*17−2*7 \\
1=1*7−2*3\\
0=1*3−3*1}\)
I właściwie co dalej, bo co tu jest w końcu rozwiązaniem?
Ale w każdym razie dzięki za naprowadzenie.-- 4 kwi 2011, o 08:42 --\(\displaystyle{ 7x=1 mod 17}\)
stosuje rozszerzony algorytm euklidesa:
\(\displaystyle{ 17 \ 7 \ 2 \ resta \ 3 \\
7 \ 3 \ 2 \ reszta \ 1 \\
3 \ 1 \ 3 \ reszta 0}\)
\(\displaystyle{ 3=1*17−2*7 \\
1=1*7−2*3\\
0=1*3−3*1}\)
I właściwie co dalej, bo co tu jest w końcu rozwiązaniem?