# Restklassenring/Z/Quadratischer Rest/Jacobi-Symbol/Einführung/Textabschnitt

Zur Berechnung des Legendre-Symbols muss man die Primfaktorzerlegung der beteiligten Zahlen kennen, was für große Zahlen ein erheblicher Rechenaufwand darstellen kann. Die Einführung des Jacobi-Symbols erlaubt es, zu entscheiden, ob eine Zahl quadratischer Rest ist oder nicht, ohne Primfaktorzerlegungen zu kennen.

## Definition

Für eine ungerade Zahl $n$ und eine ganze Zahl $k$ definiert man das Jacobi-Symbol, geschrieben $\left({\frac {k}{n}}\right)$ ($k$ nach $n$), wie folgt. Es sei $n=p_{1}\cdots p_{r}$ die Primfaktorzerlegung von $n$. Dann setzt man
    $\left({\frac {k}{n}}\right):=\left({\frac {k}{p_{1}}}\right)\cdots \left({\frac {k}{p_{r}}}\right)\,.$
Im Fall $n=p$ eine ungerade Primzahl ist das Jacobi-Symbol nichts anderes als das Legendre-Symbol. Das Jacobi-Symbol ist also eine Verallgemeinerung des Legendre-Symbols. Es ist aber zu beachten, dass die inhaltliche Definition des Legendre-Symbols sich im allgemeinen nicht auf das Jacobi-Symbol überträgt. Das Jacobi-Symbol ist nicht genau dann $1$, wenn $k$ ein Quadrat modulo $n$ ist. Die Definition des Jacobi-Symbols nimmt Bezug auf die Primfaktorzerlegung von $n$, was wir eigentlich vermeiden wollten. Der Punkt ist aber, dass man das Jacobi-Symbol berechnen kann, auch wenn man die Primfaktorzerlegung gar nicht kennt.

## Lemma

Es seien $k,k_{1},k_{2}$ ganze Zahlen und seien $n,n_{1},n_{2}$ ungerade positive Zahlen. Dann gelten folgende Aussagen.
* Das Jacobi-Symbol $\left({\frac {k}{n}}\right)$ hängt nur vom Rest $k\mod n$ ab.
* Es ist $\left({\frac {k_{1}k_{2}}{n}}\right)=\left({\frac {k_{1}}{n}}\right)\left({\frac {k_{2}}{n}}\right)$.
* Es ist
    $\left({\frac {k}{n_{1}n_{2}}}\right)=\left({\frac {k}{n_{1}}}\right)\left({\frac {k}{n_{2}}}\right)\,.$

### Beweis

Diese Aussagen folgen sofort aus der Definition des Jacobi-Symbols bzw. aus der Multiplikativität des Legendre-Symbols im Zähler.
$\Box$
Für das Jacobi-Symbol gilt das quadratische Reziprozitäts mitsamt den Ergänzungssätzen.

## Satz

Es seien $n$ und $m$ positive ungerade Zahlen. Dann gelten folgende Aussagen.

### Beweis

Diese Aussagen werden in den Aufgaben bewiesen.
$\Box$

## Bemerkung

Es seien $n$ und $m$ ungerade verschiedene Zahlen, und man möchte das Jacobi-Symbol $\left({\frac {n}{m}}\right)$ berechnen (man berechnet im Allgemeinen nicht, ob $n$ ein quadratischer Rest modulo $m$ ist, dies ist nur dann der Fall, wenn $m$ eine Primzahl ist). Durch die Restberechnung $n\mod m$ können wir sofort annehmen, dass $n<m$ ist. Wir schreiben
    $n=2^{\alpha }k\,,$
wobei $k$ ungerade sei. Dann gilt nach Fakt
    $\left({\frac {n}{m}}\right)=\left({\frac {2^{\alpha }}{m}}\right)\cdot \left({\frac {k}{m}}\right)=\left({\frac {2}{m}}\right)^{\alpha }\cdot \left({\frac {k}{m}}\right)\,.$
Hier kann, nach dem quadratischen Reziprozitätsgesetz für das Jacobi-Symbol (und der Ergänzungssätze), $\left({\frac {2}{m}}\right)$ berechnet werden und $\left({\frac {k}{m}}\right)$ kann auf $\left({\frac {m}{k}}\right)$ zurückgeführt werden. Bei diesem Verfahren werden natürlich die Nenner (und damit auch die Zähler) in den Jacobi-Symbolen kleiner, sodass man schließlich das Resultat erhält.
Wenn $p$ eine Primzahl ist, so kann man mit diesem Algorithmus, also unter Verwendung des Jacobi-Symbols, entscheiden, ob $k$ ein Quadratrest modulo $p$ ist. In den Zwischenschritten braucht man nicht die Primfaktorzerlegungen auszurechnen.