De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

Re: Re: Algebra, binaire operaties

 Dit is een reactie op vraag 23161 
Ik zou graag willen reageren op het eerste gedeelte. Ik begrijp dat je op zoek moet gaan naar a en b, zodat ab=17k+1, maar bestaat er ook oplossingsmethode voor?
Want de multiplicatieve inverse van 21 in Z 900, 55 in Z89 en 32 in Z 81 kun je niet zo maar een, twe drie vinden...althans het lukt mij niet. Als het getal geen m.i. heeft, kun je dat dan ook zien?
B.v.d.
Iris

iris
Student hbo - maandag 13 maart 2006

Antwoord

Deze stelling komt dan handig van pas: ax+by=1 heeft een gehele oplossing (x,y) als a en b onderling ondeelbaar zijn. Hoe bepaal je x en y? Wel, dat gaat met het Euclidisch algoritme: onderweg bereken je dan de ggd van a en b, dus dat moet dan wel op 1 uitkomen als je een invers wil. In je eerste voorbeeld is 3 een gemeenschappelijke deler van 21 en 900, dus heeft 21 geen invers in Z900. Dat is ook logisch: a21-900k is altijd een drievoud, dus kan nooit 1 zijn.

Laten we eens naar het laatste voorbeeld kijken: we hebben de getallen 81 en 32.
81 = 232 + 17 dus 32 en 17
32 = 117 + 15 dus 17 en 15
17 = 115 + 2 dus 15 en 2
15 = 72 + 1 dus 2 en 1. Dit laatste getal (1) is de ggd van 81 en 32.

Nu gaan we proberen de 1 te schrijven als combinatie van 32 en 81. De laatste regel hierboven geeft 1 als combinatie van 2 en 15. Die 2 kunnen we met de voorlaatste regel dan weer schrijven als combinatie van 15 en 17, die 15 kunnen we schrijven als combinatie van 17 en 32 met behulp van de regel daarboven, etc. Zo dus:

1 = 15 - 72 (laatste regel van daarnet)
1 = 15 - 7(17-15) = 815 - 717 (voorlaatste regel)
1 = 8(32-17) - 717 = (-15)17 + 832
1 = (-15)(81 - 232) + 832 = 3832 - 1581

Dus 3832 = 1 + 1581, of nog 3832 1 (mod 81), en we hebben dat 38 het invers is van 32 in Z81.

Christophe
Vragen naar aanleiding van dit antwoord? Klik rechts..!
dinsdag 14 maart 2006



klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2021 WisFaq - versie 3