Jacobisymbol mod 2

20.12.2022, 16:59

Malcang

Jacobisymbol mod 2

Hallo zusammen,

ich beiße mir gerade die Zähne an der Berechnung des Jacobisymbols $\begin{eqnarray*} J(n, p) \end{eqnarray*}$ aus.
Sei $\begin{eqnarray*} n = p_1^{\alpha_1} \cdot \dots \cdot p_k^{\alpha_k} \end{eqnarray*}$ die Primfaktorzerlegung von $\begin{eqnarray*} n. \end{eqnarray*}$
Für eine ungerade Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ fällt das jacobisymbol mit dem Legendresymbol zusammen. Das kann ich dann mittels Eulerkriterium berechnen.
Falls $\begin{eqnarray*} p \end{eqnarray*}$ keine Primzahl ist, so berechne ich ja die einzelnen Legendresymbole $\begin{eqnarray*} \begin{pmatrix}\frac{n}{p_i}\end{pmatrix}^{\alpha_i} \end{eqnarray*}$ und multipliziere auf.
Aber was, wenn $\begin{eqnarray*} p_1 = 2 \end{eqnarray*}$ ist?

Mein erster Gedanke war, dass ja für mod 2 nur die Werte 0 und 1 in Frage kommen, was beides Quadrate sind. Also $\begin{eqnarray*} \begin{pmatrix}\frac{n}{2}\end{pmatrix}= 1 \end{eqnarray*}$ . Dies ist nach wolframalpha allerdings falsch.
Leider auch falsch ist allerdings $\begin{eqnarray*} \begin{pmatrix}\frac{n}{2}\end{pmatrix}= 1 \end{eqnarray*}$ wenn $\begin{eqnarray*} n \end{eqnarray*}$ ungerade ist und $\begin{eqnarray*} \begin{pmatrix}\frac{n}{2}\end{pmatrix}= 0 \end{eqnarray*}$ wenn $\begin{eqnarray*} n \end{eqnarray*}$ gerade und daher Vielfaches von 2 ist.

Ich konnte auch nichts weiter dazu finden. Otto Forster schreibt, er lässt den trivialen Fall p=2 einfach beiseite. So trivial finde ich das nicht.

Kann mir jemand auf die Sprünge helfen?

20.12.2022, 17:51

IfindU

Auf diesen Beitrag antworten »

Ich finde nirgendwo eine Definition für $\begin{eqnarray*} p =2 \end{eqnarray*}$ . Selbst Wolfram Alpha verlinkt auf Wolfram und dort steht es ist nicht definiert.

Ich tippe die rechnen "irgendwas", weil die den Fall nicht abfangen. Oder hast du eine Definition?

Edit: Wolfram definiert aber das Legendre Symbol für alle $\begin{eqnarray*} p \end{eqnarray*}$ . Wenn $\begin{eqnarray*} p | n \end{eqnarray*}$ wird der Wert 0 gesetzt. Das ist für $\begin{eqnarray*} p = 2 \end{eqnarray*}$ genau die Bedingung "n ist gerade". Falls $\begin{eqnarray*} n \end{eqnarray*}$ ungerade ist, so ist $\begin{eqnarray*} n \equiv 1 \mod 2 \end{eqnarray*}$ und $\begin{eqnarray*} 1 \end{eqnarray*}$ ist quadratischer Rest von $\begin{eqnarray*} 1^2 \end{eqnarray*}$ .

20.12.2022, 20:08

Malcang

Auf diesen Beitrag antworten »

Ich kenne auch nur die Definition von Wikipedia:
[attach]56554[/attach]

So finde ich sie auch in Forsters Buch "Algorithmische Zahlentheorie".

Wenn ich mir die Werte der Legendresymbole $\begin{eqnarray*} L(x,2) \end{eqnarray*}$ für $\begin{eqnarray*} 0<x<30 \end{eqnarray*}$ in wolfram ausgeben lasse, sind die geraden Zahlen auch bei 0. Die anderen springen allerdings zwischen -1 und 1.
Ich überlege gerade ob das zum 1. Ergänzungssatz des quadratischen Reziprozitätsgesetz passt. Müsste ich gleich mal in Ruhe rechnen. Allerdings ist mir der Fall mit der 2 trotzdem nicht unmittelbar klar. Denn sei $\begin{eqnarray*} n \end{eqnarray*}$ gerade, dann ist $\begin{eqnarray*} 0^2 \equiv n \pmod 2 \end{eqnarray*}$ . Und falls n ungerade ist, folgt $\begin{eqnarray*} 1^2 \equiv n \pmod 2 \end{eqnarray*}$ .

20.12.2022, 20:19

IfindU

Auf diesen Beitrag antworten »

RE: Jacobisymbol mod 2
In Wikipedia steht allerdings in der Einleitung

Zitat:

Dabei muss $\begin{eqnarray*} n \end{eqnarray*}$ im Gegensatz zum Legendre-Symbol keine Primzahl sein, allerdings muss es eine ungerade Zahl größer als 1 sein.

Bei Legendre steht es auch:

Zitat:

Das Legendre-Symbol gibt an, ob die Zahl $\begin{eqnarray*} a \end{eqnarray*}$ Quadratischer Rest oder quadratischer Nichtrest modulo $\begin{eqnarray*} p \end{eqnarray*}$ ist. Dabei ist $\begin{eqnarray*} a \end{eqnarray*}$ eine ganze Zahl und $\begin{eqnarray*} p \end{eqnarray*}$ eine ungerade Primzahl.

Wenn $\begin{eqnarray*} n \end{eqnarray*}$ gerade ist, landest du im dritten und letzten Ast der Fallunterscheidung. In der Definition vom "quadratischen Rest" ist schon festgelegt, dass $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ teilerfremd sein müssen. Daher ist es eindeutig im dritten Ast.

Ich würde mal drauf tippen, dass es ein Fehler bei Alpha ist, dass es hin und wieder auf $\begin{eqnarray*} -1 \end{eqnarray*}$ springt.

Edit: Hier gibt es eine historische Begründung für das Auslassen in der Definition: StackExchange

21.12.2022, 13:48

Malcang

Auf diesen Beitrag antworten »

Guten Tag,

danke, IfindU, für die Ausführungen. Dass es wirklich nur für ungerade p definiert ist, hatte ich wohl ausgeblendet. Damit hat sich meine Frage dann auch erledigt.

Vielen Dank und schonmal schöne Feiertage an Alle! Wink

Neue Frage »

Antworten »

Jacobisymbol mod 2

Verwandte Themen