Quadratische Reste < Wettbewerbe < Schule < Mathe < Vorhilfe
|
Hallo,
ich möchte zeigen, dass [mm] x^2\equiv-3 [/mm] (mod p) nur für [mm] p\equiv1 [/mm] (mod 3)
lösbar ist.
Meine Idee dazu war, dass ich zeige, dass aus [mm] x²\equiv-3 [/mm] irgendwie dazu führt, dass ord p (x)=3 folgt., dann wäre ja [mm] x³\equiv1 [/mm] (mod p), und das ist gleichbedeutend damit, dass 3|(p-1) also p=3k+1.
Aber ich weiß nicht wie ich zeigen soll, dass [mm] x³\equiv1 [/mm] (mod 3) folgt. Wäre nett, wenn ihr mir helfen könntet.? ;D
Lg, David
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:45 Mi 15.06.2011 | | Autor: | abakus |
> Hallo,
> ich möchte zeigen, dass [mm]x^2\equiv-3[/mm] (mod p) nur für
> [mm]p\equiv1[/mm] (mod 3)
> lösbar ist.
Hallo,
diese Aussage kannst du nicht beweisen, weil sie falsch ist.
Für p=3 ist [mm]x^2\equiv-3[/mm] (mod 3) auch lösbar, obwohl nicht gilt
[mm]3\equiv1[/mm] (mod 3).
Gruß Abakus
> Meine Idee dazu war, dass ich zeige, dass aus [mm]x²\equiv-3[/mm]
> irgendwie dazu führt, dass ord p (x)=3 folgt., dann wäre
> ja [mm]x³\equiv1[/mm] (mod p), und das ist gleichbedeutend damit,
> dass 3|(p-1) also p=3k+1.
> Aber ich weiß nicht wie ich zeigen soll, dass [mm]x³\equiv1[/mm]
> (mod 3) folgt. Wäre nett, wenn ihr mir helfen könntet.?
> ;D
>
> Lg, David
|
|
|
| |
|
Entschuldige, ich habe vergessen, die Zusatzbedingung zu nennen.
p ist prim und [mm] \ge5.
[/mm]
Nun, in einer Teilaufgabe habe ich bewiesen, dass 2h+1 eine Lösung für x ist, genau dann, wenn ord p(h)=3 bzw. p [mm] \equiv [/mm] 1 (mod 3).
Also müsste ich zeigen, dass wenn [mm] x^2\equiv-3 [/mm] (mod p) löst, dass x dann ungerade sein muss, oder? Daran hänge ich.
Die andere Richtung konnte ich bereits beweisen, also dass, wenn [mm] p\equiv1 [/mm] (mod 3), dass dann ein x existiert, für das [mm] x^2\equiv-3 [/mm] (mod p)
Mein Problem ist, zu zeigen, dass x der Form 2h+1 ist.
Lg, David
|
|
|
| |
|
Hallo David,
es ist doch vollkommen witzlos zu zeigen, dass eine beliebige ungerade Zahl x in die genannte Restklasse fällt. Wäre x nämlich gerade, so wäre x+p ungerade und dennoch in der gleichen Restklasse.
Mir scheint es einfacher, ohne Änderung der Aufgabe [mm] p\equiv 1\mod{\blue{6}} [/mm] zu setzen. Da reden wir immer noch von den gleichen Primzahlen, haben aber z.B. kein Problem mehr mit dem Eulerschen Kriterium für quadratische Reste.
Soweit ich sehe, solltest Du am besten zeigen, dass für Primzahlmoduln der Form [mm] 6k\blue{-}1 [/mm] die (-3) kein q.R. sein kann.
Grüße
reverend
|
|
|
| |
|
Ich habe es heute einfach nicht drauf, Beiträge zu verfassen. xD Nochmals sry. Ich änder den obigen Beitrag sodass er richtig ist. Da sollten nämlich eigentlich überall Quadrate stehen.
Lg, David
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:50 Mi 15.06.2011 | | Autor: | reverend |
Na, dann bin ich gespannt, was "überall" heißt.
Quadrate gehen hier nicht mit den komischen ASCII-Zeichen, sondern mit LaTeX: [mm] x^2 [/mm] schreibt man x^2, und wenn der Exponent mehr als ein Zeichen haben soll, muss er in geschweifte Klammern. e^{4x-1} ergibt also [mm] e^{4x-1} [/mm] etc.
Grüße
rev
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:16 Mi 15.06.2011 | | Autor: | KingStone007 |
Hallo, ich habe den Beitrag geändert. Hat jmd. vielleicht eine Idee dazu.? :)
Lg, David
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:10 Mi 15.06.2011 | | Autor: | reverend |
Hallo David,
da muss was schiefgegangen sein. Es ist keine Änderung abgespeichert worden. Bisher steht also nur der Eintrag drin, so wie Du ihn zuerst eingegeben hast.
Nur der Starteintrag ist einmal redigiert worden, von Angela.
Grüße
reverend
|
|
|
| |
|
So, nun sollte es aber geändert worden sein.?!
Lg, David
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:24 Mi 15.06.2011 | | Autor: | reverend |
Hallo,
> So, nun sollte es aber geändert worden sein.?!
Naja, aber nicht wesentlich. Mein Einwand bleibt der gleiche: Du wirst es nicht nachweisen können, weil zu jedem ungeraden x, das die Ausgangsäquivalenz erfüllt, x+p ein entsprechendes gerades x ist, und umgekehrt.
Das ist ein Irrweg.
Einen Hinweis auf eine andere Herangehensweise habe ich oben auch schon gegeben.
Grüße
reverend
|
|
|
| |
|
Hm, dann eine Frage: Ich konnte folgenden Satz beweisen:
Eine ganze Zahl h hat genau dann die Eigenschaft 'Ordnung von h zur Primzahl p ist 3'aufweist, wenn 2h+1 eine Lösung der Kongruenz [mm] x^2\equiv-3 [/mm] (mod p) vorstellt.
Wenn ich zeigen will, dass [mm] x^2\equiv-3 [/mm] (mod p) nur für [mm] p\equiv1 [/mm] (mod 3) erfüllt werden kann, dann habe ich doch aber obigen Satz verwenden, denn 'Ordnung von h zur Primzahl p ist 3' ist doch äuivalent dazu, dass [mm] p\equiv1 [/mm] (mod 3) ist, oder?
Und wenn ich obigen Satz verwende, dann muss x doch dieser Form 2h+1 sein. Andererseits versteh ich deinen Gedankengang, aber irgendwie raff ich das nicht.
Lg, David
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:19 Do 16.06.2011 | | Autor: | felixf |
Moin!
> Hm, dann eine Frage: Ich konnte folgenden Satz beweisen:
>
> Eine ganze Zahl h hat genau dann die Eigenschaft 'Ordnung
> von h zur Primzahl p ist 3'aufweist, wenn 2h+1 eine Lösung
> der Kongruenz [mm]x^2\equiv-3[/mm] (mod p) vorstellt.
Woraus folgt: die Kongruenz [mm] $x^2 \eqiuv [/mm] -3 [mm] \pmod{p}$ [/mm] hat genau dann eine Loesung, wenn es ein Element der Ordnung 3 in [mm] $(\IZ/p\IZ)^\ast$ [/mm] gibt.
Denn: hat $h$ die Ordnung 3 modulo $p$, so ist $2 h + 1$ eine Loesung der Kongruenz. Ist alternativ $y$ eine Loesung der Kongruenz, so ist entweder $y$ oder $y + p$ ungerade (und $y + p$ ist ebenfalls eine Loesung), wir koennen also ohne Einschraenkung annehmen, dass $y$ ungerade ist, also von der Form $2 h + 1$. Nach deinem Satz ist dann $h$ ein Element der Ordnung 3 modulo $p$.
> Wenn ich zeigen will, dass [mm]x^2\equiv-3[/mm] (mod p) nur für
> [mm]p\equiv1[/mm] (mod 3) erfüllt werden kann, dann habe ich doch
> aber obigen Satz verwenden, denn 'Ordnung von h zur
> Primzahl p ist 3' ist doch äuivalent dazu, dass [mm]p\equiv1[/mm]
> (mod 3) ist, oder?
Nein, das ist nicht aequivalent dazu. Die Aussage "Ordnung von $h$ zur Primzahl $p$ ist 3" impliziert, dass $p [mm] \equiv [/mm] 1 [mm] \pmod{3}$ [/mm] ist, da es ansonsten kein Element der Ordnung 3 gibt. Hast du jedoch ein beliebiges $h$ und ist $p [mm] \equiv [/mm] 1 [mm] \pmod{3}$, [/mm] so muss $h$ noch lange kein Element der Ordnung 3 sein.
Was aber aequivalent ist: "Es gibt ein $h$, so dass die Ordnung von $h$ modulo $p$ gerade 3 ist" und "$p [mm] \equiv [/mm] 1 [mm] \pmod [/mm] {3}$".
> Und wenn ich obigen Satz verwende, dann muss x doch dieser
> Form 2h+1 sein.
Nein. Der obige Satz ist nur dann anwendbar, wenn $x$ von der Form $2 h + 1$ ist. Nach dem, was reverend schreibt, kannst du aber immer annehmen, dass $x$ von dieser Form ist. (Siehe auch mein Beweis oben.)
LG Felix
|
|
|
| |
|
Also, kann ich für den geforderten Beweis, der mir noch fehlt, einfach sagen, wir untersuchen alle ungerade Zahlen x, für die nach dem Satz offenbar p den Rest 1 modulo 3 lässt. Die Gültigkeit für gerade x folgt dann daraus, dass x+p für ungerade x gerade wird und in die gleiche Restklasse fällt. Und es existiert auch zu jedem geraden x eine ungerade Zahl m, sodass m+p=x (mod p).
Ist das soweit richtig?!
Damit wäre der Beweis ja abgeschlossen.
Lg, David
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:13 Do 16.06.2011 | | Autor: | felixf |
Moin David!
> Also, kann ich für den geforderten Beweis, der mir noch
> fehlt, einfach sagen, wir untersuchen alle ungerade Zahlen
> x, für die nach dem Satz offenbar p den Rest 1 modulo 3
> lässt.
Was hat denn $p$ mit $x$ zu tun? Der Satz macht so grad wenig Sinn.
> Die Gültigkeit für gerade x folgt dann daraus,
> dass x+p für ungerade x gerade wird und in die gleiche
> Restklasse fällt.
Dann solltest du es andersherum schreiben:
> Die Gültigkeit für gerade x folgt dann daraus,
> dass x+p für gerades x ungerade wird und in die gleiche
> Restklasse fällt.
Und hier:
> Und es existiert auch zu jedem geraden x
> eine ungerade Zahl m, sodass m+p=x (mod p).
meinst du eher $m [mm] \equiv [/mm] x [mm] \pmod{p}$.
[/mm]
> Ist das soweit richtig?!
Bis auf die Formulierung schon.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:36 Do 16.06.2011 | | Autor: | abakus |
Hallo David,
es ist im allgemeinen Suchen nach Lösungswegen etwas untergegangen:
Aus welchem ehemaligen Wettbewerb welches Jahres stammt denn eigentlich die Aufgabe?
Gruß Abakus
|
|
|
| |
|
Die Aufgabe ist aus einem Korrespondenzbrief zur Förderung. ;D
Lg, David
|
|
|
|
