polynomiale Kongruenz lösen

Neue Frage »

Pumickl Auf diesen Beitrag antworten »
polynomiale Kongruenz lösen
Meine Frage:
Hallo,
ich möchte folgende Aufgabe lösen:

mod 125


Meine Ideen:
ich weiß nicht genau, wie ich hier herangehen soll... ich weiß, dass modulo 125 heißt, dass dies alle Vielfachen von 125 sind.

also gilt es die Gleichung
mit n aus den natürlichen Zahlen zu lösen...

Wie kann ich denn hier herangehen? Mir fehlt die Strategie...
RavenOnJ Auf diesen Beitrag antworten »

Strategie? Das ist eine quadratische Gleichung, kann man also mit dem Standardverfahren lösen. Oder gibt es zusätzliche Bedingungen für x, x ganzzahlig oder so was?
Pumickl Auf diesen Beitrag antworten »

hmm, was ist denn das Standardverfahren?

Also es steht nichts von ganzzahligen Lösungen dran, wobei ich denke, dass wir ganzzahlige Lösungen suchen (wir rechnen in dieser Vorlesung immer nur mit ganzzahligen Zahlen).

Was ändert das denn?

Ich habe mal die Gleichung gelöst und erhalten. Dies ist aber nichts ganzzahliges und ist ja auch nur ein Fall der Kongruenz... Ich möchte aber alle Fälle betrachten.
Monoid Auf diesen Beitrag antworten »

Hier kannst du P-Q-Formel anwenden...
Pumickl Auf diesen Beitrag antworten »

@Mathemathemathe
ich habe die Mitternachtsformel schon angewendet, welche dasselbe Ergebnis liefert wie die P-Q-Formel.

Was mit Probleme bereitet ist die Kongruenz, nicht die Lösung einer quadratischen Gleichung!

Ich möchte diese Gleichung modulo 125 lösen. Deshalb verwende ich auch das Zeichen statt =

Also meine Frage bleibt: Gibt es ein Verfahren das zu lösen? Oder wie könnte ich ansetzen?
Monoid Auf diesen Beitrag antworten »

Dein Beispiel kannst du doch nach diesem Weg lösen. verwirrt

Oder suchst du ganz allgemein?
 
 
Complius Auf diesen Beitrag antworten »

Ich suche ALLE Lösungen für die Gleichungen.

mit

Das nennt sich modulo 125. Hier gilt und usw.

Mit der Mitternachtsformel oder P-Q-Formel bekomme ich jeweils genau eine. Dies müsste ich aber abzählbar unendlich oft wiederholen, um alle Lösungen für n zu erhalten - und da das unendlich lange dauert, suche ich eine allgemeine Lösung und dafür fehlt mir der Ansatz.
RavenOnJ Auf diesen Beitrag antworten »

du suchst alle Lösungen der Gleichung

Also ist Die Lösungsmenge

Mehr gibt es nicht.
jester. Auf diesen Beitrag antworten »

Zitat:
Original von RavenOnJ



Das beantwortet jedoch nicht die Frage, welche Restklassen das sind und wieviele Restklassen die Gleichung eigentlich lösen... (Das ist das gleiche wie zu fragen, wieviele Wurzeln aus es in gibt.)

Das sieht man auch so ein: ist äquivalent zu , es genügt uns also, die Lösungen von zu suchen.
Die Anzahl dieser Lösungen ist also die Anzahl der Lösungen der ursprünglichen Kongruenz.

Überlegen wir uns doch gemeinsam, wieviele Lösungen es gibt: Gibt es eine Lösung , also , so gibt es sicherlich auch zwei, denn und sicherlich .
Nun wollen wir folgendes zeigen: ist eine weitere Lösung der Gleichung, dann unterscheiden sich und nur bis auf das Vorzeichen.
Um das zu zeigen nutze, dass und notwendigerweise Einheiten in sind und es deswegen zwangsweise eine weitere Einheit in diesem Ring gibt, sodass gilt.

Ist die obige Behauptung gezeigt, so wissen wir, dass es, falls eine Lösung existiert, genau zwei Lösungen gibt. Diese zu finden ist dann deine Aufgabe.
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von jester.

Das beantwortet jedoch nicht die Frage, welche Restklassen das sind und wieviele Restklassen die Gleichung eigentlich lösen.


sorry, dann hatte ich die Aufgabe falsch verstanden. Hatte mich auch irgendwie gewundert... So, wie der Threadersteller seinen ersten Post geschrieben hat, war das aber auch misszuverstehen.

Dieses Problem ist natürlich schwieriger.

Gruß
Peter
Mystic Auf diesen Beitrag antworten »

Ja, wie jester ja schon ausgeführt hat, geht es hier hauptsächlich um die Frage, wann die Kongruenz



für eine ungerade Primzahlpotenz lösbar ist und wieviele Lösungen es ggf. gibt...

Klarerweise notwendig dafür ist, dass 4 Teiler von p-1 ist. Ist dies umgekehr erfüllt und g eine Primitivwurzel mod , so sind dann



alle Lösungen mod ...
tmo Auf diesen Beitrag antworten »

Unabhängig von dem elleganten Weg, den jester. und Mystic hier vorgestellt haben, gibt es doch auch eine Methode, die quasi den Vorbote des Hensel-Lifting darstellt (Und bei jedem Polynom so funktioniert).

Man löst (Das geht sogar dann theoretisch mit der pq-Formel, wäre aber nicht sinnvoll, da man ja einfach nur 4 Werte ausprobieren muss).

Ist dann a eine Lösung, so jetzt man mit an, um eine Lösung mod 25 zu gewinnen. Das macht dann so weiter und im nächsten Schritt hat man es ja dann schon.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »