Quadratischer Rest

15.01.2009, 14:03	Bjoern1982	Auf diesen Beitrag antworten »
Quadratischer Rest Hallo, noch eine kurze Frage zu QR: Sei p eine ungerade Primzahl z.z.: Der kleinste quadratische Nichtrest NQR modulo p ist immer prim. Evtl wieder indirekt ? Auch hier komme ich nicht weiter... Gruß Björn
15.01.2009, 17:54	tmo	Auf diesen Beitrag antworten »
Ja, indirekt würde ich es machen. Nehme an n sei zusammengesetzt und sei der kleinste Nichtrest modulo p. Also sind alle Primfaktoren von n quadratische Reste modulo p.
15.01.2009, 19:45	Bjoern1982	Auf diesen Beitrag antworten »
Soweit klar, bis jetzt ja noch kein Widerspruch. Was folgere ich daraus ? Einzige wage Idee im Moment von mir mit dem Jacobi Symbol zu argumentieren, welches -1 wird für Nichtrest n, jedoch wegen der Multiplikativität kann man wenn n NUR aus quadratischen Resten besteht nicht mehr auf -1 kommen, da das Jacobi-Symbol für quadratische Reste ja immer den Wert 1 annimmt. Hmm...wenn ich drüber nachdenke vielleicht doch der richtige Gedanke oder woran hattest du gedacht? Gruß Björn
15.01.2009, 19:55	tmo	Auf diesen Beitrag antworten »
Man kann doch n zerlegen in 2 Faktoren: $\begin{eqnarray} n = ab \end{eqnarray}$ Da a und b quadratische Reste modulo p sind, gibt es $\begin{eqnarray} x_1,x_2 \end{eqnarray}$ mit $\begin{eqnarray} x_1^2 \equiv a \pmod p \end{eqnarray}$ $\begin{eqnarray} x_2^2 \equiv b \pmod p \end{eqnarray}$ Nun betrachte $\begin{eqnarray} x_1^2x_2^2 \end{eqnarray}$
15.01.2009, 20:03	Bjoern1982	Auf diesen Beitrag antworten »
Achso was du meinst ist, dass dann ab wegen $\begin{eqnarray} x_1^2x_2^2=(x_1x_2)^2 \end{eqnarray*}$ dadurch quadratischer Rest sein müsste, was ein Widerspruch zur Annahme ist ?
15.01.2009, 20:05	tmo	Auf diesen Beitrag antworten »
Ja, darauf wollte ich hinaus.
Anzeige

15.01.2009, 20:07	Bjoern1982	Auf diesen Beitrag antworten »
Prima, dank dir. Noch ein Kommentar zu meiner Variante oben mit dem Jacobi Symbol ? Ist das auch möglich oder ist da irgendwo ein Denkfehler ?
15.01.2009, 20:17	tmo	Auf diesen Beitrag antworten »
Habe ehrlich gesagt noch nichts von Jacobi-Symbolen gehört, aber nachdem ich den Wikipediaartikel dazu gelesen habe, spricht doch nix dagegen, dass man es auch damit beweisen kann: Wir nehmen ja an: $\begin{eqnarray} \left( \frac{n}{p} \right) = -1 \end{eqnarray}$ . Da aber für alle Primfaktoren $\begin{eqnarray} p_i \end{eqnarray}$ von n gilt: $\begin{eqnarray} \left( \frac{p_i}{p} \right) = 1 \end{eqnarray}$ , ist das ja wegen der Multiplikativität des Zählers ein Widerspruch, weil man damit $\begin{eqnarray} \left( \frac{n}{p} \right) = 1 \end{eqnarray}$ folgern kann. Ist ja letztendlich von der Idee her der selbe Beweis, nur dass er statt dem Kalkül der Kongruenzrechnung halt das Jacobi-Symbol nutzt.
15.01.2009, 20:32	Bjoern1982	Auf diesen Beitrag antworten »
Wunderbar, dann darf sich der Korrektor was aussuchen - ist ja beides ziemlich kurz

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »