inverse 8 mod 11

[Dotcom]

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

[Tampert]

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?

[Dotcom]

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).]

[Dotcom]

'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.

[Alberto]

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

[Alberto]

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'.

[Dotcom]

Alberto schreef:
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?

[Alberto]

2 deelt 11?

11 = 1*11 + 0*8
8 = 0*11 + 1*8 (deze 1 keer van de vorige af
3 = 1*11 - 1*8 (deze 2 keer van de vorige af
2 = -2*11 + 3*8 (deze 1 keer van de vorige af
1 = 3*11 - 4*8

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

[Alberto]

Even vergeten dat een : gevolgd door een ) een oplevert.