Chinese Remainder Theorem

07.06.2018, 16:08	eroy	Auf diesen Beitrag antworten »
Chinese Remainder Theorem Hallo zusammen, ich bräuchte eure Hilfe bei der Lösung des folgenden Gleichungssystems: $\begin{eqnarray} <br /> x \equiv_{6} 0<br /> x \equiv_{8} 2<br /> x \equiv_{9} 6<br /> \end{eqnarray}$ Nun geht CRT so nicht, weil 6, 8, 9 nicht teilerfremd sind. Also gehe ich so vor, dass ich diese Zahlen in Primfaktoren zerlege: 6 = 2 * 3; 8 = 2 * 2 * 2; 9 = 3 * 3. Daraus baue ich ein neues GS: $\begin{eqnarray} <br /> x \equiv_{2} 0<br /> x \equiv_{3} 0<br /> \end{eqnarray}$ Und so wie es aussieht, ist das Unsinn. Warum funktioniert hier das nicht bzw. was mache ich falsch? Danke euch für jede Hilfe/Tipp!!
07.06.2018, 16:23	HAL 9000	Auf diesen Beitrag antworten »
Wenn man ein teilerfremdes CRT bauen will, dann nicht nur basierend auf den auftretenden Primfaktoren, sondern auf den höchsten auftauchenden Primfaktorpotenzen! Im vorliegenden Fall sind das die letzen beiden, also $\begin{eqnarray} x\equiv_8 2 \end{eqnarray}$ $\begin{eqnarray} x\equiv_9 6 \end{eqnarray}$ Jetzt muss noch überprüft werden, ob die sich aus der ersten Gleichung ergebenden Bedingungen $\begin{eqnarray} x\equiv_2 0 \end{eqnarray}$ sowie $\begin{eqnarray} x\equiv_3 0 \end{eqnarray}$ damit nicht im Widerspruch stehen (ansonsten gäbe es keine Lösung des Gesamsystems). Tun sie aber nicht, also alles Ok.
07.06.2018, 16:46	eroy	Auf diesen Beitrag antworten »
danke dir HAL 9000 für die sehr schnelle und wie immer verständliche Hilfe! Jetzt ist die Vorgehensweise klar. In dieser Aufgabe muss ich auch zeigen, dass es keine weiteren Lösungen als das gefundene x gibt. Muss ich den allgemeinen Beweis der Eindeutigkeit (Beweis des Theorems) verwenden, oder gibt es vielleicht andere Methoden, speziell für dieses Beispiel? Ich weiß, dass die Lösung im Intervall $\begin{eqnarray} 0 \leq x < 72 \end{eqnarray}$ liegt und ich habe einen Beweis der Eindeutigkeit der Lösung aus dem Beweis des Theorems, aber wie würde ich in dieser speziellen Aufgabe beweisen? Danke nochmals für die Hilfe!
07.06.2018, 16:49	HAL 9000	Auf diesen Beitrag antworten »
Bei teilerfremden Modulen hat man eine eindeutige Lösung, das ist eine der Aussagen des CRT - was will man mehr?
07.06.2018, 16:53	eroy	Auf diesen Beitrag antworten »
Ah ok, dann reicht einfach ein Verweis auf das Theorem und die Eindeutigkeit der Lösung.. Danke
07.06.2018, 16:58	HAL 9000	Auf diesen Beitrag antworten »
Ich meinte natürlich "eindeutig modulo Produkt aller beteiligten Einzelmodule", damit keine Missverständnisse aufkommen. Hier ist dieses Produkt dann tatsächlich $\begin{eqnarray} m=2^3\cdot 3^2=72 \end{eqnarray}$
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »