matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Schulmathe
  Status Primarstufe
  Status Mathe Klassen 5-7
  Status Mathe Klassen 8-10
  Status Oberstufenmathe
    Status Schul-Analysis
    Status Lin. Algebra/Vektor
    Status Stochastik
    Status Abivorbereitung
  Status Mathe-Wettbewerbe
    Status Bundeswettb. Mathe
    Status Deutsche MO
    Status Internationale MO
    Status MO andere Länder
    Status Känguru
  Status Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenMathematik-WettbewerbeQuadratische Reste
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Mathematik-Wettbewerbe" - Quadratische Reste
Quadratische Reste < Wettbewerbe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Mathematik-Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Quadratische Reste: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:21 Mi 15.06.2011
Autor: KingStone007

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

        
Bezug
Quadratische Reste: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Quadratische Reste: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:56 Mi 15.06.2011
Autor: KingStone007

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

Bezug
                        
Bezug
Quadratische Reste: Antwort
Status: (Antwort) fertig Status 
Datum: 15:34 Mi 15.06.2011
Autor: reverend

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


Bezug
                                
Bezug
Quadratische Reste: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:40 Mi 15.06.2011
Autor: KingStone007

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

Bezug
                                        
Bezug
Quadratische Reste: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                
Bezug
Quadratische Reste: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 18:16 Mi 15.06.2011
Autor: KingStone007

Hallo, ich habe den Beitrag geändert. Hat jmd. vielleicht eine Idee dazu.? :)

Lg, David

Bezug
                                        
Bezug
Quadratische Reste: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                                
Bezug
Quadratische Reste: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:16 Mi 15.06.2011
Autor: KingStone007

So, nun sollte es aber geändert worden sein.?!

Lg, David

Bezug
                                                        
Bezug
Quadratische Reste: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                                                
Bezug
Quadratische Reste: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:33 Mi 15.06.2011
Autor: KingStone007

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

Bezug
                                                                        
Bezug
Quadratische Reste: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                                                                                
Bezug
Quadratische Reste: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:52 Do 16.06.2011
Autor: KingStone007

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

Bezug
                                                                                        
Bezug
Quadratische Reste: Antwort
Status: (Antwort) fertig Status 
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


Bezug
        
Bezug
Quadratische Reste: Quelle der Aufgabe
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Quadratische Reste: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:16 Sa 18.06.2011
Autor: KingStone007

Die Aufgabe ist aus einem Korrespondenzbrief zur Förderung. ;D

Lg, David

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Mathematik-Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.schulmatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]