Euklidischer Algorithmus: 1 als Linearkombination aus 97 und 28 mit ganzzahligen Koeffizienten darstellen.

Question

Stellen Sie 1 als Linearkombination aus 97 und 28 mit ganzzahligen Koeffizienten dar.
Bestimmen Sie daraus das Inverse von 28 im Körper GF(97).

Answer 1

(1)  97 : 28 = 3 Rest 13
⇒ 13 = 97 - 3·28

(2)  28 : 13 = 2 Rest 2
⇒ 2 = 28 - 2·13 = 28 - 2·(97 - 3·28) = 7·28 - 2·97

(3)  13 : 2 = 6 Rest 1
⇒ 1 = 13 - 6·2 = (97 -3·28) - 6·(7·28 - 2·97) = 13·97 - 45·28.

Damit ist das Inverse von  28  modulo  97  gleich  -45, bzw. 52.