Diskussion:Kleiner fermatscher Satz

Allgemeines

der artikel muß auch ohne querverweis zu einem anderen artikel zumindest ansatzweise verständlich sein, was er mitnichten ist.

Der Beweis ist sehr unglücklich formuliert.

   Was bedeutet denn das Zeichen, das aus drei waagerechten Linien übereinander besteht?Udm 09:42, 12. Jan 2005 (CET)

Das ist das Kongruenzzeichen, es wird im Artikel Modulo erklärt. Stern !? 09:43, 12. Jan 2005 (CET)

Neuer Abschnitt Beweis

Ich möchte vorschlagen, den Abschnitt "Beweis" zu ersetzen durch:

Ein einfacher Beweis beruht auf folgender kombinatorischer Überlegung: Aus Perlen von $a$ verschiedenen Farben soll eine (geschlossene) Kette mit $p$ Perlen zusammengestellt werden. Für jede Perle gibt es $p$ Wahlen, insgesamt gibt es also $a^{p}$ Möglichkeiten. Betrachtet man eine Kette und alle Ketten, die aus ihr durch Rotation hervorgehen, so gibt es zwei Möglichkeiten:

• Alle Perlen der Kette haben dieselbe Farbe.
• Durch Rotation erhält man genau $p$ verschiedene Ketten.

Es gibt $a$ einfarbige Ketten, also ist $a^{p}-a$ die Anzahl der gemischtfarbigen Ketten. Nach der obigen Überlegungen kann man die gemischtfarbigen Ketten aber in Gruppen zu je $p$ zusammenfassen, ihre Anzahl ist also durch $p$ teilbar.

Ein technisch aufwendigerer Beweis nutzt den Satz von Lagrange aus der elementaren Gruppentheorie: Der Restklassenring $\mathbb {Z} /p\mathbb {Z}$ ist ein Körper, dessen multiplikative Gruppe die Ordnung $p-1$ hat. Damit gilt $a^{p-1}=1$ für alle $a\in (\mathbb {Z} /p\mathbb {Z} )^{\times }$.

Als ich bei diesem Stand war, kamen mir Zweifel, ob die Begründung, warum es nicht mehr als die zwei genannten Fälle gibt, nicht zu unelementar sein könnte. Allerdings wollte ich den Text auch nicht einfach verwerfen. Meinungen?--Gunther 18:57, 3. Aug 2005 (CEST)

Quelle

Teile des Artikels stammen von hier. Nachgetragen von Markus (Mh26) ✉ 17:11, 5. Mär 2006 (CET).

Teilweise unverständlich

Habe versucht, den letzten Teil (Beispiele) zu entwirren bzw. aufzuzeigen, was die Rechnungen bringen sollen. Der Sinn des folgenden Teils, der aus dem ehem. Artikel Kleiner Fermat-Satz (jetzt ein Redirect) stammt, bleibt mir verschlossen. Daher hierher verschoben:

Es gibt, auf die Modulo-Operation bezogen, noch die dritte Möglichkeit: $1=x\cdot x$:

1. $9^{2}\equiv 1\mod 10$
2. $9^{2}\equiv 1\mod 20$

Während für 1. noch gilt $9\equiv -1\mod 10$, gilt für 2. dieses nicht mehr.

-Markus (Mh26) ✉ 17:11, 5. Mär 2006 (CET)

Das zeigt, dass im Fall zusammengesetzter Moduln die Implikation $x^{2}\equiv 1\implies x\equiv \pm 1$ falsch ist. Das soll vermutlich erklären, warum es keine analoge Aussage zu $a^{(p-1)/2}\equiv \pm 1\mod p$ für den Fall zusammengesetzter Zahlen gibt. Allerdings ist das Beispiel insofern ungünstig gewählt, als für $n=20$ noch $a^{\varphi (n)/2}\equiv 1\mod n$ für alle teilerfremden $a$ gilt.

Ehrlich gesagt würde ich vorschlagen, den gesamten Teil ab "Praktische Anwendung" auf einen kurzen Hinweis auf die fermatschen Pseudoprimzahlen zusammenzustreichen.--Gunther 17:33, 5. Mär 2006 (CET)

Der ganze Artikel hier ist viel zu kompliziert. Beispiele sollten gebracht werden. 2A02:8388:1641:4980:52EB:F6FF:FE28:C651 21:51, 20. Jun. 2023 (CEST)

Beweis

Habe den Beweis wieder entfernt. Bei diesem Zugang muss man so viel erklären, dass der wesentliche Punkt vollkommen untergeht, und ich habe auch nicht den Eindruck, dass man aus diesem Beweis viel über den Satz lernt. Mit minimalem Vorwissen dürfte der Induktionsbeweis leichter nachzuvollziehen sein, und für einen konzeptionellere Betrachtungsweise wird ja auf den Satz von Lagrange verwiesen.--Gunther 11:15, 26. Mär 2006 (CEST)

... und nochmal. Irgendwelche technischen Kleinigkeiten zum Induktionsbeweis sind kaum erhellend. (Bei ihnen ist ja noch nicht einmal relevant, dass p eine Primzahl ist.) Der wesentliche Punkt ist hier der Induktionsschritt und die allgemeinere Feststellung $(a+b)^{p}\equiv a^{p}+b^{p}$.

Wenn bei dem Beweis keine Rolle spielt, ob p eine Primzahl ist, ist da offenbar was faul. Der Fermatsche Satz kann nämlich als Primzahlentest verwendet werden, d.h. für zusammengesetzte Zahlen gilt die Gleichung des Satzes meistens nicht. Ich hatte beim Beiweis eine etwas deutlichere Erklärung angefügt, warum es in der Tat wesentlich ist, dass p eine Primzahl ist. Leider wurden diese Änderungen wieder entfernt. Franz Scheerer

Der Beweis verwendet natürlich, dass p prim ist, aber in dieser Fassung stehen nur die genannten technischen Kleinigkeiten, für die das nicht benötigt wird. Schon deshalb haben sie mit dem Kern des Beweises nichts zu tun.--Gunther 13:04, 30. Mär 2006 (CEST)

Zu der allgemeineren Feststellung

$(a+b)^{p}\equiv a^{p}+b^{p}\mod p$

Falls a,b ganze Zahlen sind, ist auch a+b eine ganze Zahl. Wendet man den Fermatschen Satz auf diese Zahlen an, folgt daraus diese Feststellung, die für mich keineswegs trivial ersichtlich ist, sofern ich den Satz nicht schon als beweisen annehme. Franz Scheerer

Lies bitte genauer: im nächsten Satz steht: sobald man den Satz kennt. Allgemein gilt diese Aussage in jedem kommutativen Ring mit 1, aber im Spezialfall der ganzen Zahlen bleibt aufgrund des k.f.S. keine interessante Aussage mehr übrig.--Gunther 13:04, 30. Mär 2006 (CEST)

Das wird aber in diesem Kontext trivial, sobald man den Satz kennt. Deshalb sehe ich auch hier nicht, dass der Beweis nennenswert zum Verständnis des Satzes beiträgt. Wer einen Beweis haben will, kann ihn im Archiv nachlesen.--Gunther 11:14, 30. Mär 2006 (CEST)

Naja, da könnte man auf den Beweis auch ganz verzichten. Ich hatte angedeutet, wie der Induktionsbeweis im Prinzip funktioniert. Dies waren nur ein paar Zeilen. Für Details hatte ich auf das Archiv verwiesen. Ich verstehe nicht, warum dies wieder entfernt wurde.

Franz Scheerer

Siehe oben: Die letzte Fassung war Kleinkram, der mit dem Kern des Induktionsbeweises nichts zu tun hatte. Wie eine Induktion allgemein funktioniert, müssen wir nicht hier erklären, dafür gibt es einen eigenen Artikel.--Gunther 13:04, 30. Mär 2006 (CEST)

Ach ja: Mit einer Beweisskizze hat Deine Fassung nichts zu tun. Eine Beweisskizze gibt die große Linie und die wesentlichen schwierigen Punkte an, nicht irgendwelche Details, die man sich sowieso denken kann. Im Fall des Induktionsbeweises wäre das z.B.: Ein möglicher Beweis erfolgt durch Induktion über $a$. Der Induktionsschluss beruht auf der Bemerkung, dass für eine Primzahl $p$ die Binomialkoeffizienten in der Formel

$(a+1)^{p}=a^{p}+{p \choose 1}a^{p-1}+\ldots +{p \choose p-1}a+1$

allesamt durch $p$ teilbar sind, also $(a+1)^{p}\equiv a^{p}+1\mod p$ gilt. Oder so.--Gunther 13:52, 30. Mär 2006 (CEST)

Induktionsbeweis ???

Wie soll der denn funktionieren ?

Falls der Satz für alle Primzahlen bis zu einer größten gilt, dann gilt er auch für die nächst größere. Aber wieso ? Vielleicht auch über a. Da für a = 1 die Aussage trivialerweise gilt, braucht man nur zu zeigen, dass die Aussage für a+1gilt, sofern sie für a richtig ist. Dies kann jedoch für a = p-1 offenbar nicht richtig sein. Ok, es genügt die Aussage für a < p zu zeigen. Aber ich habe überhaupt keine Idee wie der Induktionsbeweis funktionieren sollte.

Siehe den Link im Artikel: Man kann per Induktion über $a$ zeigen, dass $a^{p}-a$ durch $p$ teilbar ist. (Mit der Faktorisierung $a(a^{p-1}-1)$ folgt daraus auch unmittelbar die andere Form.)--Gunther 23:04, 28. Mär 2006 (CEST)

Formattierung

Warum wird zwischen einer Zahl und dem Modulo-Operator soviel Platz gelassen und dann dieser auch noch eingeklammert. Ich wäre nie drauf gekommen, dass das ein einziger Term sein soll. Darum hat für mich die Aussage a^p=a keinen Sinn gemacht. Bitte überarbeiten. --DB1BMN 13:23, 23. Apr 2006 (CEST)

Das ist nicht der Modulo-Operator, das ist die Notation für eine Kongruenz. Dieser Artikel ist auch vor und nach der Formel zweimal verlinkt.--Gunther 13:28, 23. Apr 2006 (CEST)

Allgemeinere Form des Satzes?

Ich kenne noch eine allgemeinere Form zu der Form $a^{p-1}\equiv 1\ {\pmod {p}}$ des Satzes, weiß aber nicht ob diese auf Fermat zurückgeht:

$a^{\Phi (n)}\equiv 1\ {\pmod {n}}$ für alle a, n, die teilerfremd (bzw. relativ prim) sind, wobei die Funktion $\Phi$ die Eulerfunktion ist. Somit wäre das Theorem nicht nur auf Primzahlen beschränkt. Das Theorem wie es zur Zeit im Artikel steht, ist ein Spezialfall davon. Beweis:

Da $a^{p-1}\equiv 1\ {\pmod {p}}$ nur gilt, wenn a kein Vielfaches von p ist, und da p eine Primzahl ist, sind a und p immer relativ prim. Zudem gilt für jede Primzahl p:  $\Phi (p)=p-1$. --FreeFred 01:26, 11. Aug 2006 (CEST)

»Allgemein gültig«?

Was bedeutet »allgemein gültig«? Ist das Neuschrieb für »allgemeingültig«, oder ist damit »im allgemeinen gültig« gemeint? --Mulk 22:14, 12. Aug 2006 (CEST)

Umkehrung des Satzes

 Anwendung als Primzahltest
 Der Satz kann daher auch in seiner Umkehrung benutzt werden, um mit hoher Sicherheit zu entscheiden, ob eine Zahl keine Primzahl ist.

die Umkehrung des Satzes ist, ob eine Zahl KEINE Primzahl ist.

-- Küpferl (17:35, 30. Nov. 2009 (CET), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

Im Folgesatz geht es aber genau um den Fall, dass die Zahl eben eine Primzahl ist. --P. Birken 13:33, 6. Dez. 2009 (CET)

Es steht nicht da, was die Umkehrung des Satzes ist, sondern wozu sie benutzt werden kann. --Stefan Birkner 17:46, 6. Dez. 2009 (CET)

Umbenennung "Kleiner fermatscher Satz" in "Kleiner Fermatscher Satz"

Deutsche Rechtschreibung. Regeln und Wörterverzeichnis: Amtliche Regelung Herausgegeben vom Rat für deutsche Rechtschreibung, 2006: "§ 59 Eigennamen schreibt man groß." !!!! (nicht signierter Beitrag von Wilkibur (Diskussion | Beiträge) 16:42, 5. Feb. 2013 (CET))

Das ist die falsche Regel. Siehe http://www.duden.de/sprachwissen/rechtschreibregeln/namen#K135 --AndreasPraefcke (Diskussion) 14:53, 30. Jun. 2015 (CEST)

Groß und klein

Wird in der Wikipedia der Große Fermatsche Satz großgeschrieben, weil er groß ist, und der Kleine fermatsche Satz kleingeschrieben, weil er klein ist, oder ist das ein seltsamer Kompromiss zwischen denen, die die neue Rechtschreibung anwenden, und denen, die sie doof finden? (nicht signierter Beitrag von 92.227.141.192 (Diskussion) 21:20, 28. Sep. 2016 (CEST))

Stimmt, das ist ziemlich seltsam. Und es wird auch mit keinem Wort "Großer Fermatscher Satz" erwähnt. Das wäre doch das erste was man auch wissen möchte, nachdem man den Artikel über den "kleinen" Fermatschen Satz gelesen hat. Vielen Dank schonmal im Voraus an den jenigen der es korrigiert. 94.219.21.9 19:42, 25. Jan. 2019 (CET)

Habe ich einen Denkfehler?

Es soll gelten $a^{p}\equiv a{\pmod {p}}$ mit $a\in \mathbb {Z}$ und $p~Primzahl$:

Sei a = 5 und p = 2, dann ist

$a^{2}=25$

$25\mod 2=1\neq 5$.

Sei a = 5 und p = 3, dann ist

$a^{3}=125$

$125\mod 3=2\neq 5$.

Sei a = 5 und p = 5, dann ist

$a^{5}=3125$

$3125\mod 5=0\neq 5$.

Ohne viel Rechnung gleich drei Gegenbeispiele. Wo ist der Fehler? axp_de^Hallo! 14:10, 19. Mär. 2017 (CET)

Du musst auch a modulo p nehmen, dann stimmt’s. -- HilberTraum (d, m) 16:17, 19. Mär. 2017 (CET)

Eine noch nutzlosere Antwort habe ich selten gesehen. "Du musst auch a modulo p nehmen". Also Sie meinen: 5 mod 3 = 2. Das widerspricht aber immer noch dem Satz. Generell scheint der Satz NUR dann zu gehen, wenn a < p gilt. Was man machen muß, wenn a > p gilt, wird aber NIRGENDWO erklärt. 84.137.7.57 13:19, 3. Okt. 2020 (CEST)

Wenn man in einem CAS mod(11^7,7) eingibt, was der Formel im Satz entspricht, dann erhält man 4 NICHT 7! Also was muß man im CAS eingeben, damit das richtige rauskommt. Ach ja, mod(5^7,7) = 5. 84.137.7.57 13:22, 3. Okt. 2020 (CEST)

Folgerung durch Euler

Ich finde, dass die Formulierung "...dass die rechte Seite der Gleichung ein Vielfaches der Primzahl ist. Damit ist einer der Faktoren ein Vielfaches von p." missverständlich ist, da sie auch zuträfe, wenn der linke (bzw. der rechte) Faktor niemals ein Vielfaches wäre. Streng genommen ist hier eine Fallunterscheidung notwendig, oder zumindest: "Damit muss ein beliebiger der Faktoren ein Vielfaches von p sein." Andernfalls wäre die Folgerung "...kongruent plus oder minus 1" nicht möglich. (Ein zusätzlicher Hinweis darauf, dass p nicht auf die Faktoren aufgeteilt werden kann, weil p prim ist und die Faktoren ganze Zahlen sein müssen, wäre hilfreich aber eigentlich innerhalb der Zahlentheorie obsolet.) --Fredric (Diskussion) 20:07, 14. Nov. 2023 (CET)

Ich wollte gerade eine Diskussion zum gleichen Abschnitt starten, als ich deine Kritik gelesen habe, die meine Frage/Anmerkung sehr stark tangiert.

Vielleicht verstehe ich deine Kritik nicht ganz richtig, aber ich würde sagen, dass "einer der Faktoren" und "ein beliebiger der Faktoren" synonym zu verstehen ist, dort in der Hinsicht also nichts falsches oder Verwirrendes steht. Die von dir geforderte (und wenn auch nicht explizit gezeigte aber dennoch vorhandene) Fallunterscheidung ist doch gerade der Grund, dass das $\pm$ zustande kommt?

Ich finde deinen Punkt gerade deswegen so interessant, da meines Erachtens tatsächlich einer der Faktoren niemals ein Vielfaches von p sein kann: und zwar der, der auf $a^{\frac {p-1}{2}}\equiv +1{\pmod {p}}$ führt. Denn es kann doch in der Einheitengruppe von p (die ja nur Erzeuger enthält) kein $a^{n}$ mit $n<p-1$ die 1 liefern, korrekt? Und ${\frac {p-1}{2}}$ ist schließlich kleiner als $p-1$.

Nun weiß ich nicht, was Euler konkret geschlussfolgert hat (und bin auch zu faul es zu recherchieren) - die Gleichung die im Artikel steht ist ja trotzdem nicht falsch, da sie ja bedeutet $\dots =+1$ oder $\dots =-1$, und ich kann ja an jede wahre Aussage eine falsche "dran-disjunktieren" und die Gesamtaussage wird dadurch nicht falsch. Die Aussage ist also höchstens nicht minimal, und das kann ja durchaus gewollt sein (dann muss ich z.B. nicht erklären, wo der andere Faktor hin ist).

Kann ein Mathematiker bestätigen, dass meine Überlegungen zutreffen? Ich bin Informatikstudent und Mathe ist jetzt nicht unbedingt mein starker Anzug. 😬 --Samorost1 (Diskussion) 14:45, 10. Dez. 2023 (CET)