system simultaner kongruenzen loesen

30.06.2010, 15:47

mathelisl

system simultaner kongruenzen loesen

hallo!

zu loesen:

2x = 1 mod 5
3x = 2 mod 7
4x = 1 mod 11

man kann schnell herausfinden das 3 eine (und einzige) loesung ist (indem man jede gleichung fuer sich loest, und dann draufkommt das alle drei die gleiche loesung haben...so hab ich das gemacht :P)

gibts ein algorithmus mit dem man das allgemein machen kann - also so dass das immer funktioniert sofern das system loesbar ist?
einen in der art wie es am ende dieses dokumentes vorgeschlagen wird - ein algorithmus fuer systeme der form x=a mod m:
http://www.uni-regensburg.de/Fakultaeten.../kapI_para6.pdf

kann ich eine gleichung der form ax=b mod m zu eine gleichung in der form
x=t mod m umwandeln? wenn ja wie?

lg

30.06.2010, 16:05

system-agent

Auf diesen Beitrag antworten »

RE: system simultaner kongruenzen loesen

Zitat:

Original von mathelisl
kann ich eine gleichung der form ax=b mod m zu eine gleichung in der form
x=t mod m umwandeln? wenn ja wie?

Ganz allgemein ist das schwierig, aber wenn $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} m \end{eqnarray*}$ teilerfremd sind, dann gibt es ein Element $\begin{eqnarray*} s \end{eqnarray*}$ Modulo $\begin{eqnarray*} m \end{eqnarray*}$ derart, dass $\begin{eqnarray*} s\cdot a=1 \end{eqnarray*}$ Modulo $\begin{eqnarray*} m \end{eqnarray*}$ .

Hier wären demnach die fragen:
Was ist das Inverse von 2 mod 5? Welches das von 3 mod 7? Welches das von 4 mod 11?

30.06.2010, 16:09

mathelisl

Auf diesen Beitrag antworten »

RE: system simultaner kongruenzen loesen
ok das heisst ich kann das system im allgemeinen nicht so veraendern dass ich den algorithmus aus dem skript anwenden kann.... :-(

gibts einen algorithmus mit dem ich das system loesen kann?
oder soll ich hoffen das kleine zahlen zur pruefung kommen? :P

30.06.2010, 16:25

mathelisl

Auf diesen Beitrag antworten »

RE: system simultaner kongruenzen loesen
es gilt doch auch wenn a und m teilerfremd sind hat jede gleichung nur eine loesung
da es einen satz gibt der lautet ax=b mod m genau dann loesbar wenn ggT(a,m)b und die Anzahl der mod m inkongruenten Loesungen ist gerade ggT(a,m)

und wenn alle diese Gleichungen je nur eine Loesung haben, dann muessen die uebereinstimmen falls das System loesbar sein soll - oder?

allerdings der
der Chinesische Restsatz sagt ja aus das ein system bei dem die modulen paarweise relativ teilerfremd sind genau eine loesung mod (produkt der modulen) hat.

d.h. in meinem fall lautet die loesung wie?
3 = x mod ( 5*7*11) ??? dh. alle zahlen x die bei der division mit rest durch 5*7*11=385 den rest 3 haben sind loesungen des systems? d.h. z.b. die zahl 773 (2*385 = 3)ist eine.

30.06.2010, 16:44

system-agent

Auf diesen Beitrag antworten »

Anscheinend hast du meine Antwort nicht gelesen.

Zb. gilt $\begin{eqnarray*} 2\cdot3=6\equiv1\mod5 \end{eqnarray*}$ , also kriegt man für die erste Gleichung $\begin{eqnarray*} x\equiv3\mod 5 \end{eqnarray*}$ . Das kannst du mit den anderen beiden auch machen.

Da hier natürlich 5,7,11 paarweise teilerfremd sind, kannst du den chinesischen Satz nutzen.

30.06.2010, 17:04

mathelisl

Auf diesen Beitrag antworten »

doch hab ich schon gelesen, aber offenbar nicht verstanden (peinlich).

ok. also folgende strategie fuers losen von systemen ax=b mod m merk ich mir fuer die pruefung:

1) wenn die modulen paarweise teilerfremd sind dann nehm ich den chinsischen restsatz

2) wenn das nicht so ist, dann schau ich ob ggT(a,m)=1 ist, und such die inversen um die gleichungen zu vereinfachen

3) falls weder 1 noch 2 zutrifft dann lass ich das beispiel aus, oder schau mal was der nachbar macht :P

passt das so?

30.06.2010, 18:43

system-agent

Auf diesen Beitrag antworten »

Der chinesische Restsatz sagt etwas über Systeme der Bauart
$\begin{eqnarray*} x\equiv a_1\mod m_1 \end{eqnarray*}$
$\begin{eqnarray*} x\equiv a_2\mod m_2 \end{eqnarray*}$
...
$\begin{eqnarray*} x\equiv a_n\mod m_n \end{eqnarray*}$ .

Falls aber die Unbekannte $\begin{eqnarray*} x \end{eqnarray*}$ nicht alleine auf einer Seite der Gleichung steht, dann musst du erst dahin umformen bevor du den Satz nimmst.

Punkt (3) würde ich eher mal nicht empfehlen Big Laugh

Neue Frage »

Antworten »

system simultaner kongruenzen loesen

Verwandte Themen