0 Daumen
961 Aufrufe

Berechnen Sie mit dem Euklidischen Algorithmus ggT(113,17). Prüfen Sie, ob 17 in Z113 eine Inverse besitzt und wenn ja, berechnen Sie 17^(-1) in Z113 (Text!).

Euklidische Algo

 

Die Aufgabe kann ich leider nicht lösen, da ich in Mathe euklidschen Algorithmus nie hatte.

Danke im Voraus

Gefragt von

2 Antworten

0 Daumen
 
Beste Antwort

Du kannst dich aber fortbilden

http://de.wikipedia.org/wiki/Euklidischer_Algorithmus

ggT(113, 17)

113 - 6*17 = 11
17 - 11 = 6
11 - 6 = 5
6 - 5 = 1
5 - 5*1 = 0

ggT(113, 17) = 1

 

Multiplikativ Inverses

1 = 6 - 5

1 = 6 - (11 - 6) = - 11 + 2*6

1 = 6 - (11 - 6) = - 11 + 2*(17 - 11)

1 = - 3*11 + 2*17

1 = - 3*(113 - 6*17) + 2*17

1 = - 3*113 + 20*17

20 * 17 = 3*113 + 1

Also ist 17^-1 = 20

Beantwortet von 262 k
0 Daumen

(1)  113 : 17 = 6 Rest 11
⇒ 11 = 113 - 6·17

(2)  17 : 11 = 1 Rest 6
⇒ 6 = 17 - 1·11 = 17 - 1·(113 - 6·17) = -1·113 + 7·17

(3)  11 : 6 = 1 Rest 5
⇒ 5 = 11 - 1·6 = (113 - 6·17) - 1·(-1·113 + 7·17) = 2·113 - 13·17

(4)  6 : 5 = 1 Rest 1
⇒ 1 = 6 - 1·5 = (-1·113 + 7·17) - 1·(2·113 - 13·17) = -3·113 + 20·17.

Daraus folgt  ggT(113,17) = 1  und  17-1 = 20  in  ℤ113.

Beantwortet von
DANKEEEEEEEEEEEEEEEEEE :)

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...