Modulo - co oznacza taki zapis

[Dragon339]

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?

[JakimPL]

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

[Dragon339]

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

[JakimPL]

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