We bekijken de verzameling getallen $$A = {1, 2, ..., p-1}$$ met p een priemgetal. Het kan aangetoond worden dat er voor elk getal $$a \in A$$ een inverse $$b \in A$$ kan gevonden worden, zodat
$$(a b) \mod p = 1$$
(m.a.w. $$b$$ is het invers element van $$a$$ voor de vermenigvuldiging modulo $$p$$).

Om dit getal $$b$$ vinden zouden we dus makkelijk alle elementen van $$A$$ kunnen proberen. Gelukkig kunnen we om $$b$$ rechtstreeks te bepalen, beroep doen op de kleine stelling van Fermat, namelijk:
$$a^p \mod p = a \mod p$$
Veel resultaten uit cryptografie zijn gebaseerd op deze beroemde stelling.

Schrijf een programma dat twee gehele getallen inleest, namelijk

• het priemgetal $$p$$ (je mag veronderstellen dat de gebruiker inderdaad een priemgetal opgeeft)
• een natuurlijk getal $$a$$ met $$0 < a < p$$, waarvoor het inverse moet gezocht worden

Het resultaat is het gezochte inverse element $$b$$.

TIP: er geldt tevens voor $$x, y \in A$$ dat
$$xy \mod p = (x\mod p)(y\mod p)\mod p$$

Voorbeeld

Invoer:

7
3

Uitvoer:

5