Równiania modularne

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
pow3r
Użytkownik
Użytkownik
Posty: 207
Rejestracja: 8 kwie 2018, o 20:38
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 42 razy

Równiania modularne

Post autor: pow3r »

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ą.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Równiania modularne

Post autor: Premislav »

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}\).
ODPOWIEDZ