Quadratische Reste modulo p

Question

Aufgabe:

Es sei p eine ungerade Primzahl. Es sei q > 1 die kleinste ganze Zahl, die kein Quadrat modulo
p ist. Dann ist q eine Primzahl und q <√p + 1

Comments

Also ich hätte mir jetzt eine ungerade Primzahl p ausgesucht.

Dann hätte ich1², 2², 3² usw. bis (p-1)² mod p ausgerechnet.

Dann hätte ich mal geschaut, welche Ergebnisse NICHT vorkommen und was das kleinste dieser nicht vorkommenden Ergebnisse ist.

Dann hätte ich das Ganze mit einer weiteren Primzahl nochmal versucht.

So etwas nennt sich "entdeckendes Lernen".

Mach mal und teile deine Ergebnisse mit. Dann sehen wir weiter.

---

Die kleinste Lösung die nie vorkommt ist  die 0.

Andere nicht vorkommende Lösungen: bei p=3 : 0,2

                                                                  p=5 : 0,2,3

                                                                  p=7 : 0,3,5,6

---

Mein Fehler. Statt

 1², 2², 3² usw. bis (p-1)²

hätte ich 0², 1², 2² ... schreiben müssen. 0 ist ein quadratischer Rest, weil 0²=0 mod p gilt.

---

0 ist ein quadratischer Rest, weil 0²=0 mod p gilt.

0 ist kein quadratischer Rest, denn ggT(0,p)=p≠1.

---

haben es jetzt gemacht, aber finden nicht so wirklich raus was uns das bringen könnte.

---

kennst du schon das Legendre Symbol?

---

ja das kennen wir

---

Dann ist das nicht schwer, ich schreibe ( a / p ) für das Legendresymbol a über p

Macht einen Widerspruchsbeweis. Sei q>1 die kleinste ganze Zahl welche kein Quadrat ist, dann ist q<p (es gibt im quadratische Nichtreste) insb ggT(q,p)=1.

Und ( q / p ) = -1

Angenommen q wäre jetzt zusammengesetzt q = u * v, dann ist ggT(u,p)=1 und ggT(v,p)=1

beide sind also entweder quadratische Reste oder Nichtreste es ist also

( u / p ) = ±1 und ( v / p ) = ±1

Das Legendre Symbol ist multiplikativ:

-1 = ( q / p ) = ( u / p ) * ( v / p )

Einzige Möglichkeit dass die Gleichung erfüllt ist. Eins von beiden ist -1 das jeweils andere 1

Wegen u, v < q hat man damit aber auf jeden Fall eine kleinere Zahl als q gefunden die ebenfalls kein Quadrat ist. Das ist aber ein Widerspruch zur Minimalität von q.

---

Aber dann ist ja nur gezeigt, dass q die kleinste Zahl ist, aber nicht, dass q<\( \sqrt{x} \)p + 1

---

Dann ist gezeigt, dass q eine Primzahl sein muss.

Wenn jetzt q der kleine quadratische Nichtrest ist, dann kann man mal Polynomdivision mit Rest durchführen: Ex existieren eindeutig bestimmte x, r mit

p = x * q - r mit 0 < r < q... Warum geht r = 0 nicht?

Umformen r = x*q - p. Legendre Symbol verwenden:

( r / p ) = ( (x*q-p) / p )

Das Legendre Symbol ändert sich aber nicht wenn man zu der Zahl Vielfache von p addiert:

( r / p ) = ( (x*q-p) / p ) = ( x*q / p ) = ( x / p ) * ( q / p )

r ist jetzt ein quadratischer Rest, warum? Links steht somit eine 1

q ist quadratischer Nichtrest, Rechts steht also ( x / p ) * (-1)

Das geht nur auf, wenn ( x / p ) = -1, d.h. x quadratischer Nichtrest ist, und das geht nur falls x >= q. Warum?

x*q - p = r < q => x*q < p + q => x < p/q + 1 => q < p/q + 1

Falls q >= sqrt(p) + 1 ist p/q < sqrt(p), insb. q < p/q + 1 < sqrt(p) + 1. Widerspruch.