Lösungen von x^2 + x = 0 in Z/pZ

29.07.2023, 11:03

KonverDiv

Lösungen von x^2 + x = 0 in Z/pZ

Wenn $\begin{eqnarray*} p > 0 \end{eqnarray*}$ eine Primzahl ist, warum hat die Gleichung $\begin{eqnarray*} x^2 + x = 0 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb{Z}/p\mathbb{Z} \end{eqnarray*}$ dann zwei Lösungen?

Ich habe mal angefangen mit $\begin{eqnarray*} x^2 + x = (x + 1)(x + 0) = 0 \end{eqnarray*}$ . Damit hat man also immer die triviale Lösung $\begin{eqnarray*} x = 0 \end{eqnarray*}$ und eine Lösung mit $\begin{eqnarray*} x = -1 \end{eqnarray*}$ . Wenn ich -1 jetzt im Kontext der Restklasse interpretiere, dann ist dies ja gerade das Element $\begin{eqnarray*} p-1 \end{eqnarray*}$ .

Ich habe mir ein paare Multiplikationstabellen für $\begin{eqnarray*} \mathbb{Z}_2 \end{eqnarray*}$ , $\begin{eqnarray*} \mathbb{Z}_3 \end{eqnarray*}$ und $\begin{eqnarray*} \mathbb{Z}_5 \end{eqnarray*}$ erstellt und das Muster scheint zu sein, dass $\begin{eqnarray*} 1\cdot 1 = 1 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb{Z}_2 \end{eqnarray*}$ , $\begin{eqnarray*} 2 \cdot 2 = 1 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb{Z}_3 \end{eqnarray*}$ und $\begin{eqnarray*} 4 \cdot 4 = 1 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb{Z}_5 \end{eqnarray*}$ . Das heißt das multiplikative Inverse zu $\begin{eqnarray*} p-1 \end{eqnarray*}$ ist in $\begin{eqnarray*} \mathbb{Z}_p \end{eqnarray*}$ immer $\begin{eqnarray*} p-1 \end{eqnarray*}$ , wenn $\begin{eqnarray*} p \end{eqnarray*}$ eine Primzahl ist

Eine richtige Begründung, warum $\begin{eqnarray*} x^2 + x = 0 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb{Z}/p\mathbb{Z} \end{eqnarray*}$ zwei Lösungen hat, finde ich, ist das nicht. Wie würde man das richtig begründen? verwirrt

29.07.2023, 12:04

Elvis

Auf diesen Beitrag antworten »

In Körpern oder Integritätsbereichen hat jede quadratische Gleichung höchstens zwei Lösungen. In allgemeinen Ringen kann sie mehr Lösungen haben. $\begin{eqnarray*} \mathbb Z/p\mathbb Z \end{eqnarray*}$ ist ein Körper. Für p=2 treten alle 3 Möglichkeiten auf. $\begin{eqnarray*} x^2 +x+1=0 \end{eqnarray*}$ hat keine Lösung, $\begin{eqnarray*} x^2 =0 \end{eqnarray*}$ hat eine Lösung, $\begin{eqnarray*} x^2 +x=0 \end{eqnarray*}$ hat zwei Lösungen. Alle drei möglichen Fälle treten in jedem Körper auf. Wenn eine Lösung a existiert, kann man das quadratische Polynom durch x-a dividieren und erhält eine weitere Lösung b, die gleich a oder von a verschieden sein kann. Das erklärt, warum $\begin{eqnarray*} x^2 +x=x(x+1)=0 \end{eqnarray*}$ modulo p immer die Lösungen 0 und p-1=-1 hat.

$\begin{eqnarray*} (p-1)^2 =p^2 - 2p+1^2 =p^2 - 2p+1\equiv 1\mod p \end{eqnarray*}$ ist die Begründung dafür, dass modulo p stets p-1 selbstinvers ist.

29.07.2023, 12:31

KonverDiv

Auf diesen Beitrag antworten »

Hallo @Elvis,

ich verstehe! Auch deine letzte Anmerkung bezüglich $\begin{eqnarray*} (p-1)^2 \end{eqnarray*}$ fand ich hilfreich!

29.07.2023, 16:31

Elvis

Auf diesen Beitrag antworten »

"Alle drei möglichen Fälle treten in jedem Körper auf."
Diese Bemerkung sollten wir ganz schnell wieder vergessen, alldieweil sie falsch ist. In algebraisch abgeschlossenen Körpern wie z.B. in den komplexen Zahlen hat jedes quadratische Polynom genau eine doppelte Nullstelle oder zwei einfache Nullstellen.
Den "Fundamentalsatz" der klassischen Algebra, nach dem jedes komplexe Polynom n-ten Grades mit Vielfachheit gezaehlt genau n komplexe Nullstellen hat, hat Carl Friedrich Gauß in seiner Doktorarbeit als erster und später auf mehr als eine Weise bewiesen. Sehr geehrter Herr Professor Gauß, ich bitte Sie untertaenigst um Entschuldigung.
Übrigens gibt es es über jedem Körper bis auf Isomorphie genau einen algebraischen Abschluss, das ist eine Körpererweiterung, in dem der Fundamentalsatz gilt. Vermutlich hat dies Leopold Kronecker als erster bewiesen, ich weiß aber nicht mehr, wo und wann.

29.07.2023, 17:11

IfindU

Auf diesen Beitrag antworten »

Ein Punkt auf den noch nicht explizit eingegangen wurde: Falls $\begin{eqnarray*} p \end{eqnarray*}$ nicht prim ist, hat man keine Nullteilerfreiheit. Das führt dazu, dass man potentiell mehr als 2 Lösungen findet. Ansonsten funktioniert die Betrachtung vom Eingangspost auch für andere Modulo. Nirgendwo hat man für die Existenz der 2 Lösungen benötigt, dass $\begin{eqnarray*} p \end{eqnarray*}$ prim ist.

26.04.2026, 14:16

yogibär

Auf diesen Beitrag antworten »

2 ist eben doch ein Sonderfall unter den Primzahlen. Nennen wir deinen Körper doch wie üblich F_p .

Grundsätzlich sollte klar sein: Ein Polynom n_ten Grades kann höchstens n Wurzeln haben. Das ist in jedem Körper so.

Beginnen wir also mit F2 . Man rechnet leicht nach, dass x1 = 0 so wie x2 = 1 die beiden gesuchten Wurzeln sind.

ich symmetrisiere grundsätzlich - was in der Literatur nicht immer konsistent durch gehalten wird.

Dass sich auch Wolfram stur weigert, meine Konvention anzunehmen, ist für mich ein stetes Ärgernis.

Jede Primzahl p ist ungerade. In symmetrischer Notation

F_p = { 0 , + - [ 1 , ... , 1/2 ( p - 1 ) ] } ( 1 )

x ² + x = 0 | - x ( 2 )

Subtraktion ist ja ausführbar.

x ² = ( - x ) | : x ( 3 )

Auch hier finden wir die triviale Wurzel x1 = 0 . Wenn aber x nicht verschwindet, ist die Division zulässig:

x2 = ( - 1 ) ( 4 )

26.04.2026, 15:54

adiutor62

Auf diesen Beitrag antworten »

Für x=0 ist die Division nicht definiert bzw. verboten.
Die Lösung x= 0 geht dabei zudem verloren:

$\begin{eqnarray*} x^2 = -x| :x \end{eqnarray*}$

$\begin{eqnarray*} x= -1 \end{eqnarray*}$

27.04.2026, 11:14

Leopold

Auf diesen Beitrag antworten »

Warum wird hier eine Aufgabe „gelöst“, die der Fragesteller am 13. Dezember 1874 schon selbst gelöst hat? Die Nullteilerfreiheit sagt doch alles:

$\begin{align*} x^2 + x = 0 \ \ \Leftrightarrow \ \ x(x+1) = 0 \ \ \Leftrightarrow \ \ x = 0 \ \vee \ x = -1 \end{align*}$

Das gilt in jedem Körper, Charakteristik egal. Und die eigentliche Frage wurde von Elvis hinreichend beantwortet.

Das MatheBoard trocknet gerade aus, was Selbstdarsteller zur Selbstbefriedigung nutzen. Vermutlich werden mathematische Fragen heute eher der KI gestellt. Und den Antworten wird auch noch gleich kritiklos geglaubt. Das ist der Lauf der Zeit. Ich finde es aber gut, daß es das MatheBoard weiterhin gibt, für die alten Herren (und die ein oder andere ältere Dame). Es wäre schade, wenn es eingestellt würde. Es war immerhin eine schöne Zeit, und ab und zu gibt es ja doch noch das ein oder andere zu finden oder zu besprechen, wenn auch exponentiell abklingend.

27.04.2026, 12:02

Elvis

Auf diesen Beitrag antworten »

Mit Gemini kann man sich gut über Mathematik und Philosophie unterhalten, wenn man selbst denkt. Seit ein paar Wochen studiere ich Stewart Shapiro (1997) "Philosophy of Mathematics: Structure and Ontology". Das Buch kann ich bestens empfehlen, auch weil es meine Ansichten zur Mathematik als Strukturtheorie unterstützt. Shapiro weiß natürlich viel mehr als ich und kann als Philosoph weit besser argumentieren und formulieren, als ich das jemals könnte. Die Diskussion mit Gemini nach jedem Paragraphen läuft meistens darauf hinaus, dass die KI sich von mir erklären lässt, was der Autor uns sagen will, und manchmal lerne ich etwas daraus.
Wenn man die KI nur fragt, bekommt man kurze Antworten, die zu etwa 50% einen Teil des Textes richtig interpretieren, zum Teil aber auch das Thema verfehlen oder am Kern der Sache vorbei gehen oder zum Teil ganz falsch sind. Falls Studierende die KI benutzen, um Mathematik zu lernen und zu verstehen, werden sie genau so unfähig werden wie Schüler, die wegen der Taschenrechner verlernt haben zu rechnen und zu denken, und am Ende des Verdummungsprozesses wird die KI tatsächlich intelligenter sein als die Menschen.

27.04.2026, 13:38

HAL 9000

Auf diesen Beitrag antworten »

@Leopold

Tatsächlich wird man hier schon mal fast totgesagt, wenn man sich (aus den von dir genannten Gründen) wochenlang nicht zu Wort meldet. Augenzwinkern

P.S.: War jetzt mein erster Post nach knapp vier Wochen Stille, jetzt also wieder Timer-Restart...

27.04.2026, 14:25

Leopold

Auf diesen Beitrag antworten »

Augustus de Morgan, der Logiker, soll zu einer Meldung über sein Ableben gesagt habe, daß er „derzeit noch nicht ganz bereit sei, dieser Schlussfolgerung zuzustimmen“.

Und der Schriftsteller Mark Twain mit seinem satirisch-ironischen Humor bemerkte bei ähnlichem Anlaß: „Die Berichte über meinen Tod sind stark übertrieben.“

Du befindest dich also in bester Gesellschaft.

27.04.2026, 15:42

Conny_1729

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Wenn man die KI nur fragt, bekommt man kurze Antworten, die zu etwa 50% einen Teil des Textes richtig interpretieren, zum Teil aber auch das Thema verfehlen oder am Kern der Sache vorbei gehen oder zum Teil ganz falsch sind. Falls Studierende die KI benutzen, um Mathematik zu lernen und zu verstehen, werden sie genau so unfähig werden wie Schüler, die wegen der Taschenrechner verlernt haben zu rechnen und zu denken, und am Ende des Verdummungsprozesses wird die KI tatsächlich intelligenter sein als die Menschen.

Ja, bei jedem Werkzeug, das man nutzt, stellt sich stets das Problem, mit welcher Fertigkeit man dieses zu bedienen in der Lage ist. KI ist eine sehr schöne Sache, die ihre Nutzer aber in zwei Lager zu separieren scheint. Die einen werden immer dümmer, während die anderen das Potential haben, immer mehr aus dieser „Intelligenz“ schöpfen zu können. Um mal wieder Forrest Gump in einer abgewandelten Form zu zitieren: Dumm ist der, der Dummes fragt. – Und wer Dummes fragt, bekommt dumme Antworten, und dumme Antworten führen letztendlich zu dummen Handlungen.

KI kann man so sehen, wie den hochwertigen Stab beim Stabhochsprung. Wenn man alle Fitness und Willensstärke für diese Disziplin in sich vereinbart, kann man sich vielleicht über die 6-Meter-Hürde schwingen. Wenn man dagegen völlig untrainiert und unmotiviert ist sowie in Hausschuhen gekleidet sich behäbig dem Einstichkasten nähert, diesen dann grandios verfehlt, dann kommt man noch der vor der Matte zum Erliegen, wobei einem Stab und Stange gleichzeitig auf den Kopf donnern.

Die Frage ist also, nutzen wir KI-Tools als Support oder als Ersatz des eigenen Denkens?

Gruß
Conny

27.04.2026, 16:40

Elvis

Auf diesen Beitrag antworten »

@Leopold

Wir hatten vor langer Zeit eine Diskussion über die Kontinuumshypothese, und du hattest die Frage an mich gestellt, warum ich einerseits an die Unabhängigkeit des Parallelenaxiom von den anderen Axiomen der euklidischen Geometrie und an euklidische, elliptische und hyperbolische Geometrie glaube und andererseits trotz Gödel (V=L) und Cohen (Forcing) fest davon überzeugt bin, dass die Kontinuumshypothese entweder wahr oder falsch ist.
Damals hatte ich noch keine Antwort, jetzt bin ich mit Shapiro so weit, dass ich eine für mich überzeugende Antwort formulieren kann:
Die Axiome der euklidischen Geometrie und die übliche Logik sind nicht stark genug, um über das Parallelenaxiom zu entscheiden. Die drei wesentlich verschiedenen Geometrien haben wir, und wir kennen Modelle für diese Geometrien.
Die Axiome der Mengenlehre, insbesondere ZFC, sind mit der Prädikatenlogik erster Stufe PL1 ebenfalls zu schwach, um die Kontinuumshypothese zu entscheiden. Es ist daher möglich, Modelle in der Mengenlehre zu konstruieren, in denen diese einmal wahr und einmal falsch ist. Die Modelle beliebiger unendlicher Kardinalität, die nach Löwenheim-Skolem in der Mengenlehre existieren, sind für mich aber keine Modelle der natürlichen Zahlen.
Shapiro erläutert, dass Dedekind und andere die natürlichen Zahlen nicht in der Mengenlehre mit PL1 sondern mit den Dedekind-Peano-Axiomen und PL2 definieren. Damit wird die Struktur $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ eindeutig bis auf Isomorphie (Shapiro: "categorical"), ebenso die reellen Zahlen, die gesamte Arithmetik und die Zahlentheorie. Gemeinsam mit Shapiro glaube ich nicht nur an die reale Existenz von mathematischen Strukturen sondern auch daran, dass jede Aussage entweder wahr oder falsch ist, also auch die Kontinuumshypothese.

27.04.2026, 23:38

Luftikus

Auf diesen Beitrag antworten »

Ich denke, dass in Hinsicht auf Gödel, nach dem jedes hinreichend komplexes Aussagensystem entweder widersprüchlich ist oder wahre unbeweisbare Aussagen enthält, die unentscheidbaren Aussagen, die weder wahr noch falsch bewiesen werden können und zu keinen Widersprüchen führen, eben dann als Axiome postuliert werden können. Aber deren Widerspruchsfreiheit lässt sich ebenfalls nach Gödel nicht beweisen. Da hilft nur die Erfahrung mit Modellen, die diese Axiome beinhalten.

28.04.2026, 09:04

Elvis

Auf diesen Beitrag antworten »

Gödel hilft da überhaupt nicht weiter, denn er hat in seinem Vollständigkeitssatz gezeigt, dass jede PL1 Theorie vollständig ist. Die Unvollständigkeitssätze beziehen sich ja gerade auf die PL2 Theorie Principia Arithmetica und verwandte Systeme.
Dass eine Aussage in einem formalen System nicht entscheidbar ist, schließt nicht aus, dass sie entweder wahr oder falsch ist. Die dritte Möglichkeit, dass CH unabhängig von ZFC ist, und in einem Modell von ZFC wahr, in einem anderen Modell von ZFC falsch ist, habe ich bereits bemerkt.
Diese dritte Möglichkeit schließe ich in der Arithmetik dadurch aus, dass ich von der PL1 zur PL2 übergehe und damit die Modelle bis auf Isomorphie festlege. Dann muss CH entweder wahr oder falsch sein, was allerdings noch nicht heißt, dass sie in der Arithmetik entscheidbar ist. Wenn wir wissen, dass sie wahr oder falsch ist, können wir sie nicht einfach als neues Axiom wählen.

28.04.2026, 13:05

Luftikus

Auf diesen Beitrag antworten »

Also, für mich da als Laie hat schon mal überrascht, dass
Wahrheit != Beweisbarkeit
ist. Offenbar braucht es da eine (semantische) "Metatheorie", in der Aussagen dann wahr sind. Insofern sind da alle Aussagen über ein System dann wohl entweder wahr oder falsch.
Wählt man nun da eine endliche Anzahl von Aussagen als Axiome, so können bei Widerspruchsfreiheit aber nicht alle Aussagen bewiesen werden, das Axiomensystem ist (notwendigerweise) unvollständig. Solche Aussagen verstehe ich als (in dem Axiomensystem) nicht entscheidbar.
Im Falle von ZFC + CH kann nur eine "relative Widerspruchsfreiheit" nachgewiesen werden, wie auch für ZFC + !CH. Das ermöglicht im Rahmen ZFC widerspruchsfreie Modelle mit CH oder !CH, je nach Metatheorie.
Insofern lässt sich dann CH oder !CH als weiteres Axiom postulieren. Sehe ich das richtig?

28.04.2026, 22:43

Elvis

Auf diesen Beitrag antworten »

Das hängt nicht davon ab, wie viele Axiome es in einer Theorie gibt. In ZFC ist CH keine entscheidbare Aussage, denn es ist eine Aussage über Teilmengen der reellen Zahlen. In ZFC kann man nur alle Aussagen über Mengen entscheiden.
ZFC+PL1 ist vollständig, das sagt Gödels Vollständigkeitssatz. Die Arithmetik+PL2 ist unvollständig, das sagt Gödels Unvollständigkeitssatz.
Semantische Metatheorien gibt es nicht. Es gibt verschiedene Theorien mit unterschiedlichen Logiken.
Theorie über simple Objekte mit schwacher Logik ist vollständig, Theorie über komplizierte Objekte mit starker Logik ist unvollständig. Das hat vor 100 Jahren jeden Mathematiker überrascht, und heute ist es immer noch schwer zu begreifen.
Ob eine Theorie eine bestimmte Aussage entscheiden kann, hängt sowohl an der Theorie als auch an der Logik. ZFC ist als Theorie zu schwach, CH zu entscheiden, obwohl PL1 vollständig ist. Ob Arithmetik als Theorie mit PL2 CH entscheiden kann, wissen wir noch nicht, weil es nach Gödel wahre Aussagen gibt, die nicht entscheidbar sind.
Wie man die Mengenlehre ZFC durch weitere Axiome ergänzen und/oder die bestehenden Axiome verändern sollte, daran scheiden sich die Geister. Der eine meint dies, die andere meint das, und tausend Mathematikinnen und Philosophen wägen Vor- und Nachteile gegeneinander ab und können sich nicht einigen. (Wenn wir die Mengenlehre durch ZFH+CH definieren und in 100 Jahren findet ein kluger Mensch ein Gegenbeispiel, dann haben wir einen Fehler gemacht. Der Mengenlehre ist das egal, der Mathematik aber nicht.)
Es gibt auch noch Mathematiker und andere Leute, die eine andere Logik vorziehen, in der nicht jede Aussage entweder wahr oder falsch ist. Fast alle Menschen halten Mathematik und Logik zurecht für unbegreiflich und zu unrecht für überflüssig.

Neue Frage »

Antworten »

Lösungen von x^2 + x = 0 in Z/pZ

Verwandte Themen