0 Daumen
335 Aufrufe

Aufgabe:

Hallo, ich komme bei folgender Aufgabe leider nicht weiter..

man solle alle Primzahlen p bestimmten, bei denen 3 ein quadratischer Rest modulo p ist.


Problem/Ansatz:

Wie man quadratische Reste im allgemeinen bestimmt, weiß ich. Aber leider komme ich nicht weiter, wie ich ALLE Primzahlen bestimme..

Ich weiß dass ich ein p Suche, sodass x2=3 (mod p) gelten muss. Und mein x wähle ich aus {12, 22, ..., ((p-1)/2)2}.

Ich habe bereits, 2,3,5 ausgeschlossen. Durch austesten habe ich herausgefunden, dass für 11 3 ein quadratischer Rest modulo 11 ist.

Aber wie finde ich Alle Primzahlen heraus?


Ich hoffe ihr könnt mir helfen

von

4^2 = 3 (mod 13)

1 Antwort

+1 Daumen
 
Beste Antwort

Hallo,

Das kann man z.B. mit dem quadratischen Reziprozitätsgesetz angehen:

Für p=3 ist 3=0 also kein quadratischer Rest,

Für p>3 ist 3 genau dann ein quadratischer Rest wenn das Legendre Symbol "3 über p" den Wert 1 hat:

$$ \left(\frac{3}{p}\right) = 1 $$

Es gilt (QRG):

$$ \left(\frac{3}{p}\right) = (-1)^{\frac {3-1}{2}\frac {p-1}{2}}\left(\frac{p}{3}\right) =  (-1)^{\frac {p-1}{2}}\left(\frac{p}{3}\right)  $$ Das ist also gleich 1 wenn: $$ p \equiv 3 \mod (4), \quad p\equiv 2 \mod (3)$$(beide Faktoren =-1) Oder $$ p \equiv 1 \mod (4), \quad p\equiv 1 \mod (3)$$ (beide Faktoren =1)

Jetzt hast du zwei Systeme linearer Kongruenzen, kannst du diese lösen?

von 1,3 k

Danke für deine tolle Antwort. JEdoch wüsste ich nicht, wie ich hier weiterrechnen sollte...

Exemplarisch zeig ich dir das mal für das erste System:

$$ p \equiv 3 \mod (4), \quad p\equiv 2 \mod (3) $$

Die Moduli (3, 4) sind teilerfremd, also existieren gemäß chinesischem Restsatz auf jeden Fall Lösungen. Diese sind eindeutig modulo kgV(3,4) = 12. Wir suchen jetzt erst einmal eine ganze Zahl x mit

$$ x \equiv \color{blue}{3}\mod (\color{green}{4}), \quad x\equiv \color{red}{2} \mod (\color{purple}{3}) $$

Der Ansatz ist folgender:

$$ x = \color{blue}{3} \cdot \color{purple}{3} \cdot a + \color{red}{2} \cdot \color{green}{4} \cdot b $$

denn wenn du das modulo 3 und 4 betrachtest:

$$ x \equiv \color{blue}{3} \cdot \color{purple}{3} \cdot a \mod (\color{green}{4}) $$ $$ x \equiv \color{red}{2} \cdot \color{green}{4} \cdot b \mod (\color{purple}{3}) $$

Um zu erreichen, dass bei der ersten Kongruenz 3 rauskommt müssen wir a so wählen, dass \( \color{purple}{3} \cdot a \equiv 1 \mod (\color{green}{4}) \), dann gilt nämlich $$ x \equiv \color{blue}{3} \cdot 1 \equiv \color{blue}{3} \mod (\color{green}{4}) $$ analog muss \( \color{green}{4} \cdot b \equiv 1 \mod (\color{purple}{3}) \) sein. a und b könntest du jetzt mit dem erweiterten euklidischen Algorithmus bestimmen oder raten. Es geht z.B. a = 3, b = 1, also ist eine Lösung $$ x = 3\cdot 3 \cdot 3 + 2 \cdot 4 \cdot 1 = 35 $$

d.h. alle \( p \) mit \( p \equiv 35 \equiv11 \mod (12) \) sind eine Lösung dieses Systems, insbesondere ist für alle Primzahlen kongruent 1 modulo 12 die 3 ein quadratischer Rest modulo \(p\).

Versuche das andere System jetzt mal selbst.

oh wow, vielen lieben dank für deine ausführliche Antwort und damit verbundene Hilfe.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community