Halbsystem

Ein Halbsystem modulo einer ungeraden natürlichen Zahl $n$ ungleich 1 ist eine Teilmenge von $X := (ℤ / n ℤ) ∖ {\bar{0}}$ , der Menge der von $\bar{0}$ (dem einzigen selbstinversen Element der additiven Gruppe $(ℤ / n ℤ, +)$ 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 ∖ H$ als $H^{'}$ .

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

Beispiel

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

H := {g^{k} ∣ 1 \leq k \leq \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 $(ℤ / p ℤ)^{\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 \leq j \leq \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.