Chinesischer Restsatz

04.11.2008, 00:29

Bjoern1982

Chinesischer Restsatz

Hallo,

seien m und n aus IN
seien x und y aus IZ

ferner gelte mx+ny=1

gegeben:

$\begin{eqnarray*} z\equiv a\ mod\ m \end{eqnarray*}$

$\begin{eqnarray*} z\equiv b\ mod\ n \end{eqnarray*}$

mit z aus IZ

Jetzt soll man folgendes zeigen:

$\begin{eqnarray*} z\equiv (bxm+ayn)\ mod\ (m \cdot n) \end{eqnarray*}$ (*)

Das scheint ja ein Spezialfall des Chinesischen Restsatz zu sein, jedoch komme ich irgendwie nicht drauf wie ich die Kongruenz (*) zeigen kann...

Kann mir jemand helfen ?

Gruß Björn

04.11.2008, 04:43

Lazarus

Auf diesen Beitrag antworten »

Also komm....
$\begin{eqnarray*} mx+ny=\operatorname{ggT}(m,n) \end{eqnarray*}$

04.11.2008, 11:04

Bjoern1982

Auf diesen Beitrag antworten »

Ja gut, hätte ich vielleicht noch dabei schreiben sollen dass mir schon klar ist dass durch diese Gleichung m und n teilerfremd sind...wie mich das weiterbringt ist halt das Problem.

04.11.2008, 11:43

Auf diesen Beitrag antworten »

Zunächst mal sagt der Chinesische Restsatz, dass es im Fall teilerfremder $\begin{eqnarray*} m,n \end{eqnarray*}$ bei gegebenen

$\begin{eqnarray*} z \equiv a \mod\ m \end{eqnarray*}$

$\begin{eqnarray*} z \equiv b \mod\ n \end{eqnarray*}$

genau eine Lösung $\begin{eqnarray*} z \end{eqnarray*}$ modulo $\begin{eqnarray*} m\cdot n \end{eqnarray*}$ dieser simultanen Kongruenz gibt. Im folgenden musst du lediglich noch nachweisen, dass $\begin{eqnarray*} bxm+ayn \end{eqnarray*}$ diese Lösungsrestklasse ist, und zwar durch eine Probe, bei der du natürlich $\begin{eqnarray*} mx+ny=1 \end{eqnarray*}$ nutzen darfst (und musst).

04.11.2008, 12:09

Bjoern1982

Auf diesen Beitrag antworten »

Hmm...also so ?

bxm+ayn=bxm+a(1-xm)=a+(b-a)xm ist kongruent a mod m

bxm+ayn=b(1-ny)+ayn=b+(a-b)yn ist kongruent b mod n

Wenn das denn so stimmt, warum darf ich dann einfach so mit den Modulos rumspielen, also die Probe für einen Term machen, der vorher modulo m*n betrachtet wurde jetzt einfach separat nach Belieben einmal für einen Nachweis modulo m und modulo n verwenden ?

04.11.2008, 12:14

Auf diesen Beitrag antworten »

Zitat:

Original von Bjoern1982
Wenn das denn so stimmt, warum darf ich dann einfach so mit den Modulos rumspielen, also die Probe für einen Term machen, der vorher modulo m*n betrachtet wurde jetzt einfach separat nach Belieben einmal für einen Nachweis modulo m und modulo n verwenden ?

Weil $\begin{eqnarray*} m \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ Teiler von $\begin{eqnarray*} mn \end{eqnarray*}$ sind!

Es ist eine banale Folgerung aus der Modulrechnung, dass für $\begin{eqnarray*} r|s \end{eqnarray*}$ die Implikation

$\begin{eqnarray*} x\equiv y \mod s \quad \Longrightarrow\quad x\equiv y \mod r \end{eqnarray*}$

gilt! Wenn du es nicht glaubst, dann weise es nach.

04.11.2008, 12:59

Bjoern1982

Auf diesen Beitrag antworten »

s=r*t => x=k*(r*t)+y <=> x=(k*t)*r+y Augenzwinkern

Ok, dank dir smile

Neue Frage »

Antworten »

Chinesischer Restsatz

Verwandte Themen