GF(3) aus Axiomen erzeugen

03.08.2022, 14:31

Stud030822

GF(3) aus Axiomen erzeugen

Hallo,

ich möchte für GF(3) einmal die Additionstabelle und die Multiplikationstabelle erzeugen. Für meine Frage beschränke ich mich hier nur auf die Addition. GF(3) besteht aus den Elementen {0,1,a}

Aus den Axiomen der Körpertheorie ist mir bekannt, dass 0 + x = x ist. Das würde für den Körper schon mal folgendes bedeuten:
0 + 0 = 0, 0 + 1 = 1, 0 + a = a

Jetzt gilt es herauszufinden, was nun 1 + 1 = ?, a + 1 = ?, 1 + a = ? und a + a = ? ist.

Für 1 + 1 könnte man als Ergebnis 0, 1 oder a erhalten. Via Widerspruch und Fallunterscheidung würde ich das so angehen:
1+1= 0 --> 1 = -1 (Sieht für mich falsch aus)
1+1= 1 --> 1 = 0 (Widerspruch)
1+1= a --> 1 = a (wäre hier der einzige nicht Widerspruch)

Für a + a könnte man als Ergebnis 0, 1 oder a erhalten. Via Widerspruch würde ich das so angehen:
a+a= 0 --> a = -a (Sieht für mich falsch aus)
a+a= 1 --> 1 = a (wäre hier der einzige nicht Widerspruch und passt zu dem Oberen)
a+a= a --> a = 0 (Widerspruch)

Wie finde ich jetzt aber heraus, was "a + 1 = ?" ist? Achso sind die Vorüberlegungen soweit ok?

03.08.2022, 14:44

HAL 9000

Auf diesen Beitrag antworten »

Schauen wir uns mal die gesamte Tabelle an:

code:
1: 2: 3: 4:	+ 0 1 a 0 0 1 a 1 1 ? ? a a ? ?

In jeder Zeile und jeder Spalte müssen die drei Werte 0,1,a jeweils genau einmal vorkommen. (*)

1+1=1 ist nicht möglich, weil schon 0+1=1 ist.
1+1=0 würde 1+a=a zur Folge haben, Widerspruch zu 0+a=a.

Es bleibt nur 1+1=a übrig - die restlichen drei ? folgen blitzschnell durch Forderung (*).

03.08.2022, 14:58

Stud030822

Auf diesen Beitrag antworten »

Zitat:

In jeder Zeile und jeder Spalte müssen die drei Werte 0,1,a jeweils genau einmal vorkommen. (*)

Ach ja richtig! Das hatte ich kurzzeitig vergessen...

Vielen Dank HAL! Freude

03.08.2022, 21:09

Stud030822

Auf diesen Beitrag antworten »

Mich würde noch die Konstruktion von GF(4) interessieren, die Elemente von GF(4) sind ja {0,1,a,b}.

Warum ist in GF(4) 1+1=0? Ich versuche das wieder anhand der Axiome zu machen, komme aber hier nicht wirklich weiter. Die Möglichkeiten für 1+1 = ... in GF(4) sind ja beschränkt auf {0,a,b}, da 1 ja schon in der Zeile/Spalte vorher verwendet wird...

03.08.2022, 21:52

Elvis

Auf diesen Beitrag antworten »

GF(4) ist eine quadratische Erweiterung von GF(2), enthält diesen als Teilmenge, und in GF(2) ist 1+1=0. Daraus folgt sofort a+a=b+b=0 nach dem Distributivgesetz. Um einen endlichen Körper zu verstehen, kann man ihn konkret als Faktorring konstruieren und mit einem primitiven Element und seinen Potenzen eine Vektorraumbasis des endlichen Körpers über seinem Primkoerper herstellen. Hier ist z. B. $\begin{eqnarray*} \{1, a \} \end{eqnarray*}$ mit $\begin{eqnarray*} a^2 =a+1 \end{eqnarray*}$ eine Basis, wenn man $\begin{eqnarray*} x^2 +x+1 \end{eqnarray*}$ als irreduzibles Polynom benutzt.

03.08.2022, 22:43

Stud030822

Auf diesen Beitrag antworten »

Hey Elvis,

danke für die Antwort. Ich habe mir fast gedacht, dass es auf die Teilmenge hinausläuft. Nur das habe ich auch als Erklärung für 1+1=0 finden können.

Nebenbei, ich versuche das zu konstruieren ohne Wissen zu den Vektorräumen (die kommen später) anzuwenden...

Wenn ich jetzt ein größeres GF hätte, dann wären das doch einige Fälle, die man betrachten müsste, alleine schon für GF(5), wird das doch sehr aufwändig (viele Lücken in der Tabelle und man kann nichts als Teilmenge verwenden)?!

code:
1: 2: 3: 4: 5: 6: 7: 8:	+ 0 1 a b c 0 0 1 a b c 1 1 a a b b c c

Jetzt auch hier wieder 1+1=? Möglichkeiten wären {0,a,b,c}... Ich würde hier z.B. 1+1= 0 versuchen und irgendwie einen Widerspruch zu erzeugen, auch wenn ich das noch nicht sehe, wenn ich einen Widerspruch gefunden habe würde ich 1+1=a versuchen etc.

03.08.2022, 23:04

zweiundvierzig

Auf diesen Beitrag antworten »

Für eine Primzahl p bekommt man GF(p) als den Restklassenring Z/pZ. Für GF(q) mit q=p^n braucht man Quotienten von (Z/pZ)[X], wie von Elvis angedeutet. Der allgemeine Fall ist hier beschrieben.

04.08.2022, 08:24

Elvis

Auf diesen Beitrag antworten »

In GF(5) ist wieder alles ganz einfach. 1+1=2,2+1=3,3+1=4,4+1=0. Die Elemente sind 0,1,2,3,4 und man rechnet bei Addition und Multiplikation modulo 5. Genau so einfach ist das für GF(p) für jede Primzahl p.
Erst für GF(p^n) muss man etwas mehr Aufwand treiben. Der kleinste Teilkoerper von GF(p^n) ist GF(p), und für jeden Teiler m von n enthält GF(p^n) genau einen Teilkoerper GF(p^m).

04.08.2022, 10:22

Stud030822

Auf diesen Beitrag antworten »

Hallo Elvis,

ja stimmt für GF(5) ist der Körper über modulo 5 zu bestimmen, das geht wirklich einfach, wie für alle Primzahlkörper.

Dann wäre ja mal interessant, wie man GF(6) und GF(9) bestimmt, ersteren halte ich für sehr kompliziert, bei letzterem könnte man verwenden, dass 9 = 3^2 ist, also der Teilkörper GF(3) enthalten ist?

04.08.2022, 10:32

Stud030822

Auf diesen Beitrag antworten »

Halt, GF(6) wäre kein Körper...

04.08.2022, 12:00

Leopold

Auf diesen Beitrag antworten »

Zur Konstruktion eines Körpers $\begin{align*} L = \operatorname{GF}(9) \end{align*}$ nimmst du ein über $\begin{align*} K = \operatorname{GF}(3) = \{0,1,-1\} \end{align*}$ irreduzibles quadratisches Polynom. Das einfachste Polynom dieser Art wäre $\begin{align*} x^2 + 1 \end{align*}$ . Jetzt gehst du analog vor wie bei der Konstruktion von $\begin{align*} \mathbb{C} \end{align*}$ als Erweiterung von $\begin{align*} \mathbb{R} \end{align*}$ . Du nimmst eine formale Nullstelle dieses Polynoms. Niemand hindert dich daran, diese auch als $\begin{align*} \operatorname{i} \end{align*}$ zu bezeichnen. Es gilt somit $\begin{align*} \operatorname{i}^2 + 1 = 0 \end{align*}$ , also $\begin{align*} \operatorname{i}^2 = -1 \end{align*}$ . Die Elemente von $\begin{align*} L \end{align*}$ sind nun formale Summen $\begin{align*} a + \operatorname{i}b \end{align*}$ mit $\begin{align*} a,b \in K \end{align*}$ . Elementare Kombinatorik zeigt, daß es 9 derartige Summen gibt. Mit diesen Summen rechnest du distributiv unter Beachtung der Regeln von $\begin{align*} K \end{align*}$ und von $\begin{align*} \operatorname{i}^2 = -1 \end{align*}$ . Und wie üblich schreibt man für $\begin{align*} 0 + \operatorname{i}b \end{align*}$ einfach $\begin{align*} \operatorname{i}b \end{align*}$ und für $\begin{align*} a + \operatorname{i} \cdot 0 \end{align*}$ schlicht $\begin{align*} a \end{align*}$ . Und $\begin{align*} \operatorname{i} \cdot 1 \end{align*}$ wird kurz als $\begin{align*} \operatorname{i} \end{align*}$ geschrieben. Auf diese Weise wird $\begin{align*} L \end{align*}$ ein Oberkörper von $\begin{align*} K \end{align*}$ mit genau 9 Elementen.

Beispiel:

$\begin{align*} \alpha = -1 + \operatorname{i} \, , \ \ \beta = \operatorname{i} \end{align*}$

Hierfür gilt:

$\begin{align*} \alpha \cdot \beta = \left( -1 + \operatorname{i} \right) \cdot \operatorname{i} = - \operatorname{i} + \operatorname{i}^2 = -1 - \operatorname{i} \end{align*}$

$\begin{align*} \alpha + \beta = -1 + \operatorname{i} + \operatorname{i} = -1 + (1+1) \operatorname{i} = - 1 - \operatorname{i} \end{align*}$

Und, der Zufall will es, bei diesem Beispiel ist $\begin{align*} \alpha \cdot \beta = \alpha + \beta \end{align*}$ . Diese Gleichung nach $\begin{align*} \beta \end{align*}$ aufgelöst ergibt

$\begin{align*} \beta = \frac{\alpha}{\alpha-1} \end{align*}$

Spaßeshalber rechnen wir den Term rechts einmal aus. Zunächst ist $\begin{align*} \alpha - 1 = -1 + \operatorname{i} - 1 = 1 + \operatorname{i} \end{align*}$ . Daraus folgt:

$\begin{align*} \frac{\alpha}{\alpha - 1} = \frac{-1 + \operatorname{i}}{1 + \operatorname{i}} = \frac{\left( -1 + \operatorname{i} \right) \left( 1 - \operatorname{i} \right)}{\left( 1 + \operatorname{i} \right) \left( 1 - \operatorname{i} \right)} = \frac{-1 + \operatorname{i} + \operatorname{i} - \operatorname{i}^2}{1 - \operatorname{i}^2} = \frac{-1 + \operatorname{i} + \operatorname{i} + 1}{1+1} = \frac{- \operatorname{i}}{-1} = \operatorname{i} \end{align*}$

Wer hätt's gedacht...

04.08.2022, 14:14

Elvis

Auf diesen Beitrag antworten »

Ein schönes Beispiel, und es zeigt ein wahres Wunder: in jedem Körper kann man rechnen wie in einem Körper. (Reines Lob, keine Ironie.)

Neue Frage »

Antworten »

GF(3) aus Axiomen erzeugen

Verwandte Themen