Halbsystem

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

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

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

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

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

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