Kongruenz Anzahl Lösungen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:23 Do 21.03.2013 | | Autor: | Rubikon |
| Aufgabe | Seien p und q zwei verschiedene Primzahlen.
Bestimmen Sie die Anzahl der Lösungen der Kongruenz [mm] x^2 [/mm] ≡ 1 (mod p*q) in [mm] \IZ/pq\IZ [/mm] .
Hinweis: Nehmen Sie an, dass q ungerade ist und betrachten Sie die Fälle p gerade und p ungerade getrennt. |
Hallo,
bräuchte zu obiger Aufgabe einen Hinweis wie der Hinweis zu verstehen oder anzuwenden ist.
Wenn ich mir bei diesem Skript (http://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.100/vorlesungen/ss10/EZ/skriptez10_01.pdf) auf Seite 14 Satz 2.1.8 (b) ansehe, dann müsste es doch höchstens eine Lösung geben. Denn wegen (a) muss gelten ggT(x,p*q)=1 wenn die Aufgabe eine Lösung haben soll.
Ich bedanke mich für Antworten.
Gruß Rubikon
|
|
| |
|
Hallo,
den zitierten Satz kannst du hier nicht anwenden da keine lineare Kongruenz vorliegt.
Die Gleichung hat meherer Lösungen z.B. für p=3 und q=5
gibt es 4 Lösungen: 1,4,11,14.
Bei dieser Aufgabe hilft der chinesische Restsatz und der Umstand,
dass die Gleichung [mm] $x^2=1$ [/mm] in einem Körper angenehm lösbar ist.
(Beachte dabei den Hinweis zur Aufgabe.)
|
|
|
| |
|
Hallo Rubikon,
> Seien p und q zwei verschiedene Primzahlen.
> Bestimmen Sie die Anzahl der Lösungen der Kongruenz [mm]x^2[/mm]
> ≡ 1 (mod p*q) in [mm]\IZ/pq\IZ[/mm] .
>
> Hinweis: Nehmen Sie an, dass q ungerade ist und betrachten
> Sie die Fälle p gerade und p ungerade getrennt.
> Hallo,
>
> bräuchte zu obiger Aufgabe einen Hinweis wie der Hinweis
> zu verstehen oder anzuwenden ist.
>
> Wenn ich mir bei diesem Skript
> (http://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.100/vorlesungen/ss10/EZ/skriptez10_01.pdf)
> auf Seite 14 Satz 2.1.8 (b) ansehe, dann müsste es doch
> höchstens eine Lösung geben. Denn wegen (a) muss gelten
> ggT(x,p*q)=1 wenn die Aufgabe eine Lösung haben soll.
Na dann reicht vielleicht ein Beispiel, um Dich nochmal zum Nachdenken zu bringen:
[mm] 1^2\equiv 4^2\equiv 11^2\equiv 14^2\equiv 1\mod{(15)}
[/mm]
> Ich bedanke mich für Antworten.
Grüße
revernd
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:33 Fr 22.03.2013 | | Autor: | Rubikon |
Danke für eure Antworten. Laut dem Chinesischen Restsatz ist das System äquivalent zu:
[mm] \left\{\begin{array}{ll} x^2 \equiv 1 (mod p) \\ x^2 \equiv 1 (mod q)\end{array}\right. [/mm]
Was, da p und q Primzahlen sind, äquivalent ist zu:
[mm] \left\{\begin{array}{ll} x \equiv \pm 1 (mod p) (A) \\ x \equiv \pm 1 (mod q) (B)\end{array}\right. [/mm]
Wenn nun A gleich der Menge aller x ist für die (A) gilt und B die Menge ist für die (B) gilt, dann sollte die Anzahl der Lösungen der ursprünglichen Kongruenz gleich |A [mm] \cap [/mm] B| sein.
Leider weiß ich allerdings immer noch nicht wie ich den Hinweis hier einsetzen kann.
Gruß Rubikon
|
|
|
| |
|
> Danke für eure Antworten. Laut dem Chinesischen Restsatz
> ist das System äquivalent zu:
>
> [mm]\left\{\begin{array}{ll} x^2 \equiv 1 (mod p) \\ x^2 \equiv 1 (mod q)\end{array}\right.[/mm]
>
> Was, da p und q Primzahlen sind, äquivalent ist zu:
>
> [mm]\left\{\begin{array}{ll} x \equiv \pm 1 (mod p) (A) \\ x \equiv \pm 1 (mod q) (B)\end{array}\right.[/mm]
>
Ja, richtig.
> Wenn nun A gleich der Menge aller x ist für die (A) gilt
> und B die Menge ist für die (B) gilt, dann sollte die
> Anzahl der Lösungen der ursprünglichen Kongruenz gleich
> |A [mm]\cap[/mm] B| sein.
Was meinst du genau mit A und B? Woher kommen die x?
Aus den natürlichen Zahlen?
Wahrscheinlich läufst du hier in die falsche Richtung.
Das zweimal gegebene Bsp. gibt einen Hinweis auf die Anzahl der Lösungen (und die ist ziemlich typisch.)
> Leider weiß ich allerdings immer noch nicht wie ich den
> Hinweis hier einsetzen kann.
Schau dir doch mal ein Bsp. mit p=2 an. (die verhalten sich alle gleichartig.)
> Gruß Rubikon
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:27 Fr 22.03.2013 | | Autor: | Rubikon |
Hallo sometree,
Vielen Dank! habe nun zumindest einmal den Fall für p gerade abgearbeitet. So ein Beispiel kann schon Wunder wirken ^^.
Bei dem Fall der ungeraden Zahlen steig ich noch nicht ganz dahinter. Wäre nett wenn du mir die Anzahl verraten würdest damit ich ausgehend davon weitere Überlegungen anstellen kann. Ich schaffe es nur die Anzahl der Lösungen einzugrenzen, sie nicht aber konkret anzugeben.
Gruß Rubikon
|
|
|
| |
|
Hallo Rubikon,
> Bei dem Fall der ungeraden Zahlen steig ich noch nicht ganz
> dahinter. Wäre nett wenn du mir die Anzahl verraten
> würdest damit ich ausgehend davon weitere Überlegungen
> anstellen kann. Ich schaffe es nur die Anzahl der Lösungen
> einzugrenzen, sie nicht aber konkret anzugeben.
Vier. 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:16 Sa 23.03.2013 | | Autor: | Rubikon |
Oh, danke :).
Hatte mich bei einem Beispiel vertan bei dem ich nur 3 gefunden hatte.
Grüße.
|
|
|
|
