alle Primzahlen mit best. quadratischen Rest

10.07.2005, 23:05

sanna

alle Primzahlen mit best. quadratischen Rest

Hallo,

kann mir jemand sagen, wie ich alle Primzahlen finden kann, die
a) -3 als quadratischen Rest
b) 5 als quadratischen Rest
c) -5 als quadratischen Rest
haben?

10.07.2005, 23:21

JochenX

Auf diesen Beitrag antworten »

ich verstehe deine frage nicht
als "quadratischen Rest" wird laut wikipedia der rest bezeichnet, den quadratzahlen bei modulorechnung lassen

aber quadratzahlen sind niemals prim...
oder wie ist das gemeint?

10.07.2005, 23:36

sqrt(2)

Auf diesen Beitrag antworten »

In der Wikipedia steht genau:

Zitat:

Der quadratische Rest ist der Modulo der Division einer Quadratzahl durch eine natürliche Zahl.

Ich interpretiere das als Suche nach allen $\begin{eqnarray*} p\in \mathbb{P} \end{eqnarray*}$ für die gilt

$\begin{eqnarray*} n^2\equiv p \mod m \end{eqnarray*}$

mit $\begin{eqnarray*} m\in\{-3;5;-5\} \end{eqnarray*}$ .

10.07.2005, 23:37

sanna

Auf diesen Beitrag antworten »

Das ist der Orginaltext von meinem Uebungsblatt... Ich bin auch der Meinung, dass da irgendetwas fehlt z.B. der Modul.

Zu deiner Frage:
$\begin{eqnarray*} x^2 \equiv 12 (mod 13) \end{eqnarray*}$

dann ist auch p=5 eine Loesung.

10.07.2005, 23:44

sanna

Auf diesen Beitrag antworten »

Zitat:

Also, wir haben in der Vorlesung gelernt,dass

$\begin{eqnarray*} a quadratischer Rest (mod m) \Leftrightarrow x^2 \equiv a (mod m) loesbar \end{eqnarray*}$

also muessten 3,5,-5 an Stelle von deinem p stehen...

10.07.2005, 23:53

sqrt(2)

Auf diesen Beitrag antworten »

Zitat:

Original von sanna
also muessten 3,5,-5 an Stelle von deinem p stehen...

Das ergibt mehr Sinn (auch wenn ich die Wikipedia dann sehr missverständlich finde), denn zumindest für mein Verständnis gilt $\begin{eqnarray*} a\equiv b \pmod {-m}~\Leftrightarrow~a\equiv b \pmod m \end{eqnarray*}$ . Deine Aufgabe wäre dann teilweise sinnlos.

10.07.2005, 23:58

dfg

Auf diesen Beitrag antworten »

Erstmal Definition von Quadratischen Resten :

Sei $\begin{eqnarray*} m \in \mathbb N, m > 1, a \in \mathbb Z, ggT(a,m)=1 \end{eqnarray*}$

Dann heißen alle Lösungen der Kongruenz $\begin{eqnarray*} x^2 \equiv a ~(mod ~ m) \end{eqnarray*}$ Quadratischer Rest.

Du sollst jetzt alle p finden für die $\begin{eqnarray*} b \in \{ -3,5,-5\} \end{eqnarray*}$
Lösungen der Kongruenz $\begin{eqnarray*} x^2 \equiv a ~ (mod ~ p) \end{eqnarray*}$

oder

$\begin{eqnarray*} x^2 \equiv p ~ (mod ~ m) \end{eqnarray*}$ ist.

Welches gemeint ist geht aus der Aufgabe nicht hervor, da Primzahlen keine Quadratischen Reste haben, nur Kongruenzen können Quadratische Reste haben.

11.07.2005, 00:06

sanna

Auf diesen Beitrag antworten »

und wie kann ich die nun rausfinden, ohne das fuer x Primzahlen auszurechnen????

11.07.2005, 00:18

dfg

Auf diesen Beitrag antworten »

Lösen kannst du sowas dann mit dem Legendre-Symbol.
Einfach bei Wikipedia nachschaun da sind sogar Beispiele.

11.07.2005, 00:19

Auf diesen Beitrag antworten »

Wenn du solche Aufgaben bearbeiten sollst, kennst du doch bestimmt das Quadratische Reziprozitätsgesetz (inklusive der beiden Ergänzungssetze). Dieses Gesetz liefert eine Antwort auf deine Frage.

EDIT: Da war dfg wohl schneller... Augenzwinkern

Neue Frage »

Antworten »

alle Primzahlen mit best. quadratischen Rest

Verwandte Themen