Odwrotność modularna z twierdzenia Fermata

Dodawanie, odejmowanie i mnożenie zachowują się poprawnie modulo, ale zwykłe dzielenie już nie. Nie można po prostu podzielić wartości i wziąć reszty. ⚠️

Rozwiązaniem jest odwrotność modularna: dzielenie przez x zastępuje się mnożeniem przez odwrotność x. Zatem a / b modulo m zamienia się na a pomnożone przez odwrotność b.

Odwrotność liczby x to liczba, która po pomnożeniu przez x daje 1 modulo. Pełni rolę 1/x w zwykłej arytmetyce.

Odwrotność istnieje tylko wtedy, gdy x nie ma z m żadnego wspólnego dzielnika większego od 1. Użycie modułu pierwszego, takiego jak 1e9+7, gwarantuje, że każda niezerowa wartość x ma odwrotność.

Małe twierdzenie Fermata mówi, że dla liczby pierwszej p liczba x do potęgi p minus 1 jest przystająca do 1, o ile x nie jest wielokrotnością p.

Po wydzieleniu jednego czynnika x pozostała część musi być jego odwrotnością. Zatem odwrotność x to x podniesione do potęgi p minus 2, a następnie obliczone modulo p.

Ten wykładnik jest ogromny, więc użyj szybkiego potęgowania z poprzedniej lekcji. W Pythonie jedno wywołanie pow wykona całą pracę.

Aby obliczyć a podzielone przez b modulo, pomnóż a przez odwrotność b. Otrzymana reszta jest dokładnie prawdziwym ilorazem modulo p.

Odwrotność 0 nie istnieje, ponieważ żadna liczba pomnożona przez zero nie daje jedynki. Należy zabezpieczyć się przed dzieleniem przez wartość, która modulo daje zero.

Każda odwrotność wyznaczana twierdzeniem Fermata wymaga jednego szybkiego potęgowania, więc jej koszt czasowy wynosi O(log p). To niewiele przy kilku dzieleniach, ale koszt rośnie przy milionach operacji.

Gdy potrzebnych jest wiele odwrotności, można obliczyć je w sprytnym liniowym przejściu zamiast wywoływać pow dla każdego elementu. Ta technika przyda się w następnym temacie, dotyczącym nCr.

Jaka potęga daje odwrotność modularną dla modułu pierwszego?

Można teraz dzielić modulo liczby pierwszej, mnożąc przez odwrotność modularną, wyznaczaną jako x do potęgi p minus 2 za pomocą pow. Nie wolno tylko odwracać zera. ✅