Notizen zur ersten Übung

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Notizen zur ersten Übung

Beitrag von Steven »

Da mir in meiner Übungsgruppe einige Startschwierigkeiten mit der ersten Übung aufgefallen sind, habe ich mal ein paar Notizen dazu aufgeschrieben - in der Hoffnung, dass sie für den einen oder anderen hilfreich sind. Ihr findet das Dokument hier.

Ich würde euch dennoch empfehlen, euch zuerst selbst an einer komplett eigenständigen Lösung zu versuchen. Klappt das nicht, hilft ein Blick ins Dokument eventuell weiter, um einen Anfang zu finden.

trinity
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 29. Sep 2009 12:57

Re: Notizen zur ersten Übung

Beitrag von trinity »

Hallo,

danke für das Hochladen der Notizen, die sind wirklich sehr hilfreich, auch zum Abgleichen mit der eigenen Lösung. :)

Viele Grüße,
trinity

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: Notizen zur ersten Übung

Beitrag von kain »

Bei 1b verstehe ich nicht, wie man auf 16 kommen soll. Mit Hilfe des erweiterten euklidischen Algortihmus kommt man wieder auf den ggT.
Man muss jetzt irgendwie k und l ändern, aber wie?

Ist bei 1c das Inverse von 1215 das l aus dem Algorithmus? Falls ja, immer?

Aufgabe 2 weiss nicht wie man das zeigen soll.

Bsp.:

p|n
a = b (mod n) => a = b (mod p)


3|6
a = 9 (mod 6) = 3
a = 9 (mod 3) = 0

?

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: Notizen zur ersten Übung

Beitrag von Steven »

kain hat geschrieben:Bei 1b verstehe ich nicht, wie man auf 16 kommen soll. Mit Hilfe des erweiterten euklidischen Algortihmus kommt man wieder auf den ggT.
Du hast aus dem erweiterten Euklidischen Algorithmus x und y sodass gilt: 2464 * x + 1215 * y = 1. Du brauchst rechts aber 16 statt 1. Das ist eine normale Gleichung, also machst du was? Hier reicht eine einzige Äquivalenzumformung.
kain hat geschrieben:Ist bei 1c das Inverse von 1215 das l aus dem Algorithmus? Falls ja, immer?
Ja genau, den Wert schreibst du einfach aus dem Algorithmus ab. Die Begründung, warum das so einfach geht, ist die Herleitung im Dokument.
kain hat geschrieben:Aufgabe 2 weiss nicht wie man das zeigen soll.
Zeigen sollst du es allgemein, ich gebe hier mal ein Zahlenbeispiel zur Verdeutlichung. Sei p=3, n=6. Dann sollst du zeigen, dass aus a=b (mod 6) auch a=b (mod 3) folgt. Also beispielsweise: Aus 12=18 (mod 6) folgt zwingend, dass auch 12=18 (mod 3) gilt. Und zwar für alle a, b und nicht nur für 12 und 18. Und natürlich auch für alle p und n, solange p ein Teiler von n ist.

Da macht es Sinn, sich die Definition des Modulo-Operators noch einmal anzusehen. Was bedeutet es denn, wenn zwei zwei Werte modulo irgend etwas gleich sind? Oder anders gefragt: Wann ist denn a=b (mod n)?
Damit kannst du den Modulo-Operator herauswerfen - du ersetzt ihn durch seine Definition. Dann formst du nur noch ein bisschen um.

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: Notizen zur ersten Übung

Beitrag von kain »

Ok, danke.

Kurze Frage noch: Das Inverse von a oder b, ist immer das jeweilige k oder l?

downsampling
Mausschubser
Mausschubser
Beiträge: 95
Registriert: 28. Mär 2011 22:58

Re: Notizen zur ersten Übung

Beitrag von downsampling »

kain hat geschrieben:Ok, danke.

Kurze Frage noch: Das Inverse von a oder b, ist immer das jeweilige k oder l?
Nein. AFAIR nur für ggt = 1

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: Notizen zur ersten Übung

Beitrag von Steven »

Das Inverse lässt sich nur für Elemente berechnen, die auch invertierbar sind. Ist der ggT(a,n)!=1, dann ist a nicht invertierbar mod n, d.h. es gibt gar kein Inverses. Diese Aussage soll auch auf dem zweiten Übungsblatt in Aufgabe 2b gezeigt werden.

Benutzeravatar
Michl
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 293
Registriert: 12. Apr 2009 08:53
Wohnort: Darmstadt

Re: Notizen zur ersten Übung

Beitrag von Michl »

Wie kommt man mit einer Äquivalenzumformung von 2464*(-536)+1215*1087 = 1 auf 2464x+1215y=16?

LucasR
Kernelcompilierer
Kernelcompilierer
Beiträge: 474
Registriert: 9. Jun 2009 09:55

Re: Notizen zur ersten Übung

Beitrag von LucasR »

Michl hat geschrieben:Wie kommt man mit einer Äquivalenzumformung von 2464*(-536)+1215*1087 = 1 auf 2464x+1215y=16?
Multipliziere deine -536 und 1087 mit 16.

Benutzeravatar
Cpro
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 16. Okt 2010 22:13
Wohnort: Darmstadt

Re: Notizen zur ersten Übung

Beitrag von Cpro »

Achso von 1 auf 16... ja dann Multiplizieren... niemand hat was gelesen :P

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: Notizen zur ersten Übung

Beitrag von Steven »

Ich biete meinen Übungsteilnehmern auch an, Übungen abzugeben und korrigieren zu lassen. Das bringt zwar keine Punkte, aber ihr wisst dann, was falsch und was richtig war bzw. was ihr nochmal genauer anschauen solltet. Die richtige Idee alleine reicht ja nicht, es muss auch richtig auf dem Papier stehen.

Antworten

Zurück zu „Archiv“