Kongruenzensystem lösen

06.05.2012, 14:30	SKP	Auf diesen Beitrag antworten »
Kongruenzensystem lösen Meine Aufgabe: Man bestimme alle Lösungen des Kongruenzensystems $\begin{eqnarray} x\equiv 13 mod 30 \end{eqnarray}$ $\begin{eqnarray} x\equiv 28 mod 105 \end{eqnarray}$ $\begin{eqnarray} x\equiv 28 mod 385 \end{eqnarray}$ für $\begin{eqnarray} x\in \mathbb Z \end{eqnarray}$ . Mein Problem: Wo finde ich ein Algorithmus zum Lösen von Kongruenzsystemen mit nicht teilerfremden Moduli? Habe bis jetzt nur Algorithmen für teilerfremde Moduli gefunden
06.05.2012, 15:04	HAL 9000	Auf diesen Beitrag antworten »
Wenn du nach allgemeinen Hinweisen dazu suchst, siehe http://de.wikipedia.org/wiki/Chinesische...llgemeiner_Fall . Im vorliegenden Fall kann man die Sache aber erheblich abkürzen: Die erste Kongruenz $\begin{eqnarray} x\equiv 13\bmod 30 \end{eqnarray}$ kann man zerlegen in $\begin{eqnarray} x\equiv 13\equiv 1\bmod 2 \end{eqnarray}$ und $\begin{eqnarray} x\equiv 13\equiv 28\bmod 15 \end{eqnarray}$ Letzteres ist wegen $\begin{eqnarray} 105=7\cdot 15 \end{eqnarray}$ bereits durch die zweite Originalkongruenz abgedeckt. Unter Beachtung von $\begin{eqnarray} 385 = 5\cdot 7\cdot 11 \end{eqnarray}$ kann man dann die drei Originalkongruenzen äquivalent in das einfache System $\begin{eqnarray} x\equiv 1\bmod 2 \end{eqnarray}$ $\begin{eqnarray} x\equiv 28\bmod 1155 \end{eqnarray}$ überführen.
06.05.2012, 17:29	SKP	Auf diesen Beitrag antworten »
Danke! Habs geschafft!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »