www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 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
Forum "Zahlentheorie" - Quadratische Kongruenz
Quadratische Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Quadratische Kongruenz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:44 Mi 14.12.2011
Autor: Loko

Aufgabe
Lösen der quadratischen Kongruenzen:
a) [mm] x^{2} [/mm] + x + 1 [mm] \equiv [/mm] 0 (mod 7)
b) [mm] x^{2} [/mm] + 5x + 1 [mm] \equiv [/mm] 0 (mod 7)
c) [mm] x^{2} [/mm] + 3x + 1 [mm] \equiv [/mm] 0 (mod 7)

Ich habe mich bisher nur an der a) versucht.

Also zunächst habe ich das alles mal etwas handlicher umgeformt:

[mm] x^{2} [/mm] + x + 1 [mm] \equiv 4x^{2} [/mm] + 4x + 4 [mm] \equiv [/mm] 0 (mod 7)
   [mm] \gdw (2x+1)^{2} \equiv [/mm] -3 [mm] \equiv [/mm] 4 (mod 7)

[mm] y^{2} [/mm] := [mm] (2x+1)^{2}. [/mm]

So kann ich dann über (4|7) prüfen ob es für y eine Lösung gibt.

(4|7) = (2|7)(2|7) = [mm] (-1)^{\bruch{7^{2}-1}{8}}*(-1)^{\bruch{7^{2}-1}{8}} [/mm]
      = 1
[mm] \Rightarrow [/mm] 4 ist quadratischer Rest von 7, und so besitzt y eine Lösung.

In der Vorlesung hatten wir dann so weiter gemacht:
prüfe p(mod 4) = ?:
  7 [mm] \equiv [/mm] 3 (mod 4)
[mm] \Rightarrow y^{2} \equiv \pm 4^{\bruch{7+1}{4}} [/mm] (mod 7) (Das hat uns eine Proposition verraten)
   [mm] \equiv [/mm] 2 (mod 7).

Jetzt weiss ich also, dass [mm] y^{2} \equiv \pm [/mm] 2 (mod 7) ist.

Wie mach ich denn jetzt weiter?
Wie kann ich darüber auf die Lösung für [mm] (2x+1)^{2} [/mm] kommen?
Und ist der Weg bis hierher so sinnvoll?

Vielen Dank und liebe Grüsse

Loko


        
Bezug
Quadratische Kongruenz: Antwort
Status: (Antwort) fertig Status 
Datum: 11:52 Mi 14.12.2011
Autor: donquijote


> Lösen der quadratischen Kongruenzen:
>  a) [mm]x^{2}[/mm] + x + 1 [mm]\equiv[/mm] 0 (mod 7)
>  b) [mm]x^{2}[/mm] + 5x + 1 [mm]\equiv[/mm] 0 (mod 7)
>  c) [mm]x^{2}[/mm] + 3x + 1 [mm]\equiv[/mm] 0 (mod 7)
>  Ich habe mich bisher nur an der a) versucht.
>  
> Also zunächst habe ich das alles mal etwas handlicher
> umgeformt:
>  
> [mm]x^{2}[/mm] + x + 1 [mm]\equiv 4x^{2}[/mm] + 4x + 4 [mm]\equiv[/mm] 0 (mod 7)
> [mm]\gdw (2x+1)^{2} \equiv[/mm] -3 [mm]\equiv[/mm] 4 (mod 7)
>  
> [mm]y^{2}[/mm] := [mm](2x+1)^{2}.[/mm]
>  
> So kann ich dann über (4|7) prüfen ob es für y eine
> Lösung gibt.
>  
> (4|7) = (2|7)(2|7) =
> [mm](-1)^{\bruch{7^{2}-1}{8}}*(-1)^{\bruch{7^{2}-1}{8}}[/mm]
>        = 1
>  [mm]\Rightarrow[/mm] 4 ist quadratischer Rest von 7, und so besitzt
> y eine Lösung.
>  
> In der Vorlesung hatten wir dann so weiter gemacht:
>  prüfe p(mod 4) = ?:
>    7 [mm]\equiv[/mm] 3 (mod 4)
> [mm]\Rightarrow y^{2} \equiv \pm 4^{\bruch{7+1}{4}}[/mm] (mod 7)
> (Das hat uns eine Proposition verraten)
>     [mm]\equiv[/mm] 2 (mod 7).
>  
> Jetzt weiss ich also, dass [mm]y^{2} \equiv \pm[/mm] 2 (mod 7) ist.
>  
> Wie mach ich denn jetzt weiter?
> Wie kann ich darüber auf die Lösung für [mm](2x+1)^{2}[/mm]

Jetzt fehlt doch nur noch die Rücksubstitution, d.h. du bestimmst die zwei Lösungen für x aus der Gleichung [mm] 2x+1=y=\pm [/mm] 2,
also [mm] 2x_1+1=2 [/mm] und [mm] 2x_2+1=-2 [/mm]

> kommen?
>  Und ist der Weg bis hierher so sinnvoll?

das scheint mir alles korrekt

>  
> Vielen Dank und liebe Grüsse
>  
> Loko
>  


Bezug
                
Bezug
Quadratische Kongruenz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:59 Mi 14.12.2011
Autor: Loko

Vielen Dank schonmal für die schnelle  Antwort!

Nur ist doch [mm] y^{2} \equiv \pm [/mm] 2? Wie kann ich da das "hoch 2" auflösen?
Tut mir leid.. ich seh noch nicht, wie die Rücksubstitution funktioniert....

Viele Grüsse! :)

(Ich hab die Nächste Stunde Vorlesung..)

Danke nochmal!

Bezug
                        
Bezug
Quadratische Kongruenz: Antwort
Status: (Antwort) fertig Status 
Datum: 12:30 Mi 14.12.2011
Autor: donquijote


> Vielen Dank schonmal für die schnelle  Antwort!
>  
> Nur ist doch [mm]y^{2} \equiv \pm[/mm] 2? Wie kann ich da das "hoch
> 2" auflösen?

Das hast du doch schon getan! Aus [mm] y^2=4 [/mm] hast du [mm] y=\pm [/mm] 2 bestimmt.

> Tut mir leid.. ich seh noch nicht, wie die
> Rücksubstitution funktioniert....

Das ist dann "nur noch" das Auflösen einer linearen Kongruenz.
Für die eine Lösung [mm] 2=2x+1\Leftrightarrow 4\m 2=4\m 2x+4\Leftrightarrow x+4=1\Leftrightarrow [/mm] x=4
durch Multiplikation mit dem Inversen [mm] 2^{-1}=4 [/mm]

>  
> Viele Grüsse! :)
>  
> (Ich hab die Nächste Stunde Vorlesung..)
>  
> Danke nochmal!


Bezug
                                
Bezug
Quadratische Kongruenz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:33 Do 15.12.2011
Autor: Loko

Vielen, vielen Dank! Heute hab ichs dann auch endlich verstanden :-D

Gut zur a) y [mm] \equiv \pm [/mm] 2 (mod 7)
   [mm] \Rightarrow [/mm] 2x + 1 [mm] \equiv \pm [/mm] 2 (mod 7)
   [mm] \gdw [/mm] x + 4 [mm] \equiv \pm [/mm] 1 (mod 7)
   [mm] \gdw [/mm] x + 4 [mm] \equiv [/mm] 1 (mod 7) [mm] \Rightarrow [/mm] x [mm] \equiv [/mm] 4 und x + 4 [mm] \equiv [/mm] -1 [mm] \equiv [/mm] 6 [mm] \Rightarrow [/mm] x [mm] \equiv [/mm] 2

b) [mm] x^{2} [/mm] + 5x + 1 [mm] \equiv [/mm] 0 (mod 7)
   [mm] \gdw 4x^{2} [/mm] + 20x + 4 [mm] \equiv [/mm] 0 (mod 7)
   [mm] \gdw 4x^{2} [/mm] - 8x + 4 [mm] \equiv [/mm] 0 (mod 7)
   [mm] \gdw [/mm] (2x - [mm] 2)^{2} \equiv [/mm] 0 (mod 7)
   [mm] \Rightarrow [/mm] 2x - 2 [mm] \equiv [/mm] 0 (mod 7)
   [mm] \gdw [/mm] x [mm] \equiv [/mm] 1 (mod 7).
   War's das hierbei schon? Oder gibt es auch hier mehr als eine Lösung?
   Ich erinnere mich nicht mehr, wie das war wenn die Legendre Zahl 0 war,
   und finde es auch nicht in der Vorlesung.
   Aber eigentlich sieht es so ja ganz hübsch aus ;)

c) [mm] x^{2} [/mm] + 3x + 1 [mm] \equiv [/mm] 0 (mod 7)
   [mm] \gdw 4x^{2} [/mm] + 12x + 4 [mm] \equiv [/mm] 0 (mod 7)
   [mm] \gdw [/mm] (2x + [mm] 3)^{2} [/mm] + 2 [mm] \equiv [/mm] 0 (mod 7) (wg 4 [mm] \equiv [/mm] 11)
   [mm] \gdw [/mm] (2x + [mm] 3)^{2} \equiv [/mm] -2 [mm] \equiv [/mm] 5 (mod 7)
   y := 2x + 3
   [mm] y^{2} \equiv [/mm] 5 (mod 7) hat Lösung, gdw (5|7) [mm] \ge [/mm] 0
   (5|7) = [mm] (-1)^{\bruch{5-1}{2} \bruch{7-1}{2}} [/mm] * (7|5)
         = (7|5) = (2|5) = [mm] (-1)^{\bruch{5^{2}-1}{8}} [/mm] = -1
   [mm] \Rightarrow [/mm] Es gibt keine Lösung


Stimmt das alles so?

Vielen Dank und Liebe Grüße!!

Loko


Bezug
                                        
Bezug
Quadratische Kongruenz: Antwort
Status: (Antwort) fertig Status 
Datum: 16:39 Do 15.12.2011
Autor: reverend

Hallo Loko,

das ist alles vollkommen richtig. [daumenhoch]

Grüße
reverend


Bezug
                                                
Bezug
Quadratische Kongruenz: Dankeschön
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:08 Do 15.12.2011
Autor: Loko

Vielen Dank ihr zwei!! :)

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]