www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · 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

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
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieQuadratische Kongruenz
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Zahlentheorie" - Quadratische Kongruenz
Quadratische Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Quadratische Kongruenz: Idee
Status: (Frage) beantwortet Status 
Datum: 12:30 Fr 08.11.2013
Autor: DrRiese

Aufgabe
Sei n>2 eine ungerade natürliche Zahl und p eine ungerade Primzahl.

a) Bestimmen Sie die Anzahl der Lösungen x der Kongruenz
              [mm] x^{2} \equiv [/mm] 1 mod [mm] p^{S} [/mm]
   für s [mm] \in \IN [/mm]

b) Bestimmen Sie die Anzahl der Lösungen von
              [mm] x^{2} \equiv [/mm] 1 mod n
  
c) Bestimmen Sie alle n, für welche die Kongruenz [mm] x^{2} \equiv [/mm] 1 mod n genau zwei Lösungen hat

Hallo liebe Forenmitglieder :-)

Habe zu dieser Aufgabe einen Ansatz, bin mir aber unsicher, ob dies nicht falsch gedacht ist...

a)

  [mm] x^{2} \equiv [/mm] 1 mod [mm] p^{S} [/mm]
[mm] \gdw x^{2}-1 \equiv [/mm] 0 mod [mm] p^{S} [/mm]
[mm] \gdw [/mm] (x+1)(x-1) [mm] \equiv [/mm] 0 mod [mm] p^{S} [/mm]
[mm] \gdw [/mm] x+1 [mm] \equiv [/mm] 0 mod [mm] p^{S} [/mm] oder x-1 [mm] \equiv [/mm] 0 mod [mm] p^{S} [/mm]
Also zwei Lösungen, nämlich x = [mm] \pm [/mm] 1

b)
[mm] x^{2} \equiv [/mm] 1 mod n
[mm] \gdw x^{2}-1 \equiv [/mm] 0 mod n
[mm] \gdw [/mm] (x-1)(x+1) [mm] \equiv [/mm] 0 mod n
[mm] \gdw [/mm] x-1 [mm] \equiv [/mm] 0 mod n oder x+1 [mm] \equiv [/mm] 0 mod n
Also zwei Lösungen, nämlich x = [mm] \pm [/mm] 1

Das wird wohl nicht ganz richtig sein, da ich keine der Voraussetzungen hier anwenden konnte....

Würde mich über Tipps freuen :-)

LG,
DrRiese

        
Bezug
Quadratische Kongruenz: Antwort
Status: (Antwort) fertig Status 
Datum: 13:43 Fr 08.11.2013
Autor: reverend

Hallo DrRiese,

die Grundidee ist gut, aber sie geht noch nicht ganz auf.

> Sei n>2 eine ungerade natürliche Zahl und p eine ungerade
> Primzahl.
>  
> a) Bestimmen Sie die Anzahl der Lösungen x der Kongruenz
>                [mm]x^{2} \equiv[/mm] 1 mod [mm]p^{S}[/mm]
>     für s [mm]\in \IN[/mm]
>  
> b) Bestimmen Sie die Anzahl der Lösungen von
>                [mm]x^{2} \equiv[/mm] 1 mod n
>    
> c) Bestimmen Sie alle n, für welche die Kongruenz [mm]x^{2} \equiv[/mm]
> 1 mod n genau zwei Lösungen hat
>  Hallo liebe Forenmitglieder :-)
>  
> Habe zu dieser Aufgabe einen Ansatz, bin mir aber unsicher,
> ob dies nicht falsch gedacht ist...
>  
> a)
>
> [mm]x^{2} \equiv[/mm] 1 mod [mm]p^{S}[/mm]
>  [mm]\gdw x^{2}-1 \equiv[/mm] 0 mod [mm]p^{S}[/mm]
>  [mm]\gdw[/mm] (x+1)(x-1) [mm]\equiv[/mm] 0 mod [mm]p^{S}[/mm]
>  [mm]\gdw[/mm] x+1 [mm]\equiv[/mm] 0 mod [mm]p^{S}[/mm] oder x-1 [mm]\equiv[/mm] 0 mod [mm]p^{S}[/mm]
>  Also zwei Lösungen, nämlich x = [mm]\pm[/mm] 1

Das ist zwar richtig, aber es nicht erkenntlich, wieso das nicht ganz allgemein (also wie auch in b) gelten sollte. Was ist die Besonderheit einer Primzahlpotenz?

> b)
>  [mm]x^{2} \equiv[/mm] 1 mod n
>  [mm]\gdw x^{2}-1 \equiv[/mm] 0 mod n
>  [mm]\gdw[/mm] (x-1)(x+1) [mm]\equiv[/mm] 0 mod n
>  [mm]\gdw[/mm] x-1 [mm]\equiv[/mm] 0 mod n oder x+1 [mm]\equiv[/mm] 0 mod n
>  Also zwei Lösungen, nämlich x = [mm]\pm[/mm] 1
>  
> Das wird wohl nicht ganz richtig sein, da ich keine der
> Voraussetzungen hier anwenden konnte....

Gegenbeispiele: [mm] 4^2\equiv 1\mod{15}, 34^2\equiv 1\mod{231} [/mm]

> Würde mich über Tipps freuen :-)

Da reicht einer für beide Teilaufgaben: chinesischer Restsatz.

Grüße
reverend

Bezug
                
Bezug
Quadratische Kongruenz: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 17:34 So 10.11.2013
Autor: DrRiese

Hi, danke für deine Antwort :-)

zu a)

Hm, so richtig weiss ich nicht, wie das mit dem chinesischen Restsatz gemacht werden soll..

Also wir haben die beiden Kongruenzgleichungen x+1 [mm] \equiv [/mm] 0 mod [mm] p^{S} [/mm] oder x-1 [mm] \equiv [/mm] 0 mod [mm] p^{S} [/mm]
Also könnte man das jetzt folgendermaßen schreiben:

[mm] \begin{cases}x \equiv -1 \mbox{mod } p^{S}\\ x \equiv 1 \mbox{mod } p^{S} \end{cases} [/mm]

So, dann [mm] p^{S}*p^{S}=p^{2S} [/mm] und nun Paare bilden [mm] (1,\bruch{p^{2S}}{p^{S}}),(-1, \bruch{p^{2S}}{p^{S}}) [/mm] = [mm] (1,p^{S}), (-1,p^{S}). [/mm]
[mm] ggT(1,p^{S})=1=(p^{2}+1)*1+(-1)*p^{S} [/mm]
[mm] ggT(-1,p^{S})=1=-(p^{2}+1)*(-1)+(-1)*p^{S} [/mm]

Lösung: [mm] 1*(-p^{S})+(-1)*(-p^{S})=0 [/mm]

Hm... ^^

LG,
DrRiese

Bezug
                        
Bezug
Quadratische Kongruenz: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:14 Di 12.11.2013
Autor: switchback

der chinese restsatz würde doch nur gehen wenn [mm] p^s [/mm] und [mm] p^s [/mm] teilferfremd wären, was wohl nicht der fall ist :p
Bezug
                        
Bezug
Quadratische Kongruenz: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:20 Di 12.11.2013
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]