Hi,

wie loese ich denn Aufgaben der folgenden Art:

Bestimme x E {1,…,576} sodass gilt: 165x kongruentzu 1(mod 577)

Ich hab doch in der Klausur keine Zeit, alle paarhundert Elemente durchzugehen, bis vielleicht mal eins dabei ist, das dann passt…..

Dann warst du wohl nicht in der Übung, wo das Verfahren genau durchgekaut wird ;)

Im Prinzip machst du erstmal eine bestimmung des ggt von 165 und 577, denn wenn die beiden nicht teilerfremd sind kann man das sowieso nicht lösen. Dazu nutzt du das Eulerverfahren und am Ende hast du irgendwo (mit passenden Variablen, keine Lust zu rechnen)
e = d * c + b
c = a * b + 1

Von diesem Punkt aus kannst du jetzt die Eulerrechnung wieder aufwickeln:
1 = c - a * b, b = e - d * c
1 = c - a * (e - d * c)
etc. etc. bis du nur noch 165 und 577 und eine weitere Zahl hast. Das ganze lässt sich dann umformen zu
1 = x * 577 + y * 165

Da modulo 577 gerechnet wird, fallen die ganzen x * 577 weg und es bleibt
1 = y * 165 (mod 577)
und da ist dann die Lösung

Lösung : x = 7

Ich gehe mal stark davon aus, dass das "Eulerverfahren" der euklidische Algorithmus sein soll?
Oder hab ich im Semester irgendwas Wichtiges verpasst?

Jo, klingt so.

Klingt als ob ich was verpasst hab oder nach dem euklidischen Algorithmus? Bzw rückwärts angewandt, so wie es in einer Übungsaufgabe verlangt war…

Du redest immer so in Rätseln :p

Klingt nach euklidischem Algorithmus, sorry.