|
|
| Autor |
Nachricht |
Peneli
Senior Member
Anmeldungsdatum: 08.06.2006
Beiträge: 2223
|
 Verfasst am: 30 Jun 2007 - 19: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.  |
|
 |
cyrix42
Valued Contributor
Anmeldungsdatum: 14.08.2006
Beiträge: 22635
|
| Verfasst am: 30 Jun 2007 - 19:08:08 Titel: |
|
|
Was sagt der kleine Fermat zu 3^(4k+l) mod 5? 
Cyrix |
|
|
Peneli
Senior Member
Anmeldungsdatum: 08.06.2006
Beiträge: 2223
|
| Verfasst am: 30 Jun 2007 - 19: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
Anmeldungsdatum: 14.08.2006
Beiträge: 22635
|
| Verfasst am: 30 Jun 2007 - 19:18:01 Titel: |
|
|
Das ist richtig!
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).
Cyrix |
|
|
Peneli
Senior Member
Anmeldungsdatum: 08.06.2006
Beiträge: 2223
|
| Verfasst am: 30 Jun 2007 - 19:21:48 Titel: |
|
|
| Alles klar! Ich dank Dir!! |
|
|
Peneli
Senior Member
Anmeldungsdatum: 08.06.2006
Beiträge: 2223
|
| Verfasst am: 30 Jun 2007 - 20:10:50 Titel: |
|
|
| Noch eine Frage dazu: Gibt es eine ähnliche Vorgehensweise für (mod q), wenn q nicht prim ist? |
|
|
cyrix42
Valued Contributor
Anmeldungsdatum: 14.08.2006
Beiträge: 22635
|
| Verfasst am: 30 Jun 2007 - 20: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
Anmeldungsdatum: 08.06.2006
Beiträge: 2223
|
| Verfasst am: 30 Jun 2007 - 20: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).  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.
Zuletzt bearbeitet von Peneli am 30 Jun 2007 - 20:52:52, insgesamt einmal bearbeitet |
|
|
cyrix42
Valued Contributor
Anmeldungsdatum: 14.08.2006
Beiträge: 22635
|
| Verfasst am: 30 Jun 2007 - 20: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
Anmeldungsdatum: 08.06.2006
Beiträge: 2223
|
| Verfasst am: 30 Jun 2007 - 20:53:36 Titel: |
|
|
| Ja, danke. Ist mir eben selbst schon eingefallen. |
|
|
Peneli
Senior Member
Anmeldungsdatum: 08.06.2006
Beiträge: 2223
|
| Verfasst am: 30 Jun 2007 - 21:13:21 Titel: |
|
|
Noch einmal zurück zu meiner Frage:
Wann darf ich mir so ein System basteln? Müssen die Modulo-Werte teilerfremd sein, damit ich dann den Algorithmus des chin. Restsatzes anwenden kann?
Was mach ich, wenn sich so ein System nicht finden lässt und ich Euler nicht anwenden will, weil es mir zu mühsam ist, die teilerfremden Zahlen zu zählen?
Bsp.: 13^22082=x (mod 144).
Darf man es splitten? Wenn ja, wie klein? Bis (mod 2) und (mod 3), oder bleib ich bei (mod 12)? Wie geh ich damit um, dass ich zweimal (oder noch häufiger) dieselbe Kongruenz zu lösen hab? |
|
|
someDay
Senior Member
Anmeldungsdatum: 04.09.2005
Beiträge: 3889
|
|
|
Peneli
Senior Member
Anmeldungsdatum: 08.06.2006
Beiträge: 2223
|
| Verfasst am: 30 Jun 2007 - 21:49:11 Titel: |
|
|
Hey, danke. Das ist ja genial einfach.
Also muss ich mich einfach damit zufrieden geben, dass ich den Weg über den chin. Restsatz in diesem Fall nicht gehen darf? (Jetzt mal unabhängig davon, dass Euler viel schneller zum Ziel führt.) |
|
|
someDay
Senior Member
Anmeldungsdatum: 04.09.2005
Beiträge: 3889
|
| Verfasst am: 30 Jun 2007 - 21:53:23 Titel: |
|
|
Naja, gehen darfst du schon - aber du musst hier halt mod 16 und mod 9 arbeiten, ob das viel hilft ist eine andere Frage.
sD. |
|
|
Peneli
Senior Member
Anmeldungsdatum: 08.06.2006
Beiträge: 2223
|
| Verfasst am: 30 Jun 2007 - 21:59:41 Titel: |
|
|
| someDay hat folgendes geschrieben: |
| aber du musst hier halt mod 16 und mod 9 arbeiten, ob das viel hilft ist eine andere Frage. |
Die Frage, ob's sinnvoll ist, will ich bewusst nicht stellen.
Aber ob's hilft, natürlich schon. Und da weder 16 noch 9 prim sind, hab ich natürlich ein Problem, die "kleinen" Module aufzulösen. Es sei denn, ich geh dort wieder über Euler, aber den wollt ich ja in diesem Fall vermeiden...
Ok, ich akzeptier einfach, dass es keinen Sinn hat.
Also vielen Dank Euch beiden. Habt mir sehr geholfen!! |
|
|
|
Home
FAQ
Regeln
Suchen
Registrieren
Login
