inverse 8 mod 11
 

ik heb een antwoordblad daar staat dat de inverse van 8 mod 11 = 7 mbv. van euclides.
hoe heeft hij dit precies berekend?

Ik doe een gokje
Misschien hebben ze het hier over de vermenigvuldiging modulo 11.

rekenen modulo 11 betekent dat je bij 11 weer opnieuw begint. Je telt dus eigenlijk als volgt:
... 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 ...

ofwel k mod 11 = k - x*11

Dan moet voor de inverse (h) van 8 gelden: 8 * h mod 11 = e. e is de eenheid, het getal wat bij vermenigvuldiging niets verandert aan het getal waar je het mee vermenigvujldigt. Bij vermenigvuldiging is de eenheid altijd 1 (immers: 1 * h = h). Proberen met bepaalde waarden van de mogelijke inverse geeft:
1*8 = 8
2*8 = 16 (=5, door de mod 11)
3*8 = 24 (=2)
4*8 = 32 (=10)
5*8 = 40 (=7)
6*8 = 48 (=4)
7*8 = 56 (=1)
is dit een antwoord op je vraag?

Ja!!!!
Thanx!

De complete vraag was trouwens:

3 Bepaal de eventuele oplossingsklasse van

8x = 3 mod 11
3x = 5 mod 7
x = 1 mod 2

Antwoord:

1) ggd(11,8)=ggd(7,3)=ggd(2,1) =1
2) en 2,7,11 ook onderling priem er is dus oplossing
3) inverse 8 mod 11 =7 (bv met euclides)
56x=21 mod 11 --- x=-1 mod 11
inverse van 3 mod 7 is 5
x=4 mod 7

stelsel is nu : x=-1 mod 11, x=4 mod 7 en x= 1 mod 2

oplossing congruent mod 154 wordt
(-1)(14)(z1)+(4)(22)(z2)+(1)(77)(z3)
z1 is de inverse van 14 mod 11 en dat is 4
z2 is de inverse van 22 mod 7 en dat is 1
z3 is de inverse van 77 mod 2 en dat is 1

antwoord is 109 mod 154



[Dit bericht is aangepast door Dotcom (07-11-2001).]

't Kon nog simpeler:

inv 8 mod 11
zoek een product dat bij 11 1 minder geeft dan bij 8
dat is 7, want 7*8=56 en 5*11=55.

Hmmm, het ziet er in mijn ogen een beetje uit als het construeren van een afbeelding voor de Chinese Reststelling.

Ik ken trouwens wel een beter algoritme om de inverse te vinden dan gewoon ze allemaal bij langs te gaan.

Noem x de inverse van 8 mod 11 in de groep (Z/11Z)*.
Dan 8x is congruent 1 mod 11. Oftewel:
8x + 11k = 1 voor een zekere k. Voer nu het Euclidisch algoritme uit om de ggd van 11 en 8 te bepalen en 'vul vervolgens alle stappen terug in'.

inv 8 mod 11
8x�ß1 mod 11
euclidisch algoritme:
ggd(11,8)
11=1*8+3
8=2*3+1
3=1+2
2=2+0
ggd=2

en nu?

2 deelt 11?

11 = 1*11 + 0*8
8 = 0*11 + 1*8 (deze 1 keer van de vorige af http://forum.scholieren.com/smile.gif
3 = 1*11 - 1*8 (deze 2 keer van de vorige af http://forum.scholieren.com/smile.gif
2 = -2*11 + 3*8 (deze 1 keer van de vorige af http://forum.scholieren.com/smile.gif
1 = 3*11 - 4*8

Blijkbaar = (-4)*8 congruent 1 mod 11. Het antwoord is dus -4 mod 11 = 7.

Even vergeten dat een : gevolgd door een ) een http://forum.scholieren.com/smile.gif oplevert.