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
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenMathematik-WettbewerbeQuadratische Reste
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
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


Alle Foren
Status vor 56m 7. Tobikall
ULinAAb/Permutationsgr./ Transposition
Status vor 2h 40m 62. Diophant
MSons/Kann man beim Roulette verlier
Status vor 4h 53m 2. matux MR Agent
DiffGlPar/Abschätzung
Status vor 6h 26m 4. Diophant
UStoc/Geordnete Stichproben mit Wdh.
Status vor 6h 53m 7. matux MR Agent
Algebra/Integritätsbereich Polynomring
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]