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[Bearbeiten | Quelltext bearbeiten]

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.