Einfache Lösung mit Jacobi-Symbol

08.02.2017, 13:44

Selina19931

Einfache Lösung mit Jacobi-Symbol

Meine Frage:
Hallo, kann mir jemand bitte bei der Aufgabe helfen:

Finde eine möglichst einfache Beschreibung der Menge der Primzahlen p>7 für die

x2 kongruent -35 mod p

eine Lösung hat.

Meine Ideen:
Ich weiß, dass es über das Jacobi-Symbol laufen muss. Aber ich kann mir keine Darstellung dazu ableiten, weil wir vorher immer nur mit Primzahlen als QR gerechnet hatten.

08.02.2017, 14:07

HAL 9000

Auf diesen Beitrag antworten »

Naja, es gibt ja Rechenregeln für diese Jacobi- bzw. eigentlich ja nur Legendre-Symbole, z.B. eben das hier nützliche $\begin{align*} \left( \frac{a\cdot b}{p} \right) = \left( \frac{a}{p} \right) \cdot \left( \frac{b}{p} \right) \end{align*}$ . Augenzwinkern

08.02.2017, 14:32

Selina19931

Auf diesen Beitrag antworten »

Also ich glaube ich habe absoluten Mist raus, aber ich habe raus, dass
p kongruent 4 mod 4 &
p kongruent +- 1 mod 15
gilt

08.02.2017, 14:53

HAL 9000

Auf diesen Beitrag antworten »

Klingt wirklich nicht gut, denn nenne mir mal eine, nur eine Primzahl $\begin{align*} p \end{align*}$ , die das hier

Zitat:

Original von Selina19931
p kongruent 4 mod 4

erfüllt...

Wie bist du denn vorgegangen? Der übliche Weg führt doch über die oben genannte Multiplikationsregel

$\begin{align*} \left( \frac{-35}{p} \right) = \left( \frac{-1}{p} \right)\cdot \left( \frac{5}{p} \right)\cdot \left( \frac{7}{p} \right) \end{align*}$ ,

und dann auf den ersten Faktor den ersten Ergänzungssatz, und auf den zweiten und dritten Faktor das eigentliche Quadratische Reziprozitätsgesetz angewandt. Oder hast du einen anderen Plan? verwirrt

08.02.2017, 15:11

Selina19931

Auf diesen Beitrag antworten »

Mit der 4 habe ich mich vertippt , aber das andere war mein Fehler.
Ich hab mich weiter dran probiert und habe jetzt raus, dass
p kongruent +1 mod 4 &
p kongruent +- 1 mod 5 &
p kongruent +-1 mod 7

Aber das kann so ja eigentlich auch nicht stimmen..

08.02.2017, 15:59

HAL 9000

Auf diesen Beitrag antworten »

Vielleicht beenden wir mal diese Trial-and-Error-Dauerschleife, und du legst mal mit Zwischenschritten dar, wie du vorgegangen bist - ich hab schließlich auch oben klar den Plan dargelegt, wie ich diese Aufgabe löse.

08.02.2017, 16:34

Selina19931

Auf diesen Beitrag antworten »

Ich habe mir überlegt, dass $\begin{eqnarray*} \frac{-1}{p} \end{eqnarray*}$ entweder -1 wenn p $\begin{eqnarray*} \equiv \end{eqnarray*}$ - 1 mod 4 oder 1 wenn p $\begin{eqnarray*} \equiv \end{eqnarray*}$ - 1 mod 4.
Weiter ist $\begin{eqnarray*} \frac{5}{p} \end{eqnarray*}$ = $\begin{eqnarray*} \frac{p}{5} \end{eqnarray*}$ und das muss gleich 1 also : p $\begin{eqnarray*} \equiv \end{eqnarray*}$ +-1 mod 5.
Und schlussendlich ist $\begin{eqnarray*} \frac{7}{p} \end{eqnarray*}$ entweder - $\begin{eqnarray*} \frac{p}{7} \end{eqnarray*}$ , wenn p $\begin{eqnarray*} \equiv \end{eqnarray*}$ - 1 mod 4 oder eben $\begin{eqnarray*} \frac{p}{7} \end{eqnarray*}$ . Und damit p $\begin{eqnarray*} \equiv \end{eqnarray*}$ +- 1 mod 7
Und das habe ich versucht miteinander zu kombinieren.

08.02.2017, 16:53

HAL 9000

Auf diesen Beitrag antworten »

Bleib doch erstmal bei dem QRG auf Formelebene - es lohnt sich, wie du gleich sehen wirst:

$\begin{align*} \left( \frac{-35}{p} \right) = \left( \frac{-1}{p} \right)\cdot \left( \frac{5}{p} \right)\cdot \left( \frac{7}{p} \right) = (-1)^{\frac{p-1}{2}}\cdot (-1)^{\frac{5-1}{2}\cdot \frac{p-1}{2}}\cdot \left( \frac{p}{5} \right)\cdot (-1)^{\frac{7-1}{2}\cdot\frac{p-1}{2}} \cdot \left( \frac{p}{7} \right) \end{align*}$ .

Und wenn du jetzt mal die ganzen (-1)-Potenzen zusammenfasst, wirst du sehen, dass sich die alle in Rauch auflösen, d.h., Wert 1. Es steht also am Ende da

$\begin{align*} \left( \frac{-35}{p} \right) = \left( \frac{p}{5} \right)\cdot \left( \frac{p}{7} \right)\qquad (*) \end{align*}$ ,

es bestehen daher modulo 4 gar keine Forderungen. Und (*) muss man nun aber auch richtig interpretieren:

-35 ist quadratischer Rest modulo $\begin{align*} p \end{align*}$ , wenn $\begin{align*} \left( \frac{-35}{p} \right) = 1 \end{align*}$ ist. Und das geschieht laut (*) genau dann, wenn

a) $\begin{align*} \left( \frac{p}{5} \right) = \left( \frac{p}{7} \right) = 1 \end{align*}$ ist, oder (!)

b) $\begin{align*} \left( \frac{p}{5} \right) = \left( \frac{p}{7} \right) = -1 \end{align*}$ ist.

D.h., wir suchen alle Primzahlen $\begin{align*} p>7 \end{align*}$ , die entweder modulo 5 und modulo 7 zugleich quadratischen Reste sind, oder aber zugleich quadratische Nichtreste!!! Im Endeffekt muss man von den $\begin{align*} \varphi(35)=24 \end{align*}$ zu 35 teilerfremden Resten modulo 35 diejenige Hälfte (also 12 Stück) aufsammeln, die entweder zu a) (6 Stück) oder zu b) (ebenfalls 6 Stück) gehören.

08.02.2017, 16:56

Selina19931

Auf diesen Beitrag antworten »

Vielen , lieben Dank!!

Neue Frage »

Antworten »

Einfache Lösung mit Jacobi-Symbol

Verwandte Themen