Quadratische Reste < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:36 Sa 06.07.2013 | | Autor: | Blubie |
| Aufgabe | n [mm] \in \IN, [/mm] n > 1, a [mm] \in \IZ_{n}^{*}. [/mm] Wieviele Lösungen besitzt die Kongruenz [mm] x^2 \equiv [/mm] a (mod n), wenn
(a) n besteht aus paarweise verschiedenen Primfaktoren
(b) ...
(c) ... |
Da mir bei meinem letzten Thread so toll geholfen wurde, habe ich hier eine weitere Frage. Ich habe gelesen, dass man das durch eine Kombination des quadratischen Reziprozitätsgesetztes und des Chinesischen Restsatzes lösen kann. Mir ist aber zunächst mal nicht ganz klar, wie hier der Chinesische Restsatz zum Einsatz kommt, da der ja nur für eine Menge von linearen Kongruenzen ist. Wo ist hier der Zusammenhang?
|
|
| |
|
Hallo Blubie,
der Tipp ist richtig.
> n [mm]\in \IN,[/mm] n > 1, a [mm]\in \IZ_{n}^{*}.[/mm] Wieviele Lösungen
> besitzt die Kongruenz [mm]x^2 \equiv[/mm] a (mod n), wenn
> (a) n besteht aus paarweise verschiedenen Primfaktoren
> (b) ...
> (c) ...
> Da mir bei meinem letzten Thread so toll geholfen wurde,
> habe ich hier eine weitere Frage. Ich habe gelesen, dass
> man das durch eine Kombination des quadratischen
> Reziprozitätsgesetztes und des Chinesischen Restsatzes
> lösen kann. Mir ist aber zunächst mal nicht ganz klar,
> wie hier der Chinesische Restsatz zum Einsatz kommt, da der
> ja nur für eine Menge von linearen Kongruenzen ist. Wo ist
> hier der Zusammenhang?
1) Damit a ein quadratischer Rest (QR) [mm] \mod{n} [/mm] ist, muss a auch QR jedes Primfaktors von n sein.
2) Einfaches Beispiel: sei n=15. a=1 ist ja immer QR, so auch hier. Es gibt nun zwei Lösungen [mm] \mod{3} [/mm] und zwei Lösungen [mm] \mod{5}, [/mm] nämlich jeweils [mm] \pm1.
[/mm]
Welche Lösungen es also [mm] \mod{15} [/mm] gibt, kannst Du dann mit dem chin.Restsatz bestimmen: 1,4,11,14.
3) Bedenke auch den Fall ggT(a,n)>1.
Grüße
reverend
|
|
|
|
