Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Existenz eines kleinen quadratischen Nichtrestes
Druckversion
Druckversion
Autor
Kein bestimmter Bereich J Existenz eines kleinen quadratischen Nichtrestes
Mano
Neu Letzter Besuch: in der letzten Woche
Dabei seit: 27.05.2020
Mitteilungen: 3
Aus: NRW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-07-03


Hallo zusammen,

ich versuche gerade folgende Aufgabe zu lösen:

Es sei <math>p\equiv1</math> (mod 4) eine Primzahl. Zeige,
dass dann ein quadratischer Nichtrest <math>r</math> modulo <math>p</math> existiert mit <math>1<r<\sqrt{p}</math>.

Bisher habe ich versucht, Information über <math>p</math> herauszufinden, indem ich kleine Werte von <math>r</math> eingesetzt habe. Das funktioniert wegen <math>p>4</math> für <math>r=2</math>, nach dem quadratischen Reziprozitätsgesetz folgt <math>p\equiv1</math> (mod 8).
Analog kann ich unter Verwendung des chinesischen Restsatzes auf <math>p\equiv1</math> (mod 24) und <math>p\equiv1</math> oder <math>p\equiv49</math> (mod 120) schließen. Modulo 840 kommen die Restklassen 1, 121, 169, 289, 361 und 529 infrage(diese sind genau die Restklassen, zu der Quadrate von Primzahlen gehören können, und außerdem auch Quadrate der zu 24 teilerfremden Zahlen von 1 bis 23). Die erste davon kann ich zeigen, die zweite nicht. Dass ich immer weitere Primzahlen als Moduli betrachten kann, lässt sich mit einfachen Primzahlabschätzungen zeigen, etwa mit der Tatsache, dass es zwischen <math>p</math> und <math>2p</math> immer eine Primzahl gibt. Leider geht das Spiel nicht mehr so schön weiter, modulo 9240 bekomme ich nicht einmal nur Quadratzatzahlen:
{1, 7681, 2689, 3721, 4489, 7561, 529, 1681, 3481, 6169, 8089, 289, 2209, 169, 5041, 1849, 8761, 961, 5569, 841, 3529, 5329, 2641, 1369, 6241, 4321, 361, 6889, 7921, 2809}
Leider ist 7681 sogar prim. Deswegen Frage bezweifle ich, ob dieser Ansatz überhaupt sinnvoll ist. Für einen kleinen Tipp oder Hinweis, in welche Richtung die Aufgabe geht, wäre ich dankbar. (Bitte keine vollständige Lösung, die möchte ich selbst finden!)

Viele Grüße,
Mano



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2245
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-07-03

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
Hallo,

ich kenne einen Beweis dafür, dass für jede ungerade Primzahl $p$ ein quadratischer Nichtrest $a$ mit $0<a<\sqrt p +1$ existiert. (*)
Leider sehe ich im Moment nicht, wie man diese Schranke unter Ausnutzung von $p\equiv 1\pmod 4$ zu $0< a < \sqrt  p$ verbessern kann. Aber vielleicht hilft es trotzdem.

Hier ist eine Skizze des Beweises (sag Bescheid, wenn du mehr Details willst):
Sei $a>0$ der minimale quadratische Nichtrest modulo $p$ und sei $b:=\lfloor \frac pa\rfloor +1$.
Aus der Minimalität von $a$ kann man folgern, dass $ab-p$ ein quadratischer Rest und somit $b$ ein Nichtrest sein muss.
Daher gilt $a\leq b < \frac pa+1$, woraus man die Behauptung (*) folgern kann.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Mano
Neu Letzter Besuch: in der letzten Woche
Dabei seit: 27.05.2020
Mitteilungen: 3
Aus: NRW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-07-04


Hallo,

danke für die schnelle Antwort und die gute Idee. Ich habe deine Antwort nachvollziehen können und habe selbst den Beweis gefunden.
Man betrachte für den minimalen quadratischen Nichtrest <math>a>0</math> stattdessen <math>c:=\lfloor\frac{p}{a}\rfloor</math> mit <math>\frac{p}{a}-1<c<\frac{p}{a}</math>, also <math>p-a<ac<p</math>. Wegen der Minmalität von <math>a</math> und <math>p\equiv1\,(\text{mod}\,4)</math> ist <math>ac</math> quadratischer Rest, also <math>c</math> quadratischer Nichtrest mit <math>a\leq c<\frac{p}{a}</math>, also <math>a<\sqrt{p}</math>. Wunderschön.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Mano hat die Antworten auf ihre/seine Frage gesehen.
Mano hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]