Euklidischer Algorithmus

Euklidischer Algorithmus:

ggT( , )


Bestimme den ggT( 7 ; 4 ) über den Euklidischen Algorithmus:

7 = 1 · 4 + 3

4 = 1 · 3 + 1

3 = 3 · 1 + 0



Die Zahlen 7 und 4 sind teilerfremd, also ggT( 7 ; 4 ) = 1.

Erweiterter Euklidischer Algorithmus:

1 = 1 · 4 - 1 · 3

1 = -1 · 7 + 2 · 4

Inverses Element der modularen Multiplikation:

Das inverse Element (Kehrwert) von 4 mod ( 7 ) lautet: 2

Probe: 4 · 2 mod ( 7 ) = 8 mod ( 7 ) = 1 mod ( 7 )