Halbsystem

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

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

Beispiel

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

<math>H := \left\{g^k \mid 1 \leq k \leq \frac{p-1}2 \right\}</math>

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

Literatur

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