www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - Kongruenzen
Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kongruenzen: Tipp
Status: (Frage) beantwortet Status 
Datum: 15:13 So 31.05.2009
Autor: Lati

Aufgabe
(a) Seien [mm] p_{1}, [/mm] . . . , [mm] p_{k} [/mm] verschiedene Primzahlen ungleich 2.
Ist a teilerfremd zu [mm] p_{1} [/mm] * . . .* [mm] p_{k}, [/mm] so hat die Kongruenz [mm] x^2 \equiv [/mm] a (mod [mm] p_{1} [/mm] * . . . * [mm] p_{k}) [/mm] entweder keine oder [mm] 2^{k} [/mm] verschiedene
Lösungen.

(b) Seien a ungerade und [mm] \alpha \ge [/mm] 3. Zeigen Sie, dass [mm] x^2 \equiv [/mm] a (mod [mm] 2 ^{\alpha}) [/mm] genau dann eine Lösung hat,
wenn a [mm] \equiv [/mm] 1 (mod 8) gilt.

Hallo zusammen,

hab mehrere Fragen zu obigen Aufgaben:

zu a):
Hier hab ich recht wenig Ahnung was ich überhaupt machen muss um das zu zeigen.
Also man weiß ja zumindest dass [mm] ggT(a,p_{1}*...*p_{k})=1 [/mm] gilt.
Aber was soll ich denn jetzt damit machen?Den Fermat anwenden?Aber was bringt mir das?
Ich hab keine Ahnung...

zu b):
Hier hab ich erstmal eine Frage und zwar muss hier nicht auch noch gelten dass x ungerade ist?
Weil ich hab mal ein Beispiel durchgerechnet mit a=9 x=4 und [mm] \alpha [/mm] = 4:

[mm] 4^2=16\equiv [/mm] 0(mod 16) aber das ist ja nicht kongruent 9 (mod 16)
Oder mach ich in meiner Rechnung was falsch?

Auch hier fehlt mir aber nichtsdestotrotz der Ansatz.

Vielen Dank für eure Hilfe!

Grüße

Lati


        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 02:30 Mo 01.06.2009
Autor: felixf

Hallo!

> (a) Seien [mm]p_{1},[/mm] . . . , [mm]p_{k}[/mm] verschiedene Primzahlen
> ungleich 2.
> Ist a teilerfremd zu [mm]p_{1}[/mm] * . . .* [mm]p_{k},[/mm] so hat die
> Kongruenz [mm]x^2 \equiv[/mm] a (mod [mm]p_{1}[/mm] * . . . * [mm]p_{k})[/mm] entweder
> keine oder [mm]2^{k}[/mm] verschiedene
>  Lösungen.
>  
> (b) Seien a ungerade und [mm]\alpha \ge[/mm] 3. Zeigen Sie, dass [mm]x^2 \equiv[/mm]
> a (mod [mm]2 ^{\alpha})[/mm] genau dann eine Lösung hat,
>  wenn a [mm]\equiv[/mm] 1 (mod 8) gilt.
>  
> Hallo zusammen,
>  
> hab mehrere Fragen zu obigen Aufgaben:
>  
> zu a):
>  Hier hab ich recht wenig Ahnung was ich überhaupt machen
> muss um das zu zeigen.
>  Also man weiß ja zumindest dass [mm]ggT(a,p_{1}*...*p_{k})=1[/mm]
> gilt.
>  Aber was soll ich denn jetzt damit machen?Den Fermat
> anwenden?Aber was bringt mir das?
>  Ich hab keine Ahnung...

Benutze den chinesischen Restsatz. Und schau dir das Problem mit $k = 1$ an, also modulo einer Primzahl. Wieviele Loesungen gibt es dort?

> zu b):
>  Hier hab ich erstmal eine Frage und zwar muss hier nicht
> auch noch gelten dass x ungerade ist?

Wieso? Wenn $a$ ungerade ist und $x$ eine Loesung ist, muss $x$ automatisch eh ungerade sein.

>  Weil ich hab mal ein Beispiel durchgerechnet mit a=9 x=4
> und [mm]\alpha[/mm] = 4:
>  
> [mm]4^2=16\equiv[/mm] 0(mod 16) aber das ist ja nicht kongruent 9
> (mod 16)

Du nimmst einfach irgendwelche Werte, rechnest aus, siehst das es nicht klappt (warum sollte es bei irgendwelchen Werten auch klappen?) und bezeichnest das als Beispiel?!

In den reellen Zahlen kannst du auch $a = 9$ und $x = 4$ nehmen und du wirst feststellen, dass ebenfalls nicht [mm] $4^2 [/mm] = 9$ ist. Warum sollte es das auch sein?

>  Oder mach ich in meiner Rechnung was falsch?

Nein.

> Auch hier fehlt mir aber nichtsdestotrotz der Ansatz.

Fuer [mm] $\alpha [/mm] = 3$ kannst du es schnell von Hand nachpruefen. Danach kannst du Induktion nach [mm] $\alpha$ [/mm] machen (den Anker hast du grad erledigt).

Zeige dazu:
a) Wenn es fuer [mm] $\alpha [/mm] + 1$ eine Loesung gibt, dann auch fuer [mm] $\alpha$. [/mm] (Das ist sehr einfach.)
b) Wenn es fuer [mm] $\alpha$ [/mm] eine Loesung gibt, dann auch fuer [mm] $\alpha [/mm] + 1$.

Daraus folgt dann die Behauptung.

Zu b): nimm eine Loesung $x$ fuer [mm] $\alpha$ [/mm] und schau dir $x$ und [mm] $2^{\alpha-1} [/mm] + x$ an: quadriere das jeweils und schau es dir modulo [mm] $2^{\alpha + 1}$ [/mm] an, und vergleiche es mit $a$ (modulo [mm] $2^{\alpha + 1}$). [/mm] Ueberlege dir, das eins davon $a$ sein muss.

LG Felix


Bezug
                
Bezug
Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:54 Mo 01.06.2009
Autor: Lati

Hi Felix,

vielen Dank für deine Antwort!

Ich hab deine Tipps aufgenommen und was versucht,ist aber zum Teil noch sehr fraglich und ich weiß manchmal auch gar nicht genau was du gemeint hast:

zu a): Fall k=1: [mm] x^2\equiv [/mm] a(mod [mm] p_{1}) [/mm]   ,   [mm] p_{1} [/mm] Primzahl.
Ich hab ein Bsp angeschaut. Wähle p=7 und a=9.Sind teilerfremd und für x würden sich die Lösungen 3 und 4 ergeben.also [mm] 2^1 [/mm] Lösungen. Aber ich mein ich kann ja hier nicht über Beispiele argumentieren.Mir fällt aber auch kein passender Satz ein.
So jetzt zu deinem nä. Tipp und zwar dem Restsatz.
Du meinst doch,dass ich [mm] Z_{p_{1}*,...,*p_{k}} [/mm] ( Z soll die Restklasse darstellen) auch schreiben kann als:
[mm] Z_{p_{1}} \times [/mm] ,..., [mm] \times Z_{p_{k}} [/mm] oder?
Also hätte ich dann quasi k-mal den Fall von oben. Jetzt muss ich nur noch herausfinden für welche a die erste Gleichung jetzt genau 2 Lösungen und für welche a keine Lösung hat.Dann wäre die Aufgabe gelöst oder?


zu b):
Du sagtest ich soll [mm] \alpha [/mm] =3 per Hand nachprüfen:
Also sozusagen Induktionsanfang: [mm] x^2 \equiv [/mm] a (mod [mm] 2^3) [/mm]  und es gilt [mm] a\equiv [/mm] 1( mod [mm] 2^3) [/mm]
es folgt also:  [mm] x^2 \equiv [/mm] 1 (mod 8) und hier ergeben sich z.B. die Lösungen 3,5,7.

Jetzt soll ich dazu zeigen:
a) Wenn es Lsg für [mm] \alpha [/mm] +1 gibt [mm] \Rightarrow [/mm] Lsg für [mm] \alpha [/mm]
Es gilt also: [mm] x^2 \equiv [/mm] a (mod [mm] 2^{\alpha +1}) \Rightarrow x^2 \equiv [/mm] a (mod [mm] 2^{\alpha}*2) [/mm] Kann ich hier jetzt den chin. Restsatz anwenden und deswegen dann sagen dass diese Richtung erfüllt ist?

b) Lsg für [mm] \alpha \Rightarrow [/mm] Lsg für [mm] \alpha [/mm] +1

Dazu soll ich mir eine Lsg x nehmen und [mm] 2^{\alpha -1} [/mm] +x und diese beiden Teile quadrieren:
Hab ich gemacht und erhalte:

[mm] x^2 [/mm] und  [mm] {(2^{\alpha -1} +x)}^2 [/mm] = [mm] 2^{2(\alpha -1)} [/mm] + [mm] 2*2^{\alpha -1}*x +x^2 [/mm]

So jetzt die beiden Ausdrücke mod [mm] 2^{\alpha +1} [/mm]

1.   [mm] x^2 [/mm] (mod [mm] 2^{\alpha +1}) [/mm]

2.   [mm] 2^{2(\alpha -1)} [/mm] + [mm] 2*2^{\alpha -1}*x +x^2 [/mm]  (mod  [mm] 2^{\alpha +1}) [/mm]

Ich würde jetzt mal spekulieren dass der 2. Teil a sein muss aber ich hab ehrlich gesagt keine Ahnung.sorry!

Und könntest du mir vielleicht auch nochmal erklären warum ich bei b) überhaupt so vorgehen kann und warum es reicht das hier zu zeigen und was ich hiermit überhaupt zeige? Sorry für die vielen Fragen...

Und eigentlich handelt es sich bei der Beh. doch um eine Äquivalenz oder?
Müsste ich dann nicht beide Richtungen zeigen oder mach ich das hiermit schon?

Vielen,vielen Dank für deine Hilfe!

Grüße

Lati


Bezug
                        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 21:50 Mo 01.06.2009
Autor: abakus


> Hi Felix,
>  
> vielen Dank für deine Antwort!
>  
> Ich hab deine Tipps aufgenommen und was versucht,ist aber
> zum Teil noch sehr fraglich und ich weiß manchmal auch gar
> nicht genau was du gemeint hast:
>  
> zu a): Fall k=1: [mm]x^2\equiv[/mm] a(mod [mm]p_{1})[/mm]   ,   [mm]p_{1}[/mm]
> Primzahl.
>  Ich hab ein Bsp angeschaut. Wähle p=7 und a=9.Sind
> teilerfremd und für x würden sich die Lösungen 3 und 4
> ergeben.also [mm]2^1[/mm] Lösungen. Aber ich mein ich kann ja hier
> nicht über Beispiele argumentieren.Mir fällt aber auch kein
> passender Satz ein.

Hallo, wenn [mm] x^2\equiv [/mm] a mod m gilt, dann gilt auch [mm] (-x)^2\equiv [/mm] a mod m .
(Warum?)
Damit dürfte man das paarweise Auftreten von Lösungen auch ohne Beispiele erklären können.
Gruß Abakus

>  So jetzt zu deinem nä. Tipp und zwar dem Restsatz.
>  Du meinst doch,dass ich [mm]Z_{p_{1}*,...,*p_{k}}[/mm] ( Z soll die
> Restklasse darstellen) auch schreiben kann als:
>  [mm]Z_{p_{1}} \times[/mm] ,..., [mm]\times Z_{p_{k}}[/mm] oder?
>  Also hätte ich dann quasi k-mal den Fall von oben. Jetzt
> muss ich nur noch herausfinden für welche a die erste
> Gleichung jetzt genau 2 Lösungen und für welche a keine
> Lösung hat.Dann wäre die Aufgabe gelöst oder?
>  
>
> zu b):
>  Du sagtest ich soll [mm]\alpha[/mm] =3 per Hand nachprüfen:
>  Also sozusagen Induktionsanfang: [mm]x^2 \equiv[/mm] a (mod [mm]2^3)[/mm]  
> und es gilt [mm]a\equiv[/mm] 1( mod [mm]2^3)[/mm]
>  es folgt also:  [mm]x^2 \equiv[/mm] 1 (mod 8) und hier ergeben sich
> z.B. die Lösungen 3,5,7.
>  
> Jetzt soll ich dazu zeigen:
>  a) Wenn es Lsg für [mm]\alpha[/mm] +1 gibt [mm]\Rightarrow[/mm] Lsg für
> [mm]\alpha[/mm]
>  Es gilt also: [mm]x^2 \equiv[/mm] a (mod [mm]2^{\alpha +1}) \Rightarrow x^2 \equiv[/mm]
> a (mod [mm]2^{\alpha}*2)[/mm] Kann ich hier jetzt den chin. Restsatz
> anwenden und deswegen dann sagen dass diese Richtung
> erfüllt ist?
>  
> b) Lsg für [mm]\alpha \Rightarrow[/mm] Lsg für [mm]\alpha[/mm] +1
>  
> Dazu soll ich mir eine Lsg x nehmen und [mm]2^{\alpha -1}[/mm] +x
> und diese beiden Teile quadrieren:
>  Hab ich gemacht und erhalte:
>  
> [mm]x^2[/mm] und  [mm]{(2^{\alpha -1} +x)}^2[/mm] = [mm]2^{2(\alpha -1)}[/mm] +
> [mm]2*2^{\alpha -1}*x +x^2[/mm]
>  
> So jetzt die beiden Ausdrücke mod [mm]2^{\alpha +1}[/mm]
>
> 1.   [mm]x^2[/mm] (mod [mm]2^{\alpha +1})[/mm]
>  
> 2.   [mm]2^{2(\alpha -1)}[/mm] + [mm]2*2^{\alpha -1}*x +x^2[/mm]  (mod  
> [mm]2^{\alpha +1})[/mm]
>  
> Ich würde jetzt mal spekulieren dass der 2. Teil a sein
> muss aber ich hab ehrlich gesagt keine Ahnung.sorry!
>  
> Und könntest du mir vielleicht auch nochmal erklären warum
> ich bei b) überhaupt so vorgehen kann und warum es reicht
> das hier zu zeigen und was ich hiermit überhaupt zeige?
> Sorry für die vielen Fragen...
>  
> Und eigentlich handelt es sich bei der Beh. doch um eine
> Äquivalenz oder?
>  Müsste ich dann nicht beide Richtungen zeigen oder mach
> ich das hiermit schon?
>  
> Vielen,vielen Dank für deine Hilfe!
>  
> Grüße
>  
> Lati
>  


Bezug
                                
Bezug
Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:15 Mo 01.06.2009
Autor: Lati

Hi Abakus,

aha,aber das beantwortet doch meine Frage nicht,ob es Lösungen geben muss und für welche a es Lösungen gibt. Das erklärt nur warum es 2 Lösungen gibt wenn es eine gibt...oder?

Gruß

Lati

Bezug
                                        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 04:24 Di 02.06.2009
Autor: felixf

Hallo Lati

> aha,aber das beantwortet doch meine Frage nicht,ob es
> Lösungen geben muss und für welche a es Lösungen gibt. Das
> erklärt nur warum es 2 Lösungen gibt wenn es eine
> gibt...oder?

Du sollst doch zeigen: entweder gibt es keine oder zwei Loesungen. Das ist damit erledigt.

Wenn du jetzt nicht $m = [mm] p_1$ [/mm] hast, sondern $m = [mm] p_1 \cdots p_k$, [/mm] so wende den chinesischen Restsatz an.

LG Felix


Bezug
                                                
Bezug
Kongruenzen: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 11:10 Di 02.06.2009
Autor: Lati

Hi Felix,

hast du meine zweite Frage gelesen?
Da hab ich doch den Restsatz angewendet weiß aber nicht genau ob das alles so stimmt.
Außerdem hatte ich dort noch viele andere Fragen gestellt...

Gruß

Lati

Bezug
                                                        
Bezug
Kongruenzen: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:20 Do 04.06.2009
Autor: matux

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


^ Seitenanfang ^
www.vorhilfe.de