Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » euklidischer Algorithmus rückwärts

euklidischer Algorithmus rückwärts

Universität / Fachhochschule

Tags: Euklidischer Algorithmus, modulo, rückwärts

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
RoXoR

RoXoR aktiv_icon

16:36 Uhr, 19.03.2011

Antworten
Hallo ich habe folgende Aufgabe:

783x = 1 mod 32231

gesucht ist x (lt. Lsg x = 27950)
ich weiß, dass ich den euklidischen Algorithmus rückwärts anweden soll. Leider bekomm ich das einfach nicht hin


vorwärts würde ich es so machen:
32231 = 41*783 + 128
783 = 6*128 + 15
128 = 8*15 + 8
15 = 1*8 + 7
8 = 1*7 + 1
7 = 7*1 + 0


Kann mir bitte jmd helfen?
Online-Nachhilfe in Mathematik
Antwort
michaL

michaL aktiv_icon

17:40 Uhr, 19.03.2011

Antworten
Hallo,

nun, es gilt, die 1 (gleich dem ggT) nur aus Vielfachen von 783 und 32231 darzustellen. Also beginnst du mit:
1=8-1⋅7 (voletzte Zeile deines euklidischen Algorithmus')
=(128-8⋅15)-1⋅7 (aus Zeile 3)
=32231-41⋅783-8⋅15-(15-8) (Zeile 1 und Zeile 4)
=32231-41⋅783-9⋅15+8 (zusammengefasst)
=32231-41⋅783-9⋅(783-6⋅128)+128-8⋅15
=32231-50⋅783+55⋅128-8⋅15

So hangelst du dich immer weiter, bis du eine Zeile 1=k⋅32231+l⋅783 da stehen hast.

Mfg Michael
Frage beantwortet
RoXoR

RoXoR aktiv_icon

09:54 Uhr, 20.03.2011

Antworten
Vielen Dank Michael