Halbsystem

Ein Halbsystem modulo einer ungeraden natürlichen Zahl $n$ ungleich 1 ist eine Teilmenge von $X:=(\mathbb{Z}/n\mathbb{Z})\setminus \{\overline{0}\}$, der Menge der von $\overline{0}$ (dem einzigen selbstinversen Element der additiven Gruppe $(\mathbb{Z}/n\mathbb{Z},+)$ des Restklassenrings modulo $n$) verschiedenen Restklassen modulo $n$, in der zu jedem $x\in X$ genau entweder $x$ oder $-x$ liegt. Bei gegebenem Halbsystem $H$ bezeichnet man das komplementäre Halbsystem $X\setminus H$ als $H^{\prime }$.

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

Beispiel

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

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

$g$ bezeichnet hier eine erzeugendes Element dieser stets zyklischen multiplikativen Gruppe der Ordnung $p-1$. Beweis: $H$ enthält genau die Hälfte der Elemente von $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$, die selbst genau $p-1$ Elemente enthält. Wegen $\overline{-1}=g^{\frac{p-1}{2}}$ liegt für $g^k=:x\in H$ das dazu additiv inverse Element $-x=-g^k=g^{\frac{p-1}{2}}{g}^k=g^{\frac{p-1}{2}+k}$ nicht in $H$, weil der Exponent $\frac{p-1}{2}+k$ modulo $p-1$ zu keinem $j$ mit $1\le j\le \frac{p-1}{2}$ kongruent ist. Denn andernfalls wäre ja $\frac{p-1}{2}+(k-j)$ durch $p-1$ teilbar, was jedoch wegen $|k-j|<\frac{p-1}{2}\Rightarrow 0<\frac{p-1}{2}+(k-j)<p-1$ unmöglich ist.

Literatur

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