Lösung eines Kongruenzsystems

04.04.2009, 17:11

Sensi

Lösung eines Kongruenzsystems

Hi,

Also ich sitze an folgender Aufgabe:

Es seien m1,..,mr Elemente aus N paarweise teilerfremd und c1,...,cr
Elemente aus Z. Zeige:
Setzt man m := m1*...*mr und Mi := m/mi für 1 kleiner/gleich i kl./gl. r,
so ist x := summe aller ciMi ^eulerscheFunktion(mi) eine Lösung
des Kongruenzsystems x kongruent zu ci mod mi .

Also bitte entschuldigt zunächst erstmal, die schlechte Schreibweise...
Und also hier meine Lösungsidee, die vielleicht auch total absurd ist:

Also, es geht ja darum zu zeigen mi teilt x minus ci.
Erst einmal ist sind ja alle Mi Produkte und nur in einem dieser Mi ist ein betrachtetes mi nicht als Faktor enthalten. Sofern es als Faktor enthalten ist,
teilt das mi ein M ja sowieso.
Es bleibt also das Mi, welches direkt zum mi gehört und in dem es nicht als Faktor enthalten ist.
Hier dachte ich den Satz von Fermat-Euler heranzuziehen, demnach gilt für zwei teilerfremde a und m, m teilt a^Eulersche Funktion(m) minus 1,
also könnte man auf die Aufgabe bezogen das minus ci als -1*ci sehen und
so zeigen, dass x kongruent zu ci mod mi ist?
Es tut mir leid, wenn das total abwegig ist, ich hab wahrscheinlich echte Verständnisprobleme und auch am korrekten mathematischen Ausdruck haperts glaub ich sehr... Bin also ein echter Härtefall! Wäre nett, wenn ihr mir helft,
Vielen Dank im Vorraus, Sensi

04.04.2009, 17:49

Auf diesen Beitrag antworten »

Chinesischer Restsatz

Zitat:

Original von Sensi
Hier dachte ich den Satz von Fermat-Euler heranzuziehen, demnach gilt für zwei teilerfremde a und m, m teilt a^Eulersche Funktion(m) minus 1,
also könnte man auf die Aufgabe bezogen das minus ci als -1*ci sehen und
so zeigen, dass x kongruent zu ci mod mi ist?
si

Kein Grund für Entschuldigungen, es ist die richtige Idee. Freude

Ein bisschen LaTeX macht die Sache lesbarer:

Zitat:

$\begin{eqnarray*} x = \sum_{i=1}^r c_i \cdot M_i^{\varphi(m_i)} \end{eqnarray*}$ mit $\begin{eqnarray*} M_i = \prod\limits_{\substack{j=1\\ j\neq i}}^r m_j \end{eqnarray*}$

ist Lösung des Kongruenzsystems

$\begin{eqnarray*} x \equiv c_i \mod m_i \end{eqnarray*}$ für $\begin{eqnarray*} i=1,\ldots,r \end{eqnarray*}$ .

05.04.2009, 13:18

Sensi

Auf diesen Beitrag antworten »

RE: Chinesischer Restsatz
Vielen,vielen Dank!
Dann werd ich mal versuchen das so korrekt und mathematisch zu formulieren;
auch in das Schreiben mit Latex muss ich mich jetzt erstmal reinarbeiten...
Viele liebe Grüße,
Sensi

Neue Frage »

Antworten »

Lösung eines Kongruenzsystems

Verwandte Themen