Beweis Kongruenz/ggT

12.12.2009, 18:19	MichaelZ.	Auf diesen Beitrag antworten »
Beweis Kongruenz/ggT Guten Abend, ich stehe vor einem Problem Ich soll zeigen, dass für alle $\begin{eqnarray} a, b \in \mathbb{Z} ~~\text{und} ~~n, m \in \mathbb{N} \end{eqnarray}$ gilt: Es gibt genau dann ein $\begin{eqnarray} x \in \mathbb{Z} \end{eqnarray}$ mit $\begin{eqnarray} x \equiv a (\mod m) \end{eqnarray}$ und $\begin{eqnarray} x \equiv b (\mod n) \end{eqnarray}$ , wenn $\begin{eqnarray} \text{ggT}(m,n) ~\|~ a-b \end{eqnarray}$ Hätte mir hier jemand einen kleinen Ansatz? Ich komme einfach auf keinen Anfang... Vielen Dank schonmal! Michael
13.12.2009, 10:04	MichaelZ.	Auf diesen Beitrag antworten »
Vielleicht mal das was ich mir inzwischen überlegt habe, vielleicht bringt's ja was: Nach dem Lemma von Bezout gilt: $\begin{eqnarray} \text{ggT}(m,n)=s \cdot m + t \cdot n \end{eqnarray}$ Also: $\begin{eqnarray} s \cdot m + t \cdot n~\|~ a-b \end{eqnarray}$ $\begin{eqnarray} \exists k \in \mathbb{Z}~:~k \cdot (s m + t n) = a-b \end{eqnarray}$ $\begin{eqnarray} a = k (s m + t n) + b \end{eqnarray}$ $\begin{eqnarray} b = -k( s m + t n) +a \end{eqnarray}$ $\begin{eqnarray} x \equiv k (s m + t n) + b (\mod m) \end{eqnarray}$ $\begin{eqnarray} x \equiv k t n + b (\mod m) \end{eqnarray}$ $\begin{eqnarray} x \equiv -k s m + (\mod n) \end{eqnarray}$ Keine Ahnung ob das stimmt und ob das was bringt... Grüße, Michael
13.12.2009, 12:51	Mystic	Auf diesen Beitrag antworten »
Ich denke, du bist da mit der Bezout Identität total auf dem Holzweg... Die ist zwar oft sehr nützlich, das ist richtig, aber hier gerade nicht... Sei im Folgenden $\begin{eqnarray} d:=ggT(m,n) \end{eqnarray}$ Der Nachweis, dass dann $\begin{eqnarray} x \equiv a \mod m, \ x \equiv b \mod n \text{ lösbar } \Rightarrow d\|a-b \end{eqnarray}$ ist trivial, wenn man bedenkt dass für eine Lösung x die beiden Kongruenzen ja auch mod d gelten müssen... Sei also umgekehrt $\begin{eqnarray} d\|a-b \end{eqnarray}$ Ist dann u das Inverse von (m/d) mod (n/d), so ist dann $\begin{eqnarray} x = a+\frac {(b-a)\,u\,m}d \end{eqnarray}$ eine Lösung von $\begin{eqnarray} x \equiv a \mod m, \ x \equiv b \mod n \end{eqnarray}$ wie du hoffentlich leicht selbst nachrechnen kannst...
14.12.2009, 16:11	Hanswurst13	Auf diesen Beitrag antworten »
Bist du auf die Lösung gekommen? Würde mich nämlich auch interessieren..
14.12.2009, 16:41	Mystic	Auf diesen Beitrag antworten »
Wenn du mich meinst und wissen willst, ob ich da selbst draufgekommen bin, dann lautet die Antwort ja... Wenn die Frage aber, wie ich fast eher glaube, an den Threadersteller gerichtet war, dann frage ich mich, was an der ganzen Sache noch unklar sein soll...
14.12.2009, 16:52	Hanswurst13	Auf diesen Beitrag antworten »
Wie kannst du dir sicher sein, dass x e Z, da du einen bruch hast...
Anzeige

14.12.2009, 17:13	Mystic	Auf diesen Beitrag antworten »
Hm, hatte ich nicht für die Umkehrung d\|b-a vorausgesetzt, was nach Adam Riese nichts anderes heißt, als dass sich die Division von (b-a):d ausgeht?? Außerdem sollte d ja sowieso u.a. auch Teiler von m sein, d.h., man kann auch so schon durch d kürzen...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »