Satz von Euler & Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:35 Mi 06.06.2012 | | Autor: | Pauli85 |
| Aufgabe | Betrachte die Einwegfunktion k [mm] \mapsto a^{k} [/mm] mod n.
Sei n nun n=11. Bestimme für a = 1...10 jeweils das kleinste k > 0 mit [mm] a^{k} \equiv [/mm] 1 mod 11. |
Hallo,
ich weiß zwar wie man bei der Aufgabe geschickt vorgehen kann, jedoch verstehe ich noch nicht so ganz warum.
Durch den Satz von Euler kann man k auf höchstens 10 festlegen, denn [mm] \phi(11) [/mm] = 10. Also muss für alle a gelten: [mm] a^{10} \equiv [/mm] 1 mod 11. Jetzt sind wir aber am kleinsten k interessiert. In Frage kommen jetzt alle k's, die Teiler von 10 sind, also k [mm] \in [/mm] {1,2,5,10}.
Doch wieso gerade die Teiler von 10? Kann mir das jemand erklären?
Grüße
|
|
| |
|
Hallo Pauli,
ich weiß noch nicht, ob ich das erklären kann - es scheint so offensichtlich zu sein. 
> Betrachte die Einwegfunktion k [mm]\mapsto a^{k}[/mm] mod n.
> Sei n nun n=11. Bestimme für a = 1...10 jeweils das
> kleinste k > 0 mit [mm]a^{k} \equiv[/mm] 1 mod 11.
> Hallo,
> ich weiß zwar wie man bei der Aufgabe geschickt vorgehen
> kann, jedoch verstehe ich noch nicht so ganz warum.
> Durch den Satz von Euler kann man k auf höchstens 10
> festlegen, denn [mm]\phi(11)[/mm] = 10. Also muss für alle a
> gelten: [mm]a^{10} \equiv[/mm] 1 mod 11. Jetzt sind wir aber am
> kleinsten k interessiert. In Frage kommen jetzt alle k's,
> die Teiler von 10 sind, also k [mm]\in[/mm] {1,2,5,10}.
Ja, alles ganz wunderbar.
> Doch wieso gerade die Teiler von 10? Kann mir das jemand
> erklären?
Na, wenn für ein k mit k|10 die Kongruenz [mm] a^k\equiv 1\mod{11} [/mm] erfüllt ist, dann gibt es ja ein m mit m*k=10, so dass auch [mm] a^{10}=a^{m*k}=\left(a^k\right)^m\equiv 1^m \equiv 1\mod{11} [/mm] gilt. Soweit, so langweilig.
Nehmen wir aber an das kleinste k sei kein Teiler von 10, dann führt das ja zu einem Widerspruch: Sei [mm] a^k\equiv 1\mod{11}, [/mm] natürlich mit k<11.
Dann gibt es ein m, so dass m*k<11<(m+1)*k ist. Dann ist d:=11-m*k<k.
Es muss aber auch gelten: [mm] a^d\equiv 1\mod{11}, [/mm] was der gesuchte Widerspruch ist.
Verstehst Du den letzten Schritt? Ich habe ihn bewusst nicht ganz vollständig aufgeschrieben.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:46 So 10.06.2012 | | Autor: | Pauli85 |
Alles klar, vielen Dank für deine Hilfe! Jetzt, wo ich die Sache in mathematischen Ausdrücken sehe, fallen mir die Tomaten vor den Augen runter ;)
|
|
|
|
