Matematyka.pl

Witam, pytanie może wydawać się głupie, ale na zajęciach liczę ze schematu ze zadania i tak szczerze powiedziawszy nie mam pojęcia jakiej liczby szuka się przy takim zapisie
\(\displaystyle{ 217 ^{-1}\pmod{491}}\)

Co prawda wolfram wywala taki sam wynik jaki mi wyszedł, tylko właśnie, co takiego tutaj jest obliczane? Podejrzewam że nie reszta z dzielenia.

\(\displaystyle{ 106=50\pmod{56}}\)

Powyższy zapis oznacza podzielność przez \(\displaystyle{ 56}\) różnicy tych dwóch liczb?

Co do drugiego, tak. Te dwie liczby mają tę samą resztę z dzielenia przez \(\displaystyle{ 56}\).

Co do pierwszego, szuka się takiej liczby \(\displaystyle{ n}\), że \(\displaystyle{ n \cdot 217 = 1\pmod{491}}\), czyli w pewnym sensie liczby odwrotnej do \(\displaystyle{ 217}\) modulo \(\displaystyle{ 491}\). Taka liczba istnieje wtedy i tylko wtedy, gdy \(\displaystyle{ \NWD(217,491)=1}\). Jeżeli istnieje, jest jedyna (modulo \(\displaystyle{ 491}\)).

W tym przypadku \(\displaystyle{ n=267}\), bo \(\displaystyle{ 267\cdot 217 = 1 \pmod{491}}\); innymi słowy \(\displaystyle{ 267 = 217^{-1}\pmod{491}}\).

JakimPL pisze:Co do drugiego, tak. Te dwie liczby mają tę samą resztę z dzielenia przez \(\displaystyle{ 56}\).

Co do pierwszego, szuka się takiej liczby \(\displaystyle{ n}\), że \(\displaystyle{ n \cdot 217 = 1\pmod{491}}\), czyli w pewnym sensie liczby odwrotnej do \(\displaystyle{ 217}\) modulo \(\displaystyle{ 491}\). Taka liczba istnieje wtedy i tylko wtedy, gdy \(\displaystyle{ \NWD(217,491)=1}\). Jeżeli istnieje, jest jedyna (modulo \(\displaystyle{ 491}\)).

W tym przypadku \(\displaystyle{ n=267}\), bo \(\displaystyle{ 267\cdot 217 = 1 \pmod{491}}\); innymi słowy \(\displaystyle{ 267 = 217^{-1}\pmod{491}}\).

W sumie to dużo się rozjaśniło bo teraz rozumiem co tu się dzieje. ale mam jedną wątpliwość, czy n musi być liczbą całkowitą dodatnią? Teraz robiąc ten sam przykład który dałem u góry mając \(\displaystyle{ NWD(217,491)}\) w postaci kombinacji liniowej, zauważyłem że wychodzi taka oto równość
\(\displaystyle{ 1=99*491-224*217}\)
Teraz możemy przerzucić na odpowiednią stronę i otrzymujemy
\(\displaystyle{ -99*491=-224*217-1}\)
A z tego wynika że równość
\(\displaystyle{ n*217=1 \pmod{491}}\)
jest spełniona dla n równego \(\displaystyle{ -224}\)

Co prawda wszystko się zgadza, ale czy tak również jest poprawnie? Wolfram pokazywał wartość 267 właśnie, wiem jak do niej dojść, aczkolwiek wartość którą podałem również spełnia równanie

Twój wynik daje tę samą resztę z dzielenia przez \(\displaystyle{ 491}\), \(\displaystyle{ -224 \equiv 217\pmod{419}}\). W arytmetyce modularnej utożsamiamy liczby o tej samej reszcie z dzielenia.

Standardowo przyjmujemy, że ze wszystkich liczb modulo \(\displaystyle{ m}\) wybieramy tę z przedziału \(\displaystyle{ [0,m-1]}\), czyli \(\displaystyle{ n\in\{1,2,\ldots,m-1\}}\).