Równiania modularne
-
- Użytkownik
- Posty: 207
- Rejestracja: 8 kwie 2018, o 20:38
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 42 razy
Równiania modularne
Wyznacz, o ile istnieje, \(\displaystyle{ 73 ^{-1}\pmod{95}.}\)
Ostatnio zmieniony 6 maja 2018, o 17:24 przez SlotaWoj, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości: \pmod. Zdanie zaczynamy dużą literą i kończymy kropką.
Powód: Poprawa wiadomości: \pmod. Zdanie zaczynamy dużą literą i kończymy kropką.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Równiania modularne
Istnieje, ponieważ \(\displaystyle{ \NWD(73,95)=1}\).
Można to znaleźć z wykorzystaniem rozszerzonego algorytmu Euklidesa.
\(\displaystyle{ 95=1\cdot 73+22\\ 73=3\cdot 22+7\\22-3\cdot 7+1}\)
czyli
\(\displaystyle{ 1=22-3\cdot 7=95-73-3(73-3\cdot 22)=\\=95-73-3\cdot 73+9\cdot(95-73)=\\=10\cdot 95-13\cdot 73}\)
czyli
\(\displaystyle{ -13\cdot 73=-10\cdot 95+1\equiv 1\pmod{95}}\)
a \(\displaystyle{ -13\equiv 82\pmod{95}}\),
czyli \(\displaystyle{ 73^{-1}\pmod{95}=82}\).
Można to znaleźć z wykorzystaniem rozszerzonego algorytmu Euklidesa.
\(\displaystyle{ 95=1\cdot 73+22\\ 73=3\cdot 22+7\\22-3\cdot 7+1}\)
czyli
\(\displaystyle{ 1=22-3\cdot 7=95-73-3(73-3\cdot 22)=\\=95-73-3\cdot 73+9\cdot(95-73)=\\=10\cdot 95-13\cdot 73}\)
czyli
\(\displaystyle{ -13\cdot 73=-10\cdot 95+1\equiv 1\pmod{95}}\)
a \(\displaystyle{ -13\equiv 82\pmod{95}}\),
czyli \(\displaystyle{ 73^{-1}\pmod{95}=82}\).