quadratische Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:10 Fr 05.07.2013 | | Autor: | Blubie |
| Aufgabe | | [mm] 3x^2+5x+3 \equiv [/mm] 0 (mod 23) soll ohne durchprobieren gelöst werden. |
Hallo,
wie kann man bei quadratischen Polynomkongruenzen generell vorgehen? Ich habe leider kein tiefes Wissen in diesem Bereich und habe diese Aufgabe im Zuge einer Vorlesung, in der Ingenieure und Mathematiker zusammentreffen, bekommen.
Und noch eine Frage: wenn ich eine Kongruenz f(x) [mm] \equiv [/mm] 0 (mod m) mit f ist ein beliebigs Polynom gegeben habe und [mm] x_{0} [/mm] löst diese Kongruenz. Lösen dann auch immer alle anderen Elemente der Restklasse von [mm] x_{0} [/mm] die Kongruenz?
Grüße
|
|
| |
|
Hallo blubie,
ich nehme es ist bekannt, dass
1) [mm] $\mathbb [/mm] Z /23 [mm] \mathbb [/mm] Z$ ein Körper ist
und dass
2) die Mitternachtsformel in allen Körpern gilt bzw. man quadratisch ergänzen kann.
Damit reduziert sich das Problem darauf die Wurzeln einer Zahl mod 23 zu finden.
Das kann man durch probieren lösen.
Oder durch ein Verfahren, dass für Primzahlen der Form $p [mm] \equiv [/mm] 3 [mm] \mod [/mm] 4$ gilt, lösen. Ist so etwas bekannt?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:38 Fr 05.07.2013 | | Autor: | Blubie |
nein mir ist nichts von beiden bekannt. ich dachte beim modulo rechnen betrachtet man ganze zahlen und nicht die elemente des restklassenrings? die mitternachtsformel liefert nur imaginäre zahlen :(
|
|
|
| |
|
Hallo Blubie,
> nein mir ist nichts von beiden bekannt.
Hm. Schade.
> ich dachte beim
> modulo rechnen betrachtet man ganze zahlen und nicht die
> elemente des restklassenrings?
Nein, das ist falsch. Allerdings darfst Du ganze Zahlen als Repräsentanten von Elementen des Restklassenrings verwenden. 
> die mitternachtsformel
> liefert nur imaginäre zahlen :(
...was hier weiterhilft.
Du kannst Deine quadratische "Gleichung" (genauer: Äquivalenz) so umformen, dass Du [mm] x^2-6x+1\equiv 0\mod{23} [/mm] erhältst. Das sieht ja schonmal freundlicher aus. Nur bleibt die Frage: was ist hier eigentlich [mm] \wurzel{8}?
[/mm]
Hilfreicher ist folgende äquivalente Darstellung:
[mm] x^2-6x-91\equiv 0\mod{23}
[/mm]
Findest Du selbst den Weg dahin, und weiter zur Lösung?
Grüße
reverend
PS: Die zweite Frage in Deinem ersten Post müsste damit übrigens auch beantwortet sein!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:03 Fr 05.07.2013 | | Autor: | Blubie |
Ich habe auch in anderen Skripten nachgeschaut und überall definiert man die Kongruenz so: a [mm] \equiv [/mm] b (mod m) :<=> m|(b-a) für ganze Zahlen a,b und eine natürliche Zahl m. (Das wird auch so bei Wikipedia gemacht). Aber wenn ich das richtig lese gilt das Folgende [mm] f(x_{0}) \equiv [/mm] 0 (mod m) => [mm] f(x_{1}) \equiv [/mm] 0 (mod m) für alle [mm] x_{1} [/mm] aus dem Restklassenring von [mm] x_{0} [/mm] mod m. Das kann man auch sehr leicht zeigen, habe ich gemerkt.
Ich kenne eine Menge Umformungsregeln für die Modulo-Rechnung, jedoch gehört das Division nicht dazu und ich sehe nicht, wie man das hier anstellen könnte. Welches Gesetzt/Satz hast du denn da angewendet?
Grüße
|
|
|
| |
|
reverend hat die Gleichung schlicht mit [mm] $3^{-1}\equiv [/mm] 8 [mm] \mod [/mm] 23$ multipliziert.
Und dass du in Restklassenringen (oder wie hier Körpern) nicht invertieren kannst ist eine massive Wissenslücke.
Schlag in deinen Unterlagen nochmal den erweiterten euklidischen Algorithmus nach.
Der Ansatz über
$ [mm] x^2-6x-91\equiv 0\mod{23} [/mm] $
ist hier sehr elegant,
der übers Wurzelziehen ist allgemein sehr hilfreich.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:23 Fr 05.07.2013 | | Autor: | Blubie |
Das bedeutet also, dass alle Elemente aus der Restklasse 13 mod 23 sowie aus der Restklasse -7 mod 23 die Kongruenzgleichung lösen (die Nullstellen des Polynoms)? Oder kann es noch andere Lösungen geben? Bei Kongruenzen ist mir das leider nicht so klar.
Ok, ich wusste auch vorher wie man das multiplikativ inverse bestimmt, also ein x, so dass a*x [mm] \equiv [/mm] 1 (mod m). Bezogen auf diese Äquivalenzgleichung ist mir das aber nicht klar. Mit 8 durchmultiplizieren:
[mm] 24x^2+40x+24 \equiv [/mm] 0 (mod 23) und ich weiß 24 [mm] \equiv [/mm] 1 (mod 23). Aber wie mache ich weiter um auf eure darstellung zu kommen?
EDIT: Ich weiß jetzt wie es geht: [mm] 24x^2+40x+24 \equiv [/mm] 0 (mod 23) => [mm] x^2+40x+24 \equiv -23x^2 [/mm] (mod 23) => [mm] x^2+40x+24 \equiv [/mm] 0 (mod 23).
Meine Frage, ob es mglw. noch andere Lösungen gibt, bleibt aber offen.
grüße
|
|
|
| |
|
> Das bedeutet also, dass alle Elemente aus der Restklasse 13
> mod 23 sowie aus der Restklasse -7 mod 23 die
> Kongruenzgleichung lösen (die Nullstellen des Polynoms)?
Ja.
> Oder kann es noch andere Lösungen geben? Bei Kongruenzen
> ist mir das leider nicht so klar.
Nein in diesem Fall sind das alle.
> Ok, ich wusste auch vorher wie man das multiplikativ
> inverse bestimmt, also ein x, so dass a*x [mm]\equiv[/mm] 1 (mod m).
> Bezogen auf diese Äquivalenzgleichung ist mir das aber
> nicht klar. Mit 8 durchmultiplizieren:
> [mm]24x^2+40x+24 \equiv[/mm] 0 (mod 23) und ich weiß 24 [mm]\equiv[/mm] 1
> (mod 23). Aber wie mache ich weiter um auf eure darstellung
> zu kommen?
Es ist $24 [mm] \equiv [/mm] 1 [mm] \mod [/mm] 23$ und [mm] $40\equiv -6\mod [/mm] 23$.
Ich verstehe nicht was hier noch unklar sein kann.
> EDIT: Ich weiß jetzt wie es geht: [mm]24x^2+40x+24 \equiv[/mm] 0
> (mod 23) => [mm]x^2+40x+24 \equiv -23x^2[/mm] (mod 23) => [mm]x^2+40x+24 \equiv[/mm]
> 0 (mod 23).
> Meine Frage, ob es mglw. noch andere Lösungen gibt,
> bleibt aber offen.
Da [mm] $\mathbb [/mm] Z/23 [mm] \mathbb [/mm] Z$ ein Körper(es würde sogar Int.ring genügen) ist, hat ein Polynom f höchstens deg(f) viele Nullstellen.
> grüße
|
|
|
|
