Quadratische Reziprozität

24.08.2011, 21:02

free2k

Quadratische Reziprozität

Hallo,
ich brauche ein wenig Hilfe beim Berechnen des Quadratische Reziprozität

Ich habe p = 12345653 und q = 2345699, was beides Primzahlen sind.
Untersuchen sie, ob q ein quadratischer Rest modulo p ist.

$\begin{eqnarray*} \frac{p}{q} \end{eqnarray*}$ = $\begin{eqnarray*} \frac{12345653}{2345699} \end{eqnarray*}$

Zunächst teste ich beide Primzahlen modulo 4

12345653 mod 4 = 1
2345699 mod 4 = 3

Aber wie rechne ist jetzt weiter und was bedeutet das?

24.08.2011, 23:18

Reksilat

Auf diesen Beitrag antworten »

RE: Quadratische Reziprozität
Hallo free2k,

Das Legendre-Symbol $\begin{eqnarray*} \left(\frac{p}{q}\right) \end{eqnarray*}$ (das im Übrigen normalerweise mit Klammern drum geschrieben wird) lässt sich vor allem für kleine $\begin{eqnarray*} q \end{eqnarray*}$ berechnen, da man für kleine Primzahlen einfach alle quadratischen Reste ausrechnen kann.
Insofern ist hier die QR fehl am Platze, da Du damit das Symbol drehen würdest und unten etwas größeres stehen würde.

Benutze zunächst, dass $\begin{eqnarray*} \left(\frac{p}{q}\right)=\left(\frac{a}{q}\right) \end{eqnarray*}$ für alle $\begin{eqnarray*} a \end{eqnarray*}$ mit $\begin{eqnarray*} a\equiv p\pmod q \end{eqnarray*}$ ist.
Berechne also p modulo q und setze das für p ein.

Gruß,
Reksilat.

25.08.2011, 22:36

free2k

Auf diesen Beitrag antworten »

Hallo Reksilat!

Also p mod q = 12345653 mod 2345699 = 617158

Nun zerlege ich 617158 in Primfaktoren, damit ich kleine Primzahlen habe.

Also 617158 = 2 * 19 * 109 * 149

Somit: $\begin{eqnarray*} \frac{2 * 19 * 109 * 149}{2345699} \end{eqnarray*}$

Wie gehts jetzt aber weiter?

Gruß,
free2k

25.08.2011, 22:47

Reksilat

Auf diesen Beitrag antworten »

Du hast jetzt $\begin{eqnarray*} \left(\frac{12345653}{2345699}\right)=\left(\frac{617158}{2345699}\right)=\left(\frac{2}{2345699}\right)\cdot\left(\frac{19}{2345699}\right)\cdot\left(\frac{109}{2345699}\right)\cdot\left(\frac{149}{2345699}\right) \end{eqnarray*}$

Nun kannst Du die vier Faktoren ausrechnen. Für $\begin{eqnarray*} \left(\frac{2}{...}\right) \end{eqnarray*}$ gibt es eine feste Regel; bei den anderen ist es sinnvoll, sie mittels QR umzudrehen.

Gruß,
Reksilat.

28.08.2011, 21:00

free2k

Auf diesen Beitrag antworten »

Ich teste also bei QR immer mod 4 und wende dann die Regeln an!?

2345699 mod 4 =3
19 mod 4 = 3
109 mod 4 = 1
149 mod 4 = 1

Folglich:

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

$\begin{eqnarray*} \left(\frac{19}{2345699}\right) = (-1) * (\frac{16}{19}) \end{eqnarray*}$

$\begin{eqnarray*} \left(\frac{109}{2345699}\right) = (\frac{19}{109}) \end{eqnarray*}$

$\begin{eqnarray*} \left(\frac{149}{2345699}\right) = (\frac{141}{109}) \end{eqnarray*}$

Stimmt das soweit?

28.08.2011, 21:25

jester.

Auf diesen Beitrag antworten »

Zitat:

Original von free2k
$\begin{eqnarray*} \left(\frac{2}{2345699}\right) = (-1) * 2^\frac{2345699-1}{8} \end{eqnarray*}$

Da hat sich ein kleiner Schreibfehler eingeschlichen: $\begin{eqnarray*} \left(\frac{2}{2345699}\right) = (-1) ^\frac{2345699-1}{8} \end{eqnarray*}$ .

Ansonsten ist das bisher richtig.

28.08.2011, 22:15

free2k

Auf diesen Beitrag antworten »

@jester.

Ja stimmt.

Jetzt kann ich ja mit den Termen weiter auflösen?

Ein paar Fragen noch:
- Wann zerlege ich eine Zahl in Primfaktoren
- Und wie weit zerlege ich die weiteren Terme?

$\begin{eqnarray*} (-1) * (\frac{16}{19}) = (-1) * (\frac{3}{16}) \end{eqnarray*}$

$\begin{eqnarray*} (\frac{19}{109}) = (\frac{14}{19}) \end{eqnarray*}$

$\begin{eqnarray*} (\frac{141}{149}) = (\frac{8}{141}) \end{eqnarray*}$

28.08.2011, 22:25

jester.

Auf diesen Beitrag antworten »

Zitat:

Original von free2k
- Wann zerlege ich eine Zahl in Primfaktoren

Es gibt zwar in der Mathematik fast nie Patentrezepte, aber wenn man $\begin{eqnarray*} \left(\frac n p \right) \end{eqnarray*}$ berechnen möchte, ist oftmals zunächst sinnvoll, den "Zähler" $\begin{eqnarray*} n \end{eqnarray*}$ auf einen geeigneten Vertreter $\begin{eqnarray*} \mod p \end{eqnarray*}$ zu bringen - gerne auch mal mit negativem Vorzeichen.

Zitat:

- Und wie weit zerlege ich die weiteren Terme?

Ich würde sagen so lange zerlegen, bis man das Legendre-Symbol berechnen kann.

Um hier weiterzumachen sind noch folgende Dinge zu erledigen:

$\begin{eqnarray*} \left(\frac 2 {2345699}\right) \end{eqnarray*}$ ausrechnen - dazu kann man alternativ zu dieser Potenz auch überprüfen, was $\begin{eqnarray*} 2345699 \mod 8 \end{eqnarray*}$ ist. Dabei fällt mir gerade auf, dass sich da noch ein Fehler eingeschlichen hat. Man muss den "Nenner" quadrieren - lies noch mal die von Reksilat verlinkte Regel durch.

$\begin{eqnarray*} \left(\frac {16} {19}\right) \end{eqnarray*}$ : da gibt es nichts mehr zu rechnen - warum?

$\begin{eqnarray*} \left(\frac {19} {109}\right) \end{eqnarray*}$ und $\begin{eqnarray*} \left(\frac {141} {149}\right) \end{eqnarray*}$ (noch ein Schreibfehler bei dir): da würde ich beim ersten das quadratische Reziprozitätsgesetz noch einmal anwenden. Beim zweiten bietet sich an $\begin{eqnarray*} \left(\frac {141} {149}\right)=\left(\frac {-8} {149}\right)=\left(\frac {-1} {149}\right)\left(\frac {2} {149}\right) \end{eqnarray*}$ (Überlege dir, warum das richtig ist).

28.08.2011, 22:28

jester.

Auf diesen Beitrag antworten »

Zitat:

Original von free2k
$\begin{eqnarray*} (\frac{141}{149}) = (\frac{8}{141}) \end{eqnarray*}$

Das ist sozusagen tödlich, denn $\begin{eqnarray*} 141=3\cdot 47 \end{eqnarray*}$ ist keine Primzahl, das quadratische Reziprozitätsgesetz ist jedoch nur für Primzahlen richtig.

Neue Frage »

Antworten »

Quadratische Reziprozität

Verwandte Themen