Chinesischer Restsatz < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich habe eine Frage zum Verständnis und der Anwendung des chinesischen Restsatzes. Aufgabe ist es , die Quadratwurzeln x zu
[mm] x^2=a [/mm] mod n
zu finden.
Hinweis ist, den Chinesische Restsatz zu verwenden. Gegeben sind a =11 und n =35.
Nun lässt sich ja 35 = 5 [mm] \* [/mm] 7 zerlegen. Aber wie komme ich nun zu den Quadratwurzeln ??
Viele Grüsse
Sabrina
|
|
| |
|
Hallo Sabrina,
> Ich habe eine Frage zum Verständnis und der Anwendung des
> chinesischen Restsatzes. Aufgabe ist es , die
> Quadratwurzeln x zu
> [mm]x^2=a[/mm] mod n
> zu finden.
> Hinweis ist, den Chinesische Restsatz zu verwenden.
> Gegeben sind a =11 und n =35.
> Nun lässt sich ja 35 = 5 [mm]\*[/mm] 7 zerlegen. Aber wie komme ich
> nun zu den Quadratwurzeln ??
Es gilt:
[mm]\IZ_{35} \;:\;x^{2} \; \equiv \;11[/mm]
Da 35 = 5 * 7 und ggt(5,7) = 1 ist, läßt sich der Chinesische Restsatz anwenden:
[mm]\begin{gathered}
\IZ_{5} \;:\;x^{2} \; \equiv \;11\; \equiv \;1 \hfill \\
\IZ_{7} \;:\;x^{2} \; \equiv \;11\; \equiv \;4 \hfill \\
\end{gathered} [/mm]
Hieraus erhältst Du dann für jede der Kongruenzen Bedingungen, die die Zahl x erfüllen muß..
Die Zahlen sind dann durch Vergleiche der Lösungen zu bestimmen.
Alternativ kannst Du eine Lösung von einer Kongruenz bestimmen, und diese dann in die andere Kongruenz einsetzen und wiederum deren Lösung bestimmen.
Gruß
MathePower
|
|
|
| |
|
Hallo MathePower.
Damit erhalte ich fuer [mm] Z_{5} [/mm] und [mm] Z_{7} [/mm] jeweils die Lösungen [mm] \pm [/mm] 1 und [mm] \pm [/mm] 2.
Aber wie klebe ich daraus die Lösungen für [mm] Z_{35} [/mm] zusammen ?
Viele Grüsse
Sabrina
|
|
|
| |
|
Hallo Julius.
Leider finde ich die anderen nicht.
Mein bisheriges Verständnis ist folgendes : wegen 35 =7 * 5 kann ich die Loesung von [mm] x^2=11 [/mm] mod 35 auf die beiden Gleichungen [mm] x^2=11 [/mm] mod 5 und [mm] x^2=11mod [/mm] 7 zurückführen. Loesung für die erste der beiden ist 1 und damit auch 5-1 =4, für die zweite ist 2 und somit auch 7-2 =5. Ich habe also 4 Paare von Lösungen (1,2), (1,5), (4,2), (4,5). Soweit komme ich. Wie klebe ich die jetzt zusammen ? Das Theorem sagt:
[mm] x^2 [/mm] = [mm] \summe_{i=1}^2 a_{i} c_{i} [/mm] Mod M; wobei M=m1 * m2 = 35.
Woher bekomme ich nun diese [mm] a_{i} [/mm] ? Das scheinen dann die Einzellösungen von oben zu sein . Aber die [mm] c_{i} [/mm] ? Wie kommst Du da auf 3 ?
Sorry, aber ich scheine wirklich Tomaten auf den Augen zu haben.
Viele Grüsse
Sabrina
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:29 Mi 27.04.2005 | | Autor: | Julius |
Hallo!
Hast du dir den Link überhaupt durchgelesen? Dort steht ja ganz genau, wie man auf die $3$ kommt (besser könnte ich es jetzt auch nicht erklären).
Okay, dann mach folgendes: Die Formel bleibt eigentlich immer gleich bei allen vier Lösungen, du musst nur einfach die $1$ und die $2$, die in meiner Formel vorkommen, durch
$1$ und $5$,
$4$ und $2$
und
$4$ und $5$
ersetzen und den Rest so lassen. Dann kommst du auf die $4$ Lösungen.
Die Koeffizienten sind halt immer [mm] $\frac{35}{7} \cdot [/mm] x = 5 [mm] \cdot [/mm] x$, wobei $x$ das Inverse von $5$ modulo $7$ (also gleich $3$) ist bzw. [mm] $\frac{35}{5} \cdot [/mm] 7 [mm] \cdot [/mm] y$, wobei $y$ das Inverse von $7$ modulo $5$ (also ebenfalls gleich $3$) ist.
Viele Grüße
Julius
|
|
|
|
![[]](/images/popup.gif){kind=small}
hier![[ok]](/images/smileys/ok.gif "[ok]"){kind=small}
