| |
| Autor |
  Kleiner Fermat mit Addition |
|
Ehemaliges_Mitglied
 |  Themenstart: 2007-12-07
|
Hallöchen,
ich hänge noch an folgender Aufgabe
Es seien p und q verschiedene ungerade Primzahlen. Beweise, daß
p^(q-1) + q^(p-1) == 1 (mod pq)
Ich habe versucht mit Potenzgesetzen das ganze auf den "kleinen Satz von Fermat" zurückzuführen, bin aber gescheitert. Wer wüsste wie man es machen könnte? Oder geht es anders?
[ Nachricht wurde editiert von VanillaFish am 07.12.2007 18:56:23 ]
|
 Profil
|
Stefan_K
Senior 
Dabei seit: 13.07.2005
Mitteilungen: 4392
Wohnort: Hamburg
| Beitrag No.1, eingetragen 2007-12-07
|
Hallo VanillaFish,
hast Du die Behauptung wirklich richtig hier aufgeschrieben? Prüfe sie einmal für p=3 und q=5.
Viele Grüße,
StefanK
[Verschoben in Forum 'Kongruenzen' von Stefan_K]
|
Profil
|
Ehemaliges_Mitglied
| Beitrag No.2, vom Themenstarter, eingetragen 2007-12-07
|
Verzeihung es fehlte ein Zeichen. Ich habs oben ergänzt.
|
Profil
|
Buri
Senior 
Dabei seit: 02.08.2003
Mitteilungen: 46882
Wohnort: Dresden
 | Beitrag No.3, eingetragen 2007-12-07
|
\quoteon(2007-12-07 17:59 - VanillaFish)
Ich habe versucht mit Potenzgesetzen das ganze auf den "kleinen Satz von Fermat" zurückzuführen ...
\quoteoff
Hi VanillaFish,
die Idee ist richtig, und Potenzgesetze braucht man nicht.
Die Differenz beider Seiten pq-1 + qp-1 - 1 ist durch p teilbar, denn nach dem kleinen Fermatschen Satz ist qp-1 - 1 durch p teilbar (q ist teilerfremd zu p, weil q ≠ p Primzahl ist), und pq-1 ist sogar durch p2 teilbar.
Ebenso beweist man die Teilbarkeit durch q, und eine Zahl, die durch zwei verschiedene Primzahlen p und q teilbar ist, ist durch pq teilbar.
Gruß Buri
[ Nachricht wurde editiert von Buri am 07.12.2007 19:17:15 ]
|
Profil
|
Ehemaliges_Mitglied
| Beitrag No.4, vom Themenstarter, eingetragen 2007-12-07
|
Ich habe es jetzt so aufgeschrieben:
Nach Satz von Euler und Satz von Fermat gilt wegen p!=q, beide prim:
q^(p-1) -1 == 0 (mod p) \and\ p^(q-1) -1 == 0 (mod p)
q^(p-1) -1 == 0 (mod q) \and\ p^(q-1) -1 == 0 (mod q)
Mit dem Fundamentalsatz der Algebra folgt, dass eine Zahl die durch zwei Primzahlen p und q teilbar ist, auch durch deren Produkt pq teilbar ist, bzw. die Zahl kongruent 0 modulo pq ist.
Wenn aber nun
q^(p-1) -1 == 0 (mod pq) \and\ p^(q-1) -1 == 0 (mod pq)
dann gilt auch
q^(p-1) + q^(p-1) -1 == 0 (mod pq) bzw.
q^(p-1) + q^(p-1) == 1 (mod pq)
Geht das so?
[ Nachricht wurde editiert von VanillaFish am 07.12.2007 19:43:27 ]
[ Nachricht wurde editiert von Buri am 07.12.2007 19:48:35 ]
|
Profil
|
Buri
Senior
Dabei seit: 02.08.2003
Mitteilungen: 46882
Wohnort: Dresden
| Beitrag No.5, eingetragen 2007-12-07
|
\quoteon(2007-12-07 19:39 - VanillaFish)
Geht das so?
\quoteoff
Hi VanillaFish,
nein, das geht nicht. Deine Kongruenzen sind falsch, nur die erste und vierte (kleiner Fermatscher Satz) sind richtig.
Der verwendete Satz ist nicht der Fundamentalsatz der Algebra, sondern eine einfache Aussage über Teilbarkeit, sie hängt mit dem chinesischen Restsatz zusammen.
Gruß Buri
[ Nachricht wurde editiert von Buri am 07.12.2007 19:54:26 ]
|
Profil
|
fru
Senior 
Dabei seit: 03.01.2005
Mitteilungen: 21456
Wohnort: Wien
 | Beitrag No.6, eingetragen 2007-12-07
|
\quoteon(2007-12-07 19:39 - VanillaFish)
Nach Satz von Euler und Satz von Fermat gilt wegen p!=q, beide prim:
q^(p-1) -1 == 0 (mod p) \and\ p^(q-1) -1 == 0 (mod p)
und
q^(p-1) -1 == 0 (mod q) \and\ p^(q-1) -1 == 0 (mod q)
\quoteoff
\
Hi VanillaFish!
Jeweils eine der zwei Kongruenzen jeder dieser beiden Zeilen ist falsch.
Außerdem ist Deine Begründung ziemlich unklar:
Du solltest schon genauer schreiben, was aus
p!=q \and\ p\el\IP \and\ q\el\IP
folgt, das die jeweils ander Kongruenz richtig macht. Sieh Dir dazu die Voraussetzungen des Satzes von Fermat genau an!
EDIT:
Ich sehe gerade, daß man dies doch ganz gut als Begründung nehmen kann.
END EDIT
Auch die darauffolgende Begründung mittels des Fundamentalsatzes der Algebra ist für mich nicht einsichtig:
Auf den ersten Blick hat dieser nichts mit der Behauptung zu tun. Wenn Du dennoch glaubst, diese mit jenem begründen zu können, dann mußt Du das schon wesentlich ausführlicher darstellen. Ich würde mich dabei aber nicht auf diesen Satz zu berufen versuchen.
Liebe Grüße, Franz
[Die Antwort wurde nach Beitrag No.4 begonnen.]
[ Nachricht wurde editiert von fed am 07.12.2007 20:02:13 ]
|
Profil
|
Ehemaliges_Mitglied
| Beitrag No.7, vom Themenstarter, eingetragen 2007-12-08
|
Hi, sorry aber ich verstehe es nicht. Die einzige Voraussetzung für den kleinen Fermat ist ja, dass die Zahl kein vielfaches ihres Exponenten ist, das ist ja automatisch gegeben weil p und q prim und verschieden.
Und wenn aber die Kongruenzen so wie ich sie aufgeschrieben habe nicht stimmen, wie bekomme ich verknüpft, dass die Summe mod pq = 1 ist? Ich stehe völlig auf dem Schlauch...
|
Profil
|
fru
Senior
Dabei seit: 03.01.2005
Mitteilungen: 21456
Wohnort: Wien
| Beitrag No.8, eingetragen 2007-12-08
|
Hi, Buri hat Dir doch die Lösung schon vollständig aufgeschrieben. Du kannst sie, wenn Du willst, natürlich noch mehr formalisieren (nötig ist das aber nicht). Beginne dann einmal damit ...
\quoteon(2007-12-07 19:16 - Buri)
... nach dem kleinen Fermatschen Satz ist qp-1 - 1 durch p teilbar [...] und pq-1 ist sogar durch p2 teilbar.
\quoteoff
..., folgere daraus das unmittelbar davor Stehende, und arbeite dann den Rest des Beitrags No. 3 analog dazu ab.
|
Profil
|
Ehemaliges_Mitglied
| Beitrag No.9, vom Themenstarter, eingetragen 2007-12-08
|
Ok, ich habe meinen Fehler in den Kongruenzen gefunden.
Nun habe ich aufgeschrieben
Es gilt:
p^(q-1) == 0 (mod p) \and\ q^(p-1) -1 == 0 (mod p)
q^(p-1) == 0 (mod q) \and\ p^(q-1) -1 == 0 (mod q)
Daraus ergibt sich ja dann, das der Gesamtterm der Ausgangsaufgabe sowohl zu p als auch zu q kongruent 1 ist.
Jetzt habe ich das Problem mit der "einfachen Aussage zur Teilbarkeit".
Ich finde keinen dazu passenden Satz in meinen Aufzeichnungen obwohl wir Teilbarkeit und Primzahlen explizit als Kapitel hatten. Und wenn ich das einfach so hinschreibe schreibt mein Prof. da wieder dran "Das müssen sie mir erstmal beweisen!" :-(
Kann ich mich da auf irgendeinen bekannten Satz berufen?
[ Nachricht wurde editiert von VanillaFish am 08.12.2007 18:14:19 ]
|
Profil
|
fru
Senior
Dabei seit: 03.01.2005
Mitteilungen: 21456
Wohnort: Wien
| Beitrag No.10, eingetragen 2007-12-08
|
\
Der allgemeine Satz, nach dem Du suchst, lautet:
m\|a\and\ n\|a\and\ ggT(m,n)=1
=>
(m*n)\|a
Beachte, daß die Voraussetzung, daß die beiden Teiler relativ prim sind, wesentlich ist. Dazu brauchst Du nur z.B. m=n=a=2 zu setzen:
2\|2\and\ 2\|2\and\ (2*2)\teiltnicht\ 2
Es wird eine gute Übung für Dich sein, diesen Satz zu beweisen, auch wenn Du ihn vielleicht als bekannt voraussetzen darfst.
|
Profil
|
Ehemaliges_Mitglied
| Beitrag No.11, vom Themenstarter, eingetragen 2007-12-08
|
Ich denke ich habs... Danke an alle!
|
Profil
|
Ehemaliges_Mitglied hat die Antworten auf ihre/seine Frage gesehen.
Ehemaliges_Mitglied hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
