Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Do 04.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
