Halbsystem

Ein Halbsystem modulo n ist eine Teilmenge von $X := (\Z/n\Z)\setminus\{\bar{0}\}$, der Menge der von $\bar0$ verschiedenen Restklassen modulo n, in der zu jedem $x \in X$ genau entweder x oder − x liegen. Bei gegebenem Halbsystem H bezeichnet man das komplementäre Halbsystem $X \setminus H$ als H'.

Anwendung finden Halbsysteme bei Leopold Kroneckers Zugang zum Jacobi-Symbol.

Beispiel

In der zyklischen Restklassengruppe modulo einer ungeraden Primzahl p, $(\Z/p\Z)^\times = (\Z/p\Z) \setminus \{\bar{0}\}$, ist zum Beispiel die folgende Menge ein Halbsystem:

$H := \left\{g^k \mid 1 \leq k \leq \frac{p-1}2 \right\}$

g bezeichnet hier eine Primitivwurzel der zyklischen Gruppe. Beweis: H enthält gerade die Hälfte der Elemente von $(\Z/p\Z)^\times$, die selbst p − 1 Elemente enthält. Da $\overline{-1} = g^{\frac{p-1}2}$ ist, ist für $g^k = x \in H$ das Negative $-x = -g^k = g^{\frac{p-1}2}g^k = g^{\frac{p-1}2 + k} \notin H$.

Literatur

• Armin Leutbecher, Zahlentheorie. Springer-Verlag, 1996. ISBN 3-540-58791-8.