WisFaq!

Inverse berekenen mbv algoritme van Euclides

Hallo,
Ik heb een opdracht die gaat over het algoritme van Euclides (heel handig algoritme overigens). Ik heb in deze opdracht bij onderdeel a laten zien dat 1 de ggd (grootst gemeenschappelijke deler) is van 35 en 26. Nu willen ze bij echter een stapje verder met de kennis. De vraag luidt:

Is 26(streep) een eenheid in /35, en zo ja, wat is de inverse van 26(streep)?

Ik weet alleen niet hoe ik moet in zien of deze stelling waar of niet waar is, en hoe ik dit vervolgens moet bewijzen.

Alvast bedankt,
Erik

Erik
28-2-2004

Antwoord

Algemeen geldt: a is dan en slechts dan een eenheid (inverteerbaar element) in /n als ggd(a,n)=1. Dat betekent namelijk dat gehele getallen x en y bestaan zodat xa+yn=1, dus xa=1 (mod n). De inverse van de restklasse van a, dat is de restklasse van x, vindt men dan met het algorithme van Euclides.
Als n=35 en a=26, dan levert Euclides 1=3.35-4.26, dus 4.26=-1 (mod 35), dus (-4).26=1 (mod 35), dus de inverse van de restklasse van 26 is de restklasse van -4, dus ook die van 31.
In dit voorbeeld kan het ook zonder Euclides, want 26=-9 (mod 35) en (-4)(-9)=36=1 (mod 35). Je kan ook de restklassen mod 35 allemaal proberen tot je de inverse gevonden hebt.

hr
4-3-2004