Modulaariaritmetiikan käänteisluku

Modulaariaritmetiikan käänteisluku on modulaari- eli jakojäännösaritmetiikan keskeisiä käsitteitä.

Kokonaisluvut  ja  ovat toistensa käänteislukuja modulo ,
missä  on nollasta eroava kokonaisluku, jos

Modulaariaritmetiikan käänteislukuja voidaan käyttää mm. kongruenssiyhtälöitä ratkaistaessa.

Kongruenssista  seuraa, että 
. Toisin sanoen luvut 
 ja  (samoin kuin luvut  ja ) ovat keskenään jaottomia.

Tämä on välttämätön ja riittävä ehto käänteisluvun olemassaololle.

Modulaariaritmetiikan käänteislukuja voidaan laskea mm. käyttämällä Eulerin lausetta, Fermat'n pientä lausetta tai laajennettua Eukleideen algoritmia.

Laajennettu Eukleideen algoritmi antaa modulaariaritmetiikan käänteislukujen laskemiseen yleispätevän ja tehokkaan laskumenetelmän.

Laskeminen Fermat'n pienen lauseen avulla

Jos  on alkuluku, merk. , niin

ts.

Luku  on siis eräs luvun  käänteisluku modulo .

Luvun  pienin ei-negatiivinen jakojäännös modulo  voidaan laskea tehokkaasti
modulaariaritmetiikan potenssiinkorotusalgoritmia käyttäen.

Menetelmän rajoituksena on se, että moduulin tulee olla alkuluku.

Laskeminen Eulerin lauseen avulla

Jos , niin Eulerin lauseen mukaan

ts.

Luku  on siis eräs luvun  käänteisluku modulo .

Luvun  pienin ei-negatiivinen jakojäännös modulo  voidaan laskea tehokkaasti
modulaariaritmetiikan potenssiinkorotusalgoritmia käyttäen.

Menetelmän rajoituksena on se, että Eulerin funktion  arvon laskemiseksi luvun 
alkutekijöihin jaon pitää yleensä olla tunnettu.

Laskeminen laajennetun Eukleideen algoritmin avulla

Olkoot  ja  kokonaislukuja,  ja
. Luvun  käänteisluku modulo , merk.
 saadaan tällöin rekursiivisesti seuraavasti:

1. Jos , niin 

2. Muulloin

missä  on funktio, joka antaa luvun  pienimmän ei-negatiivisen jakojäännöksen luvulla
 jaettaessa.

Esimerkiksi Mathematica-ohjelmistossa modulaariaritmetiikan käänteisluvun laskeva funktio 
voitaisiin tätä rekursiota käyttäen määrittää yhdellä rivillä:

Mathematica-ohjelmistosta löytyy tähän tarkoitukseen kuitenkin myös valmiiksi ohjelmoitu funktio.

Lukuteoria