WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

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
Student universiteit - zaterdag 28 februari 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.

Vragen naar aanleiding van dit antwoord? Klik rechts..!
donderdag 4 maart 2004