quadratische kongruenzen

11.07.2013, 20:40

Matheversteher

quadratische kongruenzen

Hallo alle zusammen Wink

Ich möchte folgende Gleichung lösen:
$\begin{eqnarray*} x^2-2x-1=0 \mod 7 \end{eqnarray*}$

1.) Ich habe zuerst einmal die Diskriminante gebildet
$\begin{eqnarray*} disc = 4+4=8 \equiv 1 \mod 7 \end{eqnarray*}$
--> das heißt es gibt 2 Lösungen, da $\begin{eqnarray*} 1\neq0 \end{eqnarray*}$

2.) Nun kann ich die Lösungen über die Mitternachtsformel berechnen:
$\begin{eqnarray*} x_1=\frac{2-1}{2}= 4 \end{eqnarray*}$
$\begin{eqnarray*} x_2=\frac{2+1}{2}=12\equiv 5 \mod 7 \end{eqnarray*}$

und hier ist meine Frage dazu, wie komme ich auf die 4 bzw auf 12, ich müsste ja jeweils durch zwei Teilen!? DOch wie sieht das bei den Restklassen aus? verwirrt

Ich hoffe mir kann jemand erklären wie ich das bei den Kongruenzen berechne, da ich nächste Woche eine Klausur in elementarer Zahlentheorie schreibe. Vielen Dank smile

11.07.2013, 21:23

alterHund

Auf diesen Beitrag antworten »

Hallo Matheversteher

die 4:
2-1+7 = 8
die 12 ??? nimm 2+1+7 = 10, da kommst Du gleich auf 5
im
übrigem hätt ich das Original
zu
x^2 - 2x - 1 = 0 mod 7 zu
x^2 - 2x - 8 = 0 mod 7 umgeformt
dann
geht's mit der "pq-Formel"

11.07.2013, 22:05

Matheversteher

Auf diesen Beitrag antworten »

Hallo alterHund smile

danke für deine schnelle Antwort.
Ähm sehe ich das richtig,

ich nehme den Zähler, in die diesem fall 2-1 und 2+1 und addiere dort noch das m (aus dem mod m) zu. und Teile das durch den Nenner?
Also:
$\begin{eqnarray*} \frac{2-1+m}{2}= \frac{2-1+7}{2}=4 \end{eqnarray*}$ und dann habe ich meine Lösung.
Für die zweite Lösung folgt dies Analog.

Was mache ich denn(in meine Beispiel), wenn der Zähler nach der Addition ungerade wird? Dann kann ich ja nicht durch 2 teilen. Oder verzichte ich dann auf die Addition? (Gibt es einen allgemeinen Algorithmus hierfür? Etwa wenn mod m (für $\begin{eqnarray*} m = prim \end{eqnarray*}$ bzw $\begin{eqnarray*} m \neq prim \end{eqnarray*}$ ist?)

Zitat:

Zitat
x^2 - 2x - 8 = 0 mod 7 umgeformt

Warum es dann mit der pq-Formel geht ist für mich nicht ersichtlich, bzw wie komme ich dazu es so umzoformen, dass es für die pq-Formel hinaut? Ich hoffe du verstehst was ich meine?!

11.07.2013, 22:14

watcher

Auf diesen Beitrag antworten »

Hallo matheversteher,

um $\begin{eqnarray*} \frac{a}{b} \mod m \end{eqnarray*}$ zu berechnen berechnet man das Inverse zu b.
Es ist ja a/b ja nur eine andere Schreibweise für $\begin{eqnarray*} a\cdot b^{-1} \end{eqnarray*}$ .
Wie man multiplikativ Inverse im Restklassenring ausrechnet müsste in deinem Skript stehen.

Zitat:

x^2 - 2x - 8 = 0 mod 7 umgeformt Warum es dann mit der pq-Formel geht ist für mich nicht ersichtlich, bzw wie komme ich dazu es so umzoformen, dass es für die pq-Formel hinaut? Ich hoffe du verstehst was ich meine?!

Das geht genauso wie auch mit dem anderen Term.
Man kann hier dem Term die Nullstellen (4,-2) mit Vieta relativ gut ansehen.

P.S. Das mit der p-q-Formel klappt nur wenn m prim ist, und wir daher in einem Körper arbeiten. Sonst hilft u.U. der chinesische Restsatz oder das Legendre-Symbol.

12.07.2013, 00:11

Matheversteher

Auf diesen Beitrag antworten »

Zitat:

Zitat
um $\begin{eqnarray*} \frac{a}{b} \mod m \end{eqnarray*}$ zu berechnen berechnet man das Inverse zu b. Es ist ja a/b ja nur eine andere Schreibweise für $\begin{eqnarray*} a\cdot b^{-1} \end{eqnarray*}$ .
Wie man multiplikativ Inverse im Restklassenring ausrechnet müsste in deinem Skript stehen.

Ok, also:

$\begin{eqnarray*} x_1=1\cdot 2^{-1} \leftrightarrow 2 \cdot x \equiv 1 \mod 7 =4 \end{eqnarray*}$ , denn $\begin{eqnarray*} 2\cdot4=8\equiv 1 \mod 7 \end{eqnarray*}$

für x_2 ist das dann so?!

$\begin{eqnarray*} x_2=3\cdot2^{-1} \leftrightarrow 2\cdot x =3 \mod 7 \end{eqnarray*}$ , somit $\begin{eqnarray*} x_2= 5 \end{eqnarray*}$ , denn $\begin{eqnarray*} 2\cdot5 = 10\equiv 3 \mod7 \end{eqnarray*}$ .

Habe das jetzt mal step by step aufgeschrieben, damit ihr beiden nachvollziehen könnt ob es richtig ist, so wie ich es gemacht habe.

Aber schonmal vielen Dank euch beiden (ich hoffe ich bekomme noch mal eine Antwort) smile

Nachtrag 1: Meine beiden Lösungen sind also $\begin{eqnarray*} x_1=4 \end{eqnarray*}$ und $\begin{eqnarray*} x_2 = 5 \end{eqnarray*}$ , somit habe ich $\begin{eqnarray*} (x-4)(x-5)=x^2-9x+20x\equiv x^2-2x-1 \mod 7 \end{eqnarray*}$ .

Nachtrag 2: Ich habe auch noch eine Frage zur Diskriminante:
Ich dachte bis gerade, dass meine quadratische Gleichung mod m lösbar ist, wenn meine Diskriminante $\begin{eqnarray*} \geq 0 \end{eqnarray*}$ ist.

Dies scheint aber nicht der Fall zu sein. Denn ich könnte $\begin{eqnarray*} x^2-2x-1=0 \end{eqnarray*}$ auch als $\begin{eqnarray*} x^2-2x+6 = 0 \mod 7 \end{eqnarray*}$ schreiben.
Dann wäre $\begin{eqnarray*} disc=4-4\cdot6=-20 \end{eqnarray*}$ und hätte demnach keine Lösung, da $\begin{eqnarray*} -20<0 \end{eqnarray*}$ ?! Wie wir sehen gibt es aber Lösungen. Was muss für die Diskriminante gelten? Muss sie als quadratisch darstellbar sein? Sprich $\begin{eqnarray*} -20\equiv 1 \mod 7 \end{eqnarray*}$ , somit $\begin{eqnarray*} 1=1^2 \end{eqnarray*}$ verwirrt

12.07.2013, 08:08

watcher

Auf diesen Beitrag antworten »

Ich kann nicht wirklich nachvollziehen was du tust.
Mir scheint du "löst" mit dem Wissen um die richtige Lösung.

Was ist denn jetzt $\begin{eqnarray*} 2^{-1} \mod 7 \end{eqnarray*}$ und wie berechnet man so ein Inverses?

Nachtrag 1 ist richtig und nicht sonderlich überraschend, denn für jeden Körper K gilt:
Ist a eine Nullstelle von $\begin{eqnarray*} f \in K[X] \end{eqnarray*}$ so ist $\begin{eqnarray*} (X-a)|f \end{eqnarray*}$ .

Nachtrag 2:

Zitat:

dass meine quadratische Gleichung mod m lösbar ist, wenn meine Diskriminante $\begin{eqnarray*} \geq 0 \end{eqnarray*}$ ist.

Das ist eine ziemlich unbedachte Übernahme einer Eigenschaft der rellen Zahlen.
Endliche Körper (generell Körperder Charakteristik p) sind nicht anordbar (lässt sich nleicht zeigen), daher macht eine Aussage wie x>0 dort keinerlei Sinn, genausowenig wie in den komplexen Zahlen.
Die richtige Formulierung der Bedingung der man verallgemeinern kann ist:
Eine quadratische Gleichung ist lösbar wenn die Diskriminante eine Quadratzahl ist, d.h. wenn ein $\begin{eqnarray*} b \in K \end{eqnarray*}$ existiert mit $\begin{eqnarray*} b^2=D \end{eqnarray*}$ .
In den rellen Zahlen ist das gleichwertig mit $\begin{eqnarray*} D\geq 0 \end{eqnarray*}$ .

Mal ganz abgesehen davon ist die Diskriminante ein Element des Körpers, also in dem Bsp.
$\begin{eqnarray*} D\equiv -20\equiv 1 \mod 7 \end{eqnarray*}$

12.07.2013, 11:26

Matheversteher

Auf diesen Beitrag antworten »

Vielen Dank zu deinen Antworten zu meinen Nachträgen smile

Zum Inversen Element:

Zitat:

Zitat
Was ist denn jetzt $\begin{eqnarray*} 2^{-1} \mod 7 \end{eqnarray*}$ und wie berechnet man so ein Inverses?

Ähm ja gute Frage, die Formel für mein Inverses lautet:
$\begin{eqnarray*} ab\equiv 1 \mod m \end{eqnarray*}$

Das heißt für $\begin{eqnarray*} x_1=1\cdot 2^{-1} \end{eqnarray*}$ suche ich ein $\begin{eqnarray*} x_1 \end{eqnarray*}$ sodass 1 heraus kommt:
$\begin{eqnarray*} x_1=1\cdot 2^{-1} \mod 7 \end{eqnarray*}$ (an dieser Stelle habe ich dann $\begin{eqnarray*} \cdot 2 \end{eqnarray*}$ gerechnet )
$\begin{eqnarray*} \leftrightarrow 2\cdot x_1 = 1 \mod 7 \end{eqnarray*}$ und nun habe ich durch einsetzen geschaut, mit welcher Zahl von $\begin{eqnarray*} 1\leq x \leq 6 \end{eqnarray*}$ ich auf den Rest 1 (an dieser Stelle sehe ich eigentlich erst, dass der Rest 1 ist) komme. Oder ist das falsch? verwirrt

Mein Problem ist dann, dass ich für z.B. m = 71 viel mehr Zahlen testen müsste, ist etwas aufwendig und zeitraubend, wenn es da einen "Trick" gibt, dann kenne ich ihn nicht.)

Edit:
folgendes habe ich gefunden für das Inverse, allerdings gilt dies, glaube ich, nur für 2:

$\begin{eqnarray*} 2(\frac{p+1}{2})\equiv 1 \mod p \end{eqnarray*}$ für p prim

somit
$\begin{eqnarray*} x_1= 2^(-1)=4 \end{eqnarray*}$ . Das Heißt, das Inverse zu 2 ist 4.
$\begin{eqnarray*} x_2= 3\cdot4 =12\equiv5 \mod 7 \end{eqnarray*}$ .

12.07.2013, 15:37

watcher

Auf diesen Beitrag antworten »

Den erweiterten euklidischen Algorithmus behandelt man heutzutage also nicht mehr in elementaren Zahlentheorie Vorlesungen?

12.07.2013, 16:43

Matheversteher

Auf diesen Beitrag antworten »

Zitat:

Zitat
Den erweiterten euklidischen Algorithmus behandelt man heutzutage also nicht mehr in elementaren Zahlentheorie Vorlesungen?

Ich musste jetzt erstmal kurz überlegen, wo ich den anwenden soll. Das war jetzt für mich (als unwissender, der diesen Schritt nicht kennt etwas) etwas schwer zu erkennen, an welcher Stelle ich ansetzen soll. Augenzwinkern

Ich sage es aber nochmal, ich bin froh, dass du mir hilfst!

Zurück zum Thema:
Mit Hilfe des erweiterten Euklidischen Algorithmus kann ich $\begin{eqnarray*} ggT(a,b)=a \cdot y+b \cdot x \end{eqnarray*}$ darstellen.

Was ich bisher nicht wusste ist:

Es gilt: $\begin{eqnarray*} ay=1 \mod b \end{eqnarray*}$ genau dann, wenn es eine ganze Zahl x mit $\begin{eqnarray*} ay+bx=1 \end{eqnarray*}$ gibt. Sind m und n teilerfremd zueinander, so lassen sich x,y mit Hilfe des erweiterten Euklidischen Algorithmus bestimmen.

So kann ich nun das Inverse zu 2 bestimmen:
$\begin{eqnarray*} 2x\equiv 1 \mod 7 \end{eqnarray*}$ $\begin{eqnarray*} \leftrightarrow 7y+2x=1 \end{eqnarray*}$

$\begin{eqnarray*} y=1 \end{eqnarray*}$ und $\begin{eqnarray*} x= -3 \end{eqnarray*}$ letzteres ist $\begin{eqnarray*} x= -3 \equiv 4 \mod 7 \end{eqnarray*}$ somit erhalte ich mein Inverses. Ist das nun korrekt? verwirrt

12.07.2013, 16:53

watcher

Auf diesen Beitrag antworten »

Zitat:

Ihr habt den Algorithmus ernsthaft nicht gemacht?
Seltsame elementare Zahlentheorie Vorlesung.

Zitat:

Es gilt: $\begin{eqnarray*} ay=1 \mod b \end{eqnarray*}$ genau dann, wenn es eine ganze Zahl x mit $\begin{eqnarray*} ay+bx=1 \end{eqnarray*}$ gibt.

Das ist schlicht die Def. des modulo d.h. des Restklassenrings.

Zitat:

So kann ich nun das Inverse zu 2 bestimmen: $\begin{eqnarray*} 2x\equiv 1 \mod 7 \end{eqnarray*}$ $\begin{eqnarray*} \leftrightarrow 7y+2x=1 \end{eqnarray*}$

Zum einen muss es heißen:

$\begin{eqnarray*} 2x\equiv 1 \mod 7 \end{eqnarray*}$ $\begin{eqnarray*} \Leftrightarrow \exists x,y \in \mathbb Z :7y+2x=1 \end{eqnarray*}$
zum anderen lässt sich mittels des erw. eukl. Alg. auch x, y explizit bestimmen.
(Was hier sehr einfach ist.)

12.07.2013, 17:08

Matheversteher

Auf diesen Beitrag antworten »

Ähm wir haben es bestimmt gemacht, ich muss allerdings sagen, dass unsere Vorlesung wirklich chaotisch und unstrukturiert gewesen ist. Das Skript ist mir deshalb leider keine Hilfe.

Zitat:

Zitat
$\begin{eqnarray*} \Leftrightarrow \exists x,y \in \mathbb Z :7y+2x=1 \end{eqnarray*}$

Danke für die Verbesserung.

Habe es gerade auch bei 2 anderen Aufgaben so gemacht smile

Zitat:

Zitat
zum anderen lässt sich mittels des erw. eukl. Alg. auch x, y explizit bestimmen.

Ich habe es mir gespart die 2 Zeilen hier zu tippen aber wenn du es haben möchtest:

$\begin{eqnarray*} 7= 3 \cdot 2 + 1 \end{eqnarray*}$
$\begin{eqnarray*} 2= 2 \cdot 1 + 0 \end{eqnarray*}$
Das heißt 1 ist mein $\begin{eqnarray*} ggT(7,2) \end{eqnarray*}$ , somit $\begin{eqnarray*} 1= y7+x2 \end{eqnarray*}$
Aus Zeile 1 folgt:
$\begin{eqnarray*} 1= 1\cdot 7 + (-3)\cdot 2 \end{eqnarray*}$
also: $\begin{eqnarray*} y=1 \end{eqnarray*}$ und $\begin{eqnarray*} x=-3 \end{eqnarray*}$

War es das was du sehen wolltest?!

12.07.2013, 17:15

watcher

Auf diesen Beitrag antworten »

Ich will hier überhaupt nichts.
Die Erfahrung lehrt mich nur, dass das oft ein Problem ist.
Insbesondere wenn man sich mit diesem wichtigen Algo. anfangs auseinandersetzt.

Aber alles richtig.

12.07.2013, 17:44

Matheversteher

Auf diesen Beitrag antworten »

Ok, super ich danke dir für deine Geduld smile

Neue Frage »

Antworten »

quadratische kongruenzen

Verwandte Themen