Halbsystem

Ein Halbsystem modulo einer ungeraden natürlichen Zahl $n$ ungleich 1 ist eine Teilmenge von $X:=(\mathbb {Z} /n\mathbb {Z} )\setminus \{{\bar {0}}\}$, der Menge der von ${\bar {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'$.

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 \{{\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 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 ${\tfrac {p-1}{2}}+k$ modulo $p-1$ zu keinem $j$ mit $1\leq j\leq {\tfrac {p-1}{2}}$ kongruent ist. Denn andernfalls wäre ja ${\tfrac {p-1}{2}}+(k-j)$ durch $p-1$ teilbar, was jedoch wegen $|k-j|<{\tfrac {p-1}{2}}\Rightarrow 0<{\tfrac {p-1}{2}}+(k-j)<p-1$ unmöglich ist.

Literatur

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