Allgemeine Lösung von simultanen Kongruenzen

16.07.2014, 12:45	MartinL	Auf diesen Beitrag antworten »
Allgemeine Lösung von simultanen Kongruenzen Moin, in folgender Aufgabe geht es um simultane Kongruenzen. Ich glaube, die Aufgabe gelöst zu haben und würde mich sehr freuen, wenn jemand das bestätigen würde. Aufgabe: Sei $\begin{eqnarray} 2 \leq n \in \mathbb{Z} \end{eqnarray}$ und $\begin{eqnarray} a_1,....,a_n \in \mathbb{Z} \end{eqnarray}$ ferner seien $\begin{eqnarray} m_1,....,m_n \in \mathbb{Z} \end{eqnarray}$ paarweise Teilerfremd. Zeige: Die Lösung der simultanen Kongruenzen $\begin{eqnarray} x \equiv a_i \ mod \ m_i \end{eqnarray}$ für $\begin{eqnarray} 1 \leq i \leq n \end{eqnarray}$ ist gegeben durch $\begin{eqnarray} x_0 := \sum\limits_{i=1}^n a_is_iM_i \end{eqnarray}$ wobei $\begin{eqnarray} M := \prod\limits_{i=1}^n m_i \end{eqnarray}$ , $\begin{eqnarray} M_i := \frac{M}{m_i} \end{eqnarray}$ und $\begin{eqnarray} s_i \in \mathbb{Z} \end{eqnarray}$ mit $\begin{eqnarray} s_iM_i \equiv 1 \ mod \ m_1 \end{eqnarray}$ für $\begin{eqnarray} 1 \leq i \leq n \end{eqnarray}$ . Lösung: Sei $\begin{eqnarray} a_i < m_i \end{eqnarray}$ . Das kann ich annehmen, da ich sowieso auf Kongruenz modulo mi prüfe. Falls ein ai also größer ist, rechne ich einfach so lange ai mod mi, bis ai kleiner ist als mi. Dabei ändere ich nichts am Ergebnis. Damit ist zu zeigen: $\begin{eqnarray} (\sum\limits_{i=1}^n a_is_iM_i) \ mod \ m_i = a_i \end{eqnarray}$ Zuerst schaue ich mir den i-ten Summanden an, welcher folgendermaßen aussieht: $\begin{eqnarray} (... + a_is_iM_i + ....) \ mod \ m_i \end{eqnarray}$ $\begin{eqnarray} \Leftrightarrow (... + (a_is_iM_i) \ mod \ m_i + ....) \ mod \ m_i \end{eqnarray}$ $\begin{eqnarray} \Leftrightarrow (... + (a_i \ mod \ m_i )(s_iM_i \ mod \ m_i) + ....) \ mod \ m_i \end{eqnarray}$ $\begin{eqnarray} \Leftrightarrow (... + a_i 1 + ....) \ mod \ m_i \end{eqnarray}$ In jedem anderen Summanden $\begin{eqnarray} a_ks_kM_k \end{eqnarray}$ ist $\begin{eqnarray} m_i \end{eqnarray}$ als Faktor in $\begin{eqnarray} M_k \end{eqnarray}$ enthalten. Es gilt also $\begin{eqnarray} (a_ks_kM_k) \ mod \ m_i = 0 \end{eqnarray}$ und somit sind alle Summanden, außer dem i-ten Summanden 0. Insgesamt gilt damit die Aussage: $\begin{eqnarray} (\sum\limits_{i=1}^n a_is_iM_i) \ mod \ m_i = a_i \end{eqnarray*}$ Kommt das so hin? Oder hab ich irgendwo etwas vorrausgesetzt, was ich nicht hätte vorraussetzen dürfen? Bisher hege ich die Hoffnung, dass diese Aufgabe endlich mal direkt von Anfang an richtig gelöst ist . Gruß Martin
16.07.2014, 15:34	RavenOnJ	Auf diesen Beitrag antworten »
RE: Allgemeine Lösung von simultanen Kongruenzen Deine Argumentation ist richtig, aber du hast es zu kompliziert aufgeschrieben. Schreib doch einfach $\begin{align} s_i M_i =1\!\!\!\mod m_i\Rightarrow a_i s_i M_i = a_i\cdot 1 = a_i\!\!\!\mod m_i \end{align}$ da gilt: $\begin{eqnarray} y=r\!\!\!\mod m\land z=s\!\!\!\mod m\Rightarrow yz = rs\!\!\!\mod m \end{eqnarray}$ Außerdem ist $\begin{eqnarray} \forall k\not=i: m_i\mid M_k\Rightarrow a_k s_k M_k=0 \!\!\!\mod m_i \end{eqnarray}$ sodass zusammenfassend für alle i gilt: $\begin{eqnarray} x_0 := \sum\limits_{k=1}^n a_k s_k M_k=a_i \!\!\!\mod m_i \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »