Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Kleiner Fermat
Gehe zu Seite 1, 2  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Kleiner Fermat
 
Autor Nachricht
Peneli
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 08.06.2006
Beiträge: 2223

BeitragVerfasst am: 30 Jun 2007 - 18:06:56    Titel: Kleiner Fermat

Hab grad ein Brett vor dem Kopf:

Was nützt mir der "Kleine Fermat" [a^p=a (mod p), mit a aus Z, p prim], wenn ich Kongruenzen wie z.B. 3^(251)=x (mod 5) auflösen will?

Danke. Very Happy
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 23528

BeitragVerfasst am: 30 Jun 2007 - 18:08:08    Titel:

Was sagt der kleine Fermat zu 3^(4k+l) mod 5? Smile

Cyrix
Peneli
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 08.06.2006
Beiträge: 2223

BeitragVerfasst am: 30 Jun 2007 - 18:15:43    Titel:

Sagt er denn was dazu??
Ich vermute, dass es so was wie 3^(4k+l)=3^l (mod 5) sein könnte...? Oder lieg ich da ganz daneben?
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 23528

BeitragVerfasst am: 30 Jun 2007 - 18:18:01    Titel:

Das ist richtig! Smile

Wie man darauf kommt: z.B. so:

laut kleinem Fermat ist 3^5 == 3 (mod 5), und da 3 teilerfremd zu 5 ist, können wir die Gleichung durch 3 teilen, erhalten also 3^4 == 1 (mod 5), und insbesondere auch 3^(4k)=(3^4)^k == 1^k = 1 (mod 5).

Also gilt 3^251 = 3^(4*62+3) == 3^3 (mod 5). Smile


Cyrix
Peneli
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 08.06.2006
Beiträge: 2223

BeitragVerfasst am: 30 Jun 2007 - 18:21:48    Titel:

Alles klar! Ich dank Dir!! Very Happy
Peneli
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 08.06.2006
Beiträge: 2223

BeitragVerfasst am: 30 Jun 2007 - 19:10:50    Titel:

Noch eine Frage dazu: Gibt es eine ähnliche Vorgehensweise für (mod q), wenn q nicht prim ist?
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 23528

BeitragVerfasst am: 30 Jun 2007 - 19:14:11    Titel:

Peneli hat folgendes geschrieben:
Noch eine Frage dazu: Gibt es eine ähnliche Vorgehensweise für (mod q), wenn q nicht prim ist?



Ja. Zum einen kannst du oft die Kongruenz mittels des chinesischen Restsatz bezüglich kleinerer Module auseinander nehmen,

zum anderen gibt es eine Verallgemeineriung des kleinen Fermats, den Satz von Euler-Fermat, der da lautet, dass für zu m teilerfremdes a folgendes gilt:

a^( phi(m) ) == 1 (mod m),

wobei phi(m) die Eulersche Phi-Funktion ist, und die Anzahl der zu zu m teilerfremden nat. Zahlen <m angibt.


Cyrix
Peneli
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 08.06.2006
Beiträge: 2223

BeitragVerfasst am: 30 Jun 2007 - 19:49:37    Titel:

Danke. Hab noch ein kleines Problem...

Die Sache mit der Verallgemeinerung von Euler funktioniert problemlos.
Hab das jetzt durchexerziert mit 2^23483=x (mod 39), komme auf 24 teilerfremde Zahlen und folglich:
2^(24*978+11)=2^11=20 (mod 39).

Aber der chinesische Restsatz will nicht so recht...
Hab jetzt laut Wiki aus meiner Kongruenz ein System gebaut:

x=2^23483 (mod 3)
x=2^23483 (mod 13).

Unter welchen Bedingungen darf ich das überhaupt??

Wenn ich das dann durchführe, dreh ich mich im Kreis:

Mit den angegebenen Bezeichnungen komm ich auf M=39, M1=13, M2=3, m1=3, m2=13.
Wegen 1=1*13-4*3 folgen r1=-4, s1=1, r2=1, s2=-4 sowie e1=13 und e2=-12.

Damit: x=2^23483*13+2^23483*(-12)=2^23483 (mod 39). Laughing Zumindest weiß ich, dass ich den Algorithmus richtig durchgeführt hab, aber gewonnen hab ich dadurch natürlich nichts...

Was muss ich anders machen?

EDIT: *Lichtblick hab* Muss ich evtl. die beiden kleinen Module erst vereinfachen? Werd das gleich mal austesten...

EDIT2: *Brett vom Kopf nehm* Alles paletti. Funktioniert. Very Happy


Zuletzt bearbeitet von Peneli am 30 Jun 2007 - 19:52:52, insgesamt einmal bearbeitet
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 23528

BeitragVerfasst am: 30 Jun 2007 - 19:52:45    Titel:

Na wenn du die Kongruenz von einer großen Zahl modulo 39 bestimmen willst, bestimmst du sie erst modulo 3 und 13, und fügst deine Ergebnisse mittels CRT wieder zusammen.

Beispiel:

2^bla == x (modulo 3) und 2^bla == y (modulo 13) ==> 2^bla == irgendwas (modulo 39).

Cyrix
Peneli
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 08.06.2006
Beiträge: 2223

BeitragVerfasst am: 30 Jun 2007 - 19:53:36    Titel:

Ja, danke. Ist mir eben selbst schon eingefallen. Very Happy
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Kleiner Fermat
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2  Weiter
Seite 1 von 2

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum