Jacobisymbol, notwendige Bedingung für quadratischen Rest

30.01.2023, 16:46

Malcang

Jacobisymbol, notwendige Bedingung für quadratischen Rest

Hallo und schönen Wochenstart smile

ich bin es nochmal mit meinem bekannten Thema, dem Jacobi-Symbol.
Ich hoffe erstmal dass es ok ist, soviele einzelne Threads zu machen. Ich denke schon, da ja Leser davon profitieren. Falls es aber in einen Sammelthread sollte, möchte ich einen Mod darum bitten.

Das Jacobi-Symbol gibt mir ja nur eine notwendige Bedingung dafür, dass eine Zahl aquadratischer Rest ist modulo p.
Meine Behauptung ist also

Zitat:

Sei $\begin{eqnarray*} a \end{eqnarray*}$ eine ganze Zahl und sei $\begin{eqnarray*} m \end{eqnarray*}$ eine ungerade ganze Zahl. Falls $\begin{eqnarray*} a \end{eqnarray*}$ quadratischer Rest modulo $\begin{eqnarray*} m \end{eqnarray*}$ ist, so folgt $\begin{eqnarray*} \big(\frac{a}{m}\big) = 1 \end{eqnarray*}$ .

Ich hänge am Beweis.

Sei $\begin{eqnarray*} m = p_1\cdot p_2\dots p_n \end{eqnarray*}$ . Dann ist
$\begin{eqnarray*} \big(\frac{a}{m}\big) = \big(\frac{a}{p_1}\big)\cdot \big(\frac{a}{p_2}\big)\dots \big(\frac{a}{p_n}\big) \end{eqnarray*}$ .

Ich bin mir ziemlich sicher, dass die Legendre-Symbole alle $\begin{eqnarray*} 1 \end{eqnarray*}$ ergeben, aber mir fehlt da gerade ein knackiges Argument für verwirrt

Kann mir jemand auf die Sprünge helfen?

Edit: Ich weiß natürich, dass $\begin{eqnarray*} ggT(a, m)=1 \end{eqnarray*}$ ist und damit auch $\begin{eqnarray*} ggT(a, p_i) = 1 \forall i \end{eqnarray*}$ . Aber wie bekomme ich den Rest argumentiert?

30.01.2023, 17:57

IfindU

Auf diesen Beitrag antworten »

Da $\begin{eqnarray*} a \end{eqnarray*}$ quadratischer Rest modulo $\begin{eqnarray*} m \end{eqnarray*}$ ist, existiert also eine Zahl $\begin{eqnarray*} x \end{eqnarray*}$ mit $\begin{eqnarray*} m | (a - x^2) \end{eqnarray*}$ .

Hilft das schon?

30.01.2023, 18:26

Malcang

Auf diesen Beitrag antworten »

Hallo IfindU! Wink

Zitat:

Original von IfindU
Da $\begin{eqnarray*} a \end{eqnarray*}$ quadratischer Rest modulo $\begin{eqnarray*} m \end{eqnarray*}$ ist, existiert also eine Zahl $\begin{eqnarray*} x \end{eqnarray*}$ mit $\begin{eqnarray*} m | (a - x^2) \end{eqnarray*}$ .

Ich glaube ja. Das gilt ja dann auch für jeden Teiler $\begin{eqnarray*} p_i \end{eqnarray*}$ von $\begin{eqnarray*} m. \end{eqnarray*}$ Also:
$\begin{eqnarray*} a \end{eqnarray*}$ ist quadratischer Rest mod $\begin{eqnarray*} m \Leftrightarrow \exists x: m|(a-x^2) \Rightarrow p_i|(a-x^2) \Leftrightarrow a\equiv x^2 \pmod {p_i} \forall p_i|m \end{eqnarray*}$ .

Korrekt?
Das habe ich auch verstanden. Oftmals tue ich mir so schwer damit das in meinen Kopf zu lassen. Ich habe zwar Beweise dafür gefunden, aber die argumentieren dann mit Halbsystemen, Potenzresten o.Ä.

Ist das aber soweit ok wie ich es nun habe?

30.01.2023, 18:50

IfindU

Auf diesen Beitrag antworten »

So war mein Gedanke. Freude

Jetzt wo du es sagst, gibt es aber noch einen Fall: Was ist wenn $\begin{eqnarray*} x^2 \equiv 0 \mod p_i \end{eqnarray*}$ ist. Dann haben wir ein Problem. In Wiki fordern sie zusätzlich $\begin{eqnarray*} ggT(a, m) = 1 \end{eqnarray*}$ . Das wird den Fall ausschließen.

30.01.2023, 19:23

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
So war mein Gedanke. Freude

Ich danke dir vielmals!

Zitat:

Original von IfindU
Jetzt wo du es sagst, gibt es aber noch einen Fall: Was ist wenn $\begin{eqnarray*} x^2 \equiv 0 \mod p_i \end{eqnarray*}$ ist. Dann haben wir ein Problem. In Wiki fordern sie zusätzlich $\begin{eqnarray*} ggT(a, m) = 1 \end{eqnarray*}$ . Das wird den Fall ausschließen.

Oh, auch hierfür danke. Ja, das werde ich so auch bei mir übernehmen.

Neue Frage »

Antworten »

Jacobisymbol, notwendige Bedingung für quadratischen Rest

Verwandte Themen