WisFaq!

Re: n^p = n (mod p)

Hartelijk bedankt, ik heb echter nog een kleine vraag.
Ik moest hierna afleiden dat

n^p-1 º 1 (mod p)

In het antwoordmodel deelt men beide zeiden door n en als verklaring word gegeven dat dit is toegestaan omdat n en p relatief priem zijn. Ik zie echter niet in wat dit er mee te doen heeft. Ik hoop dat jullie me kunnen helpen.

Bas

Bas de Vries
1-3-2007

Antwoord

Dat `delen' is wel erg kort door de bocht. Omdat ggd(n,p)=1 zorgt het algoritme van Euclides voor twee gehele getallen a en b zo dat 1=a·n+b·p, met ander woorden, zo dat a·n=1 (mod p). Vermenigvuldig in n<sup>p</sup>=n (mod p) links en rechts met a, dan krijg je de gevraagde gelijkheid. Met dat `delen' bedoelt men toch `vermenigvuldigen met de inverse a'.

kphart
1-3-2007