Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Klausur F09 - Aufgabe III-2
Hi,
http://www8.informatik.uni-erlangen.de/IMMD8/Lectures/THINF3/Klausuren/F09Klausur.pdf
Teilaufgabe 3: Ich verzweifle langsam an dieser Aufgabe weil ich schon alles (offensichtlich fast alles) ausprobiert habe.
Aus Teilaufgabe 1 und 2 habe ich folgende Ergebnisse:
ord_11 (2) = 10
ord_17 (2) = 8
ord_19 (2) = 18
2^111 mod 11 = 2
2^111 mod 17 = 9
2^111 mod 19 = 8
Dann weiß ich natürlich: ord_3553 (2) = kgV(10,8,18) = 360
Und: 2^111 mod 3553 = 2763 (mit EEA-Rumrechnen)
So und nun?
3552/360 = 9 Rest 312. Also müsste ich noch immer 2^312 mod 3553 rechnen, fail 
3552/111 = 32. Das wäre dann 2763^32, auch fail.
Jetzt fehlen mir die Ideen. Ich hoffe es kann mir jemand helfen. Danke.
Ich denke, man soll modular rechnen, wie auch in der Aufgabenstellung angegeben.
D.h. statt
[m]2^3552 mod 3553[/m]
rechnest du[m]
2^3552 = 2^11132 = (2^111)^32 = 2^32 = 4 mod 11
2^3552 = 2^11132 = (2^111)^32 = 9^32 = 1 mod 17
2^3552 = 2^111*32 = (2^111)^32 = 8^32 = 7 mod 19[/m]
Weiß grad nicht auswendig, ob das schon reicht (ich hab von der ganzen modularen Arithmetik immer nur die Hälfte im Kopf ;)), denke aber schon. Wenn nicht, muss halt noch der chinesische Restesatz her, dann is aber gut ^^
Ok, so kann man das machen. Danke. Da man zeigen soll dass a=2 ein Fermat-Zeuge ist denke ich aber schon, dass man noch den Chinesischen Restsatz anwenden muss, wobei mir das für 3 Punkte fast etwas viel erscheint.
Kann vllt jemand kurz erklären, wie teilaufgabe 1 und 2 funktionieren?
Oder hat jemand vielleicht nen Link, wo beschrieben wird, wie das geht?
Solange multiplizieren, bis du wieder bei 1 ankommst.
Zum Beispiel für [m]ord_11 (2)[/m]:
[m]2^1 = 2 mod 11
2^2 = 4 mod 11
2^3 = 8 mod 11
2^4 = 16 = 5 mod 11
2^5 = 2^4 * 2 = 52 = 10 mod 11
2^6 = 102 = 9 mod 11
2^7 = 18 = 7 mod 11
2^8 = 14 = 3 mod 11
2^9 = 6 mod 11
2^10 = 12 = 1 mod 11
=> ord_11 (2) = 10[/m]
Für die zweite Teilaufgabe brauchst du, dass
[m] ( a^k = a^(k mod ord_n (a)) ) mod n[/m]
gilt.
D.h. [m]2^111 = 2^1 mod 11[/m]
zu 1.: Für z.B. Z11:
Sukzessive 2^1mod11, 2^2mod11,2^3mod11,… berechnen, bis 1 rauskommt. Die Hochzahl ist dann die Ordnung. Diese Ordnung muss die Gruppenordnung (hier 10) teilen, nur als Hinweis dass man nicht manchmal zu viel rumrechnet. Manchmal ist auch die Ordnung einer Zahl gleich der Gruppenordnung (wie hier).
zu 2.: Jetzt weiss man ja dass 2^10 mod 11=1. Also kann man das von 2^111 einfach rausdividieren, denn:
2^111 = (2^10)^11 * 2^1 = 1^11 * 2^1 = 2^1 = 2. Und 2 mod 11 = 2.
Die anderen Zahlen gehen sehr ähnlich.
P.S. Ich bin morgen den ganzen Tag an der Uni, falls also noch fragen sind, PM, dann kann man sich ja mal kurz treffen.
Edit: Doppelt gemoppelt hält besser Und nochwas: Das P.S. soll nicht bedeuten ich könnte auch alles andere 
super, danke euch beiden!
für all diejenigen die die klausur noch vor sich haben möchte ich noch kurz anmerken das, wenn man die ordnung berechnen will nicht von 1 bis n-1 alle potenzen ausprobieren muss.
Wegen dem Satz von Lagrange muss die Ordnung ein Teiler von Phi(n) sein.
Konkret heisst das hier, dass bei mod 11 (also Phi(11)= 10 = 2 * 5) nur 2,5,10 in frage kommen! man muss also nicht alle zahlen durchprobieren