Für welche Primzahlen p ist das Gleichungssystem A * x = b über dem endlichen Körper Fp lösbar?

Question

Aufgabe:

$$A:= \begin{pmatrix} -1 & 2 & 2 \\ -2 & 1 & 0 \\ -3 & -3 & -1 \end{pmatrix} \in Z^{3x3} b:=\begin{pmatrix} 0\\-1\\-3 \end{pmatrix} \in Z^{3}$$

Für welche Primzahlen p ist das Gleichungssystem A * x = b über dem endlichen Körper Fp lösbar?

Frage:

Ich möchte wissen wie ich hier anfangen muss.

Heißt A*x das x die Primzahl ist?

Und wie verwende ich Körper über Fp bei solchen Aufgaben

Bitte um Starthilfe :)

mfg coffee.cup

Answer 1

Heißt A*x das x die Primzahl ist?

Nein. Du sollst entscheiden ob ein x (Vektor) existiert s.d. Ax = b mod (p)

Und wie verwende ich Körper über Fp bei solchen Aufgaben

Im Körper Fp wird jede ganze Zahl modulo p betrachtet. Z.B. in F3 gilt 5=2 mod (3), da 5 = 3*1 + 2. (Rest der Division durch p)

Ich möchte wissen wie ich hier anfangen muss.

Rechne mal die Determinante von A aus und bestimme ihre Primteiler.

Ist p eine Primzahl die nicht die Determinante teilt, so ist die Determinante von (A modulo p) ungleich 0, also existiert eine eindeutige Lösung.

Für die Primteiler p (endlich viele) rechnest du einfach explizit nach.

Comments

Danke für die Antwort :)

Als Determinante hab ich 15 rausbekommen und die Primteiler von 15 sind {3,5}

Für A mod p ist

15 mod {2,7,11,13,15...} ungleich 0

15 mod {3,5} sind gleich null

Wie wende ich das jetzt auf deine Angabe Ax = b mod (p) an?

---

Richtig, für p ≠ 3, 5 hast du also eine eindeutige Lösung.

Für p = 3 ist die erweiterte Koeffizientenmatrix:

$$\left(\begin{matrix}2&2&2\\1&1&0\\0&0&2\end{matrix}\middle|\begin{matrix}0\\2\\0\end{matrix} \right)$$

Für p = 5:

$$\left(\begin{matrix}4&2&2\\3&1&0\\2&2&4\end{matrix}\middle|\begin{matrix}0\\4\\2\end{matrix} \right)$$ 

Einfach alles modulo p rechnen, jetzt das LGS lösen (dabei halt auch modulo p rechnen, statt zu dividieren eben mit dem multiplikativ Inversen multiplizieren. Bsp p=5, nicht durch 4 teilen sondern mit 4 multiplizieren, da 4*4=16=1 mod 5)

---

Das mit dem Matrix modulo p rechnen hab ich soweit verstanden.

Zeilen voneinander abziehen wie beim Gauß-Algorithmus ist möglich oder?

Kannst du ein paar Schritte des LGS lösen vormachen, und zeigen wie du multipliziert

und dividiert hast?

(dann kann ich mir besser das mit dem inversen und so vorstellen)

---

P=3

$$\left(\begin{matrix}2&2&2\\1&1&0\\0&0&2\end{matrix}\middle|\begin{matrix}0\\2\\0\end{matrix} \right) \sim \left(\begin{matrix}1&1&0\\2&2&2\\0&0&2\end{matrix}\middle|\begin{matrix}2\\0\\0\end{matrix} \right) \sim \left(\begin{matrix}1&1&0\\0&0&2\\0&0&2\end{matrix}\middle|\begin{matrix}2\\2\\0\end{matrix} \right)$$
Zeilen tauschen, anschließend auf zweite die erste addieren  (3=0 mod 3)

Also Rang(A)=2 ≠ 3 = Rang(A|b) => keine Lösung.

P = 5:

$$\left(\begin{matrix}4&2&2\\3&1&0\\2&2&4\end{matrix}\middle|\begin{matrix}0\\4\\2\end{matrix} \right) \sim \left(\begin{matrix}1&3&3\\3&1&0\\2&2&4\end{matrix}\middle|\begin{matrix}0\\4\\2\end{matrix} \right)\sim \left(\begin{matrix}1&3&3\\0&2&1\\0&1&3\end{matrix}\middle|\begin{matrix}0\\4\\2\end{matrix} \right)$$ 

Erste Zeile mit dem Inversen von 4 (=4) multiplizieren. Anschließend von den anderen abziehen. Jetzt 3. Zeile von den anderen beiden abziehen

$$\left(\begin{matrix}1&3&3\\0&2&1\\0&1&3\end{matrix}\middle|\begin{matrix}0\\4\\2\end{matrix} \right) \sim \left(\begin{matrix}1&0&4\\0&0&0\\0&1&3\end{matrix}\middle|\begin{matrix}4\\0\\2\end{matrix} \right)$$

Jetzt haben wir eine strenge Zeilenstufenform, den Lösungraum solltest du daran ablesen können

---

Danke für die Hilfe :) jetzt hab ich es verstanden wie es funktioniert

.