Multiplikativni inverz

Motivacija

Računanje je čas posla, ali što je sa i kada je to uopće definirano?

Slično kao i u aritmetici s realnim brojevima, se definira kao inverzna operacija množenju, odnosno je jednak broju takvom da . Analogno tome, definiramo kao sve brojeve takve da . Može se pokazati da je jednoznačno definiran ako i samo ako su i relativno prosti.

Naoružani novim znanjem, ne treba dugo da pomislite vrijedi li ? E pa vrijedi (pogledati sekciju "Za one koji žele znati više")! Dakle, dovoljno je za svaki broj znati iznos "multilikativnog inverza" da bismo izračunali rezultat. Donja dva odjeljka objašnjavaju kako!

Računanje binarnim potenciranjem (čas posla)

Još od malih nogu (ili barem od predavanja iz teorije brojeva) znamo za svaki prosti broj i cijeli vrijedi da

Drugim riječima, multilikativni inverz broja računamo pomoću brzog potenciranja. Laganica.

Računanje svih inverzova (čas časa posla)

Da skratimo priču:

int M = 10007; // da, prost je
int inverz[M];
inverz[1] = 1;
for (int x = 2; x < M; ++x)
  inverz[x] = (M - M/x) * inverz[M%x] % M;

Čudesno, zar ne?! Ali, pitate zašto?

Recimo da smo izračunali sve inverze . Znamo po "teoremu o ostacima" da postoje i takvi da:

Pomnožimo sve s (kojeg smo već izračunali), te imamo:

Drugim riječima, je modularni inverz broja . Podsjetimo se samo kako izračunati i :

i s time smo gotovi!

Za one koji žele znati više

Andrej Dujella: Uvod u teoriju brojeva - skripta (predavanje s PMF-a): http://web.math.pmf.unizg.hr/~duje/utb/utblink.pdf

© 2014. Goran Žužić Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License