Berechnen von multiplikativem Inversen mittels Euklid

Question

1. Wie kann ich den Euklidischen Algorythmus dazu verwenden, ein multiplikatives inverses zu berechnen.

Beispielsweise von 5 mod 17.

2. Worin unterscheiden sich der ursprüngliche und der erweiterte Algorythmus?

Answer 1

Zu 1. 17=3*5+2

            5=2*2+1

            2=2*1+0

Also ist der ggT von 17 und 5 die 1.

2. Mit dem erweiterten eukl.Alg. ergibt sich die Darstellung: 1=5-2*2=5-2*(17-3*5)=-2*17+7*5

Damit ergibt sich die Inverse modulo 17: Die Gleichung wird zu 1=7*5 mod 17

und damit ist 7 das Inverse zu 5.

 

P.S. Ein Algorithmus hat nicht mit dem musikalischen Rhythmus nichts gemein

Comments

Wenn ichs richtig verstehe brauche ich den erweiterten Alg. um die Inverse zu bestimmen?

zu 2.

aus dem letzten Schritt ergibt sich -2*17+7*5, wobei 17mod17 = 0 und deshalb bleibt 1=7*5?

---

Bitte.

Ja und ja.