Quadratische Reste von Primzahlen, Gleichungssystem

14.05.2018, 10:26

SoulOfMidgard

Quadratische Reste von Primzahlen, Gleichungssystem

Meine Aufgabe ist es die kleinste Primzahl q zu finden, sodass 2,3, 5 quadratische Reste Modulo q sind und 7 quadratischer Nichtrest. Dies gibt mir ein Gleichungssystem:

$\begin{eqnarray*} 2^{\frac{p-1}{2}}=1 \end{eqnarray*}$
$\begin{eqnarray*} 3^{\frac{p-1}{2}}=1 \end{eqnarray*}$
$\begin{eqnarray*} 5^{\frac{p-1}{2}}=1 \end{eqnarray*}$
$\begin{eqnarray*} 7^{\frac{p-1}{2}}\neq1 \end{eqnarray*}$

Mithilfe der Tatsache dass ich (p-1)/2 quadratische Reste hatte wollte ich darauf schliessen, dass meine Zahl mindestens 7 oder größer sein muss. Aber brute force brachte mich hier nicht weiter.

Meine nächste Idee war die Eulersche phi-Funktion zu nutzen, da diese mir zumindest

$\begin{eqnarray*} 2^{p-1}=1 \end{eqnarray*}$
...

ausgibt. Aber auch dies trug bis jetzt keine Früchte. Hat jemand anderweitig eine Idee?

14.05.2018, 14:01

Huggy

Auf diesen Beitrag antworten »

RE: Quadratische Reste von Primzahlen, Gleichungssystem

Zitat:

Original von SoulOfMidgard
Aber brute force brachte mich hier nicht weiter.

Mein Rechner kommt auf $\begin{eqnarray*} q=71 \end{eqnarray*}$ .

14.05.2018, 17:44

HAL 9000

Auf diesen Beitrag antworten »

Man kann sich der Sache natürlich auch mit dem Quadratischen Reziprozitätsgesetz nähern. Der Aufwand ist aber eher gerechtfertigt, wenn man alle (!) Primzahlen mit diesen Eigenschaften charakterisieren will. So führen z.B. alleine die ersten beiden Bedingungen "2 und 3 quadratische Reste modulo $\begin{eqnarray*} p \end{eqnarray*}$ " zu $\begin{eqnarray*} p\equiv \pm 1\bmod 24 \end{eqnarray*}$ .

14.05.2018, 17:52

SoulOfMidgard

Auf diesen Beitrag antworten »

RE: Quadratische Reste von Primzahlen, Gleichungssystem

Zitat:

Original von Huggy

Zitat:

Original von SoulOfMidgard
Aber brute force brachte mich hier nicht weiter.

Mein Rechner kommt auf $\begin{eqnarray*} q=71 \end{eqnarray*}$ .

Ja aber ich müsste natürlich auch zeigen, dass es die kleinste Zahl ist und ich wüsste nicht wie ich das anstellen sollte ohne zu zeigen dass jede kleinere nicht funktioniert und per Hand wäre das deutlich zu viel Arbeit (ich muss es händisch lösen)..

14.05.2018, 17:59

SoulOfMidgard

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Man kann sich der Sache natürlich auch mit dem Quadratischen Reziprozitätsgesetz nähern. Der Aufwand ist aber eher gerechtfertigt, wenn man alle (!) Primzahlen mit diesen Eigenschaften charakterisieren will. So führen z.B. alleine die ersten beiden Bedingungen "2 und 3 quadratische Reste modulo $\begin{eqnarray*} p \end{eqnarray*}$ " zu $\begin{eqnarray*} p\equiv \pm 1\bmod 24 \end{eqnarray*}$ .

Ich sehe gerade nicht wie ich das anwenden muss. Benutze ich dieses nicht um ein Legendre Symbol zu berechnen? Wie soll ich es hier nutzen um ein System von Gleichungen die das Legendre Symbol beinhalten zu lösen?

14.05.2018, 18:23

HAL 9000

Auf diesen Beitrag antworten »

Aus dem Quadratischen Reziprozitätsgesetz inklusive Ergänzungssätzen folgt

$\begin{eqnarray*} \left( \frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = 1\qquad (1) \end{eqnarray*}$

$\begin{eqnarray*} \left( \frac{3}{p}\right) = (-1)^{\frac{p-1}{2}}\cdot \left( \frac{p}{3}\right) = 1\qquad (2) \end{eqnarray*}$

$\begin{eqnarray*} \left( \frac{5}{p}\right) = \left( \frac{p}{5}\right) = 1\qquad (3) \end{eqnarray*}$

$\begin{eqnarray*} \left( \frac{7}{p}\right) = (-1)^{\frac{p-1}{2}}\cdot \left( \frac{p}{7}\right) = -1\qquad (4) \end{eqnarray*}$ .

(1) bedeutet $\begin{eqnarray*} p=24k\pm 1 \end{eqnarray*}$ oder $\begin{eqnarray*} p=24k\pm 7 \end{eqnarray*}$ , letzteres verfehlt aber "Filter" (2), bleibt also erstmal nur $\begin{eqnarray*} p=24k\pm 1 \end{eqnarray*}$ übrig. Jetzt kann man das mit (3) und (4) weiter eingrenzen...

16.05.2018, 09:32

SoulOfMidgard

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
(1) bedeutet $\begin{eqnarray*} p=24k\pm 1 \end{eqnarray*}$ oder $\begin{eqnarray*} p=24k\pm 7 \end{eqnarray*}$ .

Es will sich mir nicht recht erschließen, wie sie darauf kommen. Ich nehme an das soll daraus resultieren, dass der Exponent ungerade sein muss, also $\begin{eqnarray*} 2k+1&=\frac{p^2-1}{8} \end{eqnarray*}$ aber damit komme ich nach Umformung auf $\begin{eqnarray*} p=\pm \sqrt{16k+7} \end{eqnarray*}$ . Was mache ich falsch? Desweiteren sehe ich indes auch nicht wie ich an diese "k-Bedingungen" für die anderen Gleichungen komme..

16.05.2018, 11:47

HAL 9000

Auf diesen Beitrag antworten »

1) Für $\begin{eqnarray*} p=4m\pm 1 \end{eqnarray*}$ gilt $\begin{eqnarray*} (-1)^{\frac{p^2-1}{8}} = (-1)^{2m^2\pm m} = (-1)^m \end{eqnarray*}$ , d.h. es wird nur dann 1, wenn $\begin{eqnarray*} m \end{eqnarray*}$ gerade ist. Also müssen die Primzahlen die Form $\begin{eqnarray*} p=8m'\pm 1 \end{eqnarray*}$ haben.

2) Jetzt schauen wir uns Gleichung (2) an unter Berücksichtigung von $\begin{eqnarray*} \left( \frac{1}{3}\right) = 1 \end{eqnarray*}$ sowie $\begin{eqnarray*} \left( \frac{-1}{3}\right) = -1 \end{eqnarray*}$ :

$\begin{eqnarray*} \left( \frac{3}{8m'+1}\right) = (-1)^{4m'}\cdot \left( \frac{8m'+1}{3}\right) = \left( \frac{-m'+1}{3}\right) = 1 \end{eqnarray*}$ erfordert $\begin{eqnarray*} m'=0\bmod 3 \end{eqnarray*}$ .

$\begin{eqnarray*} \left( \frac{3}{8m'-1}\right) = (-1)^{4m'-1}\cdot \left( \frac{8m'-1}{3}\right) = -\left( \frac{-m'-1}{3}\right) = 1 \end{eqnarray*}$ erfordert ebenfalls $\begin{eqnarray*} m'=0\bmod 3 \end{eqnarray*}$ .

Damit bleibt jeweils nur $\begin{eqnarray*} m'=3k \end{eqnarray*}$ und damit $\begin{eqnarray*} p=24k\pm 1 \end{eqnarray*}$ übrig.

3) Nun Gleichung (3), dabei berücksichtigen wir $\begin{eqnarray*} \left( \frac{\pm 1}{5}\right) = 1 \end{eqnarray*}$ sowie $\begin{eqnarray*} \left( \frac{\pm 2}{5}\right) = -1 \end{eqnarray*}$ :

$\begin{eqnarray*} \left( \frac{5}{24k+1}\right) = \left( \frac{24k+1}{5}\right) = \left( \frac{-k+1}{5}\right) = 1 \end{eqnarray*}$ erfordert $\begin{eqnarray*} k\equiv 0,2\bmod 5 \end{eqnarray*}$ .

$\begin{eqnarray*} \left( \frac{5}{24k-1}\right) = \left( \frac{24k-1}{5}\right) = \left( \frac{-k-1}{5}\right) = 1 \end{eqnarray*}$ erfordert $\begin{eqnarray*} k\equiv 0,-2\bmod 5 \end{eqnarray*}$ .

Insgesamt bedeutet dies $\begin{eqnarray*} p=120k'\pm 1 \end{eqnarray*}$ oder $\begin{eqnarray*} p=120k'\pm 49 \end{eqnarray*}$

4) Schließlich und endlich Gleichung (4), dabei berücksichtigen wir $\begin{eqnarray*} \left( \frac{1}{7}\right) = \left( \frac{2}{7}\right) = \left( \frac{-3}{7}\right) = 1 \end{eqnarray*}$ sowie $\begin{eqnarray*} \left( \frac{-1}{7}\right) = \left( \frac{-2}{7}\right) = \left( \frac{3}{7}\right) = -1 \end{eqnarray*}$ :

$\begin{eqnarray*} \left( \frac{7}{120k'+1}\right) = \left( \frac{120k'+1}{7}\right) = \left( \frac{k'+1}{7}\right) = -1 \end{eqnarray*}$ erfordert $\begin{eqnarray*} k'\equiv -2,-3,2\bmod 7 \end{eqnarray*}$ .

$\begin{eqnarray*} \left( \frac{7}{120k'-1}\right) = -\left( \frac{120k'-1}{7}\right) = -\left( \frac{k'-1}{7}\right) = -1 \end{eqnarray*}$ erfordert $\begin{eqnarray*} k'\equiv 2,3,-2\bmod 7 \end{eqnarray*}$ .

$\begin{eqnarray*} \left( \frac{7}{120k'+49}\right) = \left( \frac{120k'+49}{7}\right) = \left( \frac{k'}{7}\right) = -1 \end{eqnarray*}$ erfordert $\begin{eqnarray*} k'\equiv -1,-2,3\bmod 7 \end{eqnarray*}$ .

$\begin{eqnarray*} \left( \frac{7}{120k'-49}\right) = -\left( \frac{120k'-49}{7}\right) = -\left( \frac{k'}{7}\right) = -1 \end{eqnarray*}$ erfordert $\begin{eqnarray*} k'\equiv 1,2,-3\bmod 7 \end{eqnarray*}$ .

Das ergibt die möglichen Primzahlkandidaten $\begin{eqnarray*} 840k\pm 71,840k\pm 191,840k\pm 239,840k\pm 241,840k\pm 359,840k\pm 409 \end{eqnarray*}$ . Von denen ist dann 71 die kleinste mögliche Primzahl, ja.

Wie gesagt, ein enormer Aufwand, und man hat viel mehr erreicht, als man eigentlich braucht: Nämlich eine genaue Charakterisierung der Primzahlen, die diesen vier Bedingungen genügen.

Neue Frage »

Antworten »

Quadratische Reste von Primzahlen, Gleichungssystem

Verwandte Themen