www.vorkurse.de
Ein Projekt von vorhilfe.de
Die Online-Kurse der Vorhilfe

E-Learning leicht gemacht.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Teams · Forum · Wissen · Kurse · Impressum
Forenbaum
^ Forenbaum
Status Mathe-Vorkurse
  Status Organisatorisches
  Status Schule
    Status Wiederholung Algebra
    Status Einführung Analysis
    Status Einführung Analytisc
    Status VK 21: Mathematik 6.
    Status VK 37: Kurvendiskussionen
    Status VK Abivorbereitungen
  Status Universität
    Status Lerngruppe LinAlg
    Status VK 13 Analysis I FH
    Status Algebra 2006
    Status VK 22: Algebra 2007
    Status GruMiHH 06
    Status VK 58: Algebra 1
    Status VK 59: Lineare Algebra
    Status VK 60: Analysis
    Status Wahrscheinlichkeitst

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - Satz von Euler & Kongruenzen
Satz von Euler & Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Satz von Euler & Kongruenzen: Rückfrage
Status: (Frage) beantwortet Status 
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

        
Bezug
Satz von Euler & Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 19:49 Mi 06.06.2012
Autor: reverend

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


Bezug
                
Bezug
Satz von Euler & Kongruenzen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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 ;)

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorkurse.de
[ Startseite | Mitglieder | Teams | Forum | Wissen | Kurse | Impressum ]