WisFaq!

Het uitgebreide algoritme van Euclides

Hie kunnen we 11 x a = 1 (mod 27) oplossen? Wij hadden hier als antwoord uit: a =5, maar we moeten dit aantonen met behulp van het uitgebreide algoritme van Euclides. Hoe moet dat?

Marichelle
24-2-2003

Antwoord

In feite wil je de inverse bereken van vermenigvuligen met 11 (mod 27). De berekening m.b.v. het algoritme van Euclides:

Eerst de ggd van 11 en 27 berekenen

27 = 2 · 11 + 5 5 = 27 - 2 · 11
11 = 2 · 5 + 1 1 = 11 - 2 · 5

Nu terug rekenen

1 = 11 - 2 · 5
1 = 1 · 11 - 2 · (27 - 2 · 11)
1 = 5 · 11 - 2 · 27

de inverse van 11 (mod 27) is 5 (mod 27)
de inverse van 11 (mod 27) is 5

Zie ook Inverse van 301 (modulo 577) en Inverse van a modulo n berekenen

WvR
24-2-2003