Lösbarkeit von Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:24 Fr 18.11.2011 | | Autor: | briddi |
| Aufgabe | 1) Das System
[mm] x\equiv a_1 [/mm] mod [mm] m_1
[/mm]
[mm] x\equiv a_2 [/mm] mod [mm] m_2
[/mm]
ist lösbar genau dann , wenn [mm] a_1\equiv a_2 [/mm] mod [mm] ggT(m_1,m_2).
[/mm]
2) Verallgemeinere 1) induktiv (=alternativer Beweis des (verallgemeinerten) Restsatzes für [mm] R=\IZ [/mm] |
Hallo,
zu 1)
Die Hin-Richtung habe ich bereits gezeigt, da konnte man gleichsetzen (da eine Lösung nach Voraussetzung existiert) und durch Umformen auf die Aussage schließen.
Bei der Rückrichtung habe ich allerdings Probleme. Ich kann die Aussage nur im Spezialfall [mm] ggT(m_1,m_2)=m_1 [/mm] oder [mm] ggT(m_1,m_2)=m_2 [/mm] zeigen, allerdings sonst nicht. Ich schildere mal mein Vorgehen, vielleicht kann mir dann einer von euch einen Tipp geben.
Nach Voraussetzung gilt [mm] a_1\equiv a_2 [/mm] mod [mm] ggT(m_1,m_2), [/mm] das ist gleichbedeutend mit [mm] a_1=a_2+k*d, [/mm] mit [mm] d=ggT(m_1,m_2), k\in \IZ. [/mm]
Dies setze ich nun ein in: [mm] x\equiv a_1 [/mm] mod [mm] m_1, [/mm] also [mm] x=a_1+k_1*m_1, k_1\in \IZ. [/mm] Und damit: [mm] x=a_2+k*d+k_1*m_1
[/mm]
Ich hab versucht die letzten beiden Summanden in die Form [mm] k_2*m_2 [/mm] umzuformen, damit die zweite Kongruenz herauskommt, schaffe das aber nur für die oben genannten Spezialfälle...
Dies scheint also nicht der richtige Weg zu sein, alles andere war leider auch noch nicht zielführend.
zu 2) Hierbei ist mir weder die Aufgabe noch das Vorgehen wirklich klar, soll ich zeigen, dass das System
[mm] x\equiv a_1 [/mm] mod [mm] m_1
[/mm]
...
[mm] x\equiv a_r [/mm] mod [mm] m_r
[/mm]
genau dann lösbar ist, wenn [mm] a_i\equiv a_j [/mm] mod [mm] ggT(m_i, m_j) [/mm] für alle i,j [mm] \le [/mm] r.
(Also sind die [mm] a_i [/mm] paarweise kongruent zueinander?)
Vielen Dank,
briddi
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:15 Sa 19.11.2011 | | Autor: | briddi |
Okay, mittlerweile hab ich auch die andere Richtung hinbekommen bei 1), nur die zweite Aufgabe fehlt leider immer noch.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:12 Sa 19.11.2011 | | Autor: | felixf |
Moin!
> 1) Das System
> [mm]x\equiv a_1[/mm] mod [mm]m_1[/mm]
> [mm]x\equiv a_2[/mm] mod [mm]m_2[/mm]
> ist lösbar genau dann , wenn [mm]a_1\equiv a_2[/mm] mod
> [mm]ggT(m_1,m_2).[/mm]
>
> 2) Verallgemeinere 1) induktiv (=alternativer Beweis des
> (verallgemeinerten) Restsatzes für [mm]R=\IZ[/mm]
>
> zu 1)
Das hast du ja mittlerweile.
Etwas, was hilft, ist eine endliche Menge [mm] $p_1, \dots, p_k$ [/mm] Primzahlen zu nehmen, so dass [mm] $m_1$ [/mm] und [mm] $m_2$ [/mm] jeweils als Potenzprodukt der [mm] $p_i$ [/mm] darstellbar sind. Dann kannst du mit dem Chinesischen Restsatz die Kongruenz $x [mm] \equiv a_1 \pmod{m}$ [/mm] zu einem Kongruenzsystem $x [mm] \equiv a_1 \pmod{p_i^{e_i}}$ [/mm] mit passenden [mm] $e_i \in \IN$ [/mm] abaendern.
Wenn du jetzt zwei solche Kongruenzsysteme $x [mm] \equiv a_1 \pmod{p_i^{e_i}}$ [/mm] und $x [mm] \equiv a_2 \pmod{p_i^{f_i}}$ [/mm] hast, musst du dir ueberlegen, wann diese gleichzeitig loesbar sind. Daraus ergibt sich die Bedingung aus der Aufgabenstellung.
> zu 2) Hierbei ist mir weder die Aufgabe noch das Vorgehen
> wirklich klar, soll ich zeigen, dass das System
> [mm]x\equiv a_1[/mm] mod [mm]m_1[/mm]
> ...
> [mm]x\equiv a_r[/mm] mod [mm]m_r[/mm]
>
> genau dann lösbar ist, wenn [mm]a_i\equiv a_j[/mm] mod [mm]ggT(m_i, m_j)[/mm]
> für alle i,j [mm]\le[/mm] r.
Genau.
> (Also sind die [mm]a_i[/mm] paarweise kongruent zueinander?)
Ja, und zwar modulo passenden Moduli.
Moeglicherweise kannst du das per Induktion nach $r$ beweisen. Den Fall $r = 2$ hattest du ja schon.
Alternativ kannst du genauso wie bei 1) vorgehen -- zumindest wenn du es so gemacht hast wie ich das oben beschrieben hab.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:51 So 20.11.2011 | | Autor: | briddi |
Hallo, ich muss nochmal nachfragen, denn ich soll die zweite Aufgabe ja induktiv beweisen, ich komm damit nur irgendwie nicht voran.
Der Induktionsanfang ist ja schon gemacht durch Aufgabe 1.
Gelte die Aussage dann also für r, das heißt, das System
[mm] x\eqiuv a_1 [/mm] mod [mm] m_1
[/mm]
...
[mm] x\eqiuv a_r [/mm] mod [mm] m_r [/mm]
ist genau dann lösbar, wenn [mm] a_i \equiv a_j [/mm] mod [mm] ggT(m_i,m_j) [/mm] für i [mm] \not= [/mm] j, 2 [mm] \le [/mm] i,j [mm] \le [/mm] r
Nun muss ich die Aussage für r+1 zeigen. Muss ich Hin- und Rückrichtung einzeln zeigen?
Im Prinzip weiß ich ja, dass sich mein Kongruenzsystem aufgrund der Voraussetzung für r vereinfacht zu zwei Kongruenzen, da für die ersten r Kongruenzen ja eine Lösung existiert. Gelesen hab ich, dass diese die Form hat
[mm] x\equiv [/mm] a' mod [mm] (kgV(m_1,...m_r)). [/mm] ich weiß nicht, inwiefern mir das hilft (oder ob ich das überhaupt voraussetzen darf), es würde aber eben zumindest das Sytem vereinfachen zu:
[mm] x\equiv [/mm] a' mod [mm] (kgV(m_1,...m_r))
[/mm]
[mm] x\equiv a_{r+1} [/mm] mod [mm] (m_{r+1})
[/mm]
Darf man hier wieder annehmen, dass das genau dann lösbar ist, wenn
[mm] a'\equiv a_{r+1} [/mm] mod [mm] (kgV(m_1,...m_r),m_{r+1})
[/mm]
Allerdings komm ich damit nicht weiter, geh ich komplett falsch an die Aufgabe heran?
LG, briddi
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:38 So 20.11.2011 | | Autor: | felixf |
Moin briddi!
> Hallo, ich muss nochmal nachfragen, denn ich soll die
> zweite Aufgabe ja induktiv beweisen, ich komm damit nur
> irgendwie nicht voran.
> Der Induktionsanfang ist ja schon gemacht durch Aufgabe
> 1.
>
> Gelte die Aussage dann also für r, das heißt, das System
>
> [mm]x\eqiuv a_1[/mm] mod [mm]m_1[/mm]
> ...
> [mm]x\eqiuv a_r[/mm] mod [mm]m_r[/mm]
>
> ist genau dann lösbar, wenn [mm]a_i \equiv a_j[/mm] mod
> [mm]ggT(m_i,m_j)[/mm] für i [mm]\not=[/mm] j, 2 [mm]\le[/mm] i,j [mm]\le[/mm] r
>
> Nun muss ich die Aussage für r+1 zeigen. Muss ich Hin- und
> Rückrichtung einzeln zeigen?
> Im Prinzip weiß ich ja, dass sich mein Kongruenzsystem
> aufgrund der Voraussetzung für r vereinfacht zu zwei
> Kongruenzen, da für die ersten r Kongruenzen ja eine
> Lösung existiert. Gelesen hab ich, dass diese die Form
> hat
> [mm]x\equiv[/mm] a' mod [mm](kgV(m_1,...m_r)).[/mm]
Das brauchst du.
> ich weiß nicht,
> inwiefern mir das hilft (oder ob ich das überhaupt
> voraussetzen darf),
Nun, du musst es noch zeigen.
Am besten aenderst du die Aussage, die du zeigen willst, so ab:
Das Gleichungssystem $x [mm] \equiv a_i \pmod{n_i}$, [/mm] $1 [mm] \le [/mm] i [mm] \le [/mm] k$ hat genau dann eine Loesung, wenn [mm] $a_i \equiv a_j \pmod{ggT(n_i, n_j)}$ [/mm] gilt fuer alle $i [mm] \neq [/mm] j$, und falls es eine Loesung gibt, ist diese eindeutig modulo [mm] $kgV(n_1, \dots, n_k)$.
[/mm]
> es würde aber eben zumindest das Sytem
> vereinfachen zu:
> [mm]x\equiv[/mm] a' mod [mm](kgV(m_1,...m_r))[/mm]
> [mm]x\equiv a_{r+1}[/mm] mod [mm](m_{r+1})[/mm]
>
> Darf man hier wieder annehmen, dass das genau dann lösbar
> ist, wenn
> [mm]a'\equiv a_{r+1}[/mm] mod [mm](kgV(m_1,...m_r),m_{r+1})[/mm]
Da fehlt ein ggT, oder?
Aus dieser Gleichung bekommst du sofort $a' [mm] \equiv a_{r+1} \pmod{ggT(m_i, m_{r+1})}$ [/mm] fuer alle $1 [mm] \le [/mm] i [mm] \le [/mm] r$, und da $a' [mm] \equiv a_i \pmod{m_i}$ [/mm] gilt hast du somit [mm] $a_i \equiv a_{r+1} \pmod{ggT(m_i, m_{r+1})}$. [/mm] Weiterhin folgt aus $a' [mm] \equiv a_i \pmod{m_i}$, [/mm] dass auch [mm] $a_i \equiv a_j \pmod{ggT(m_i, m_j)}$ [/mm] gilt.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 21:39 So 20.11.2011 | | Autor: | briddi |
Hallo Felix
erstmal vielen Dank, aber ich hab immer noch Fragen. Entweder ich bin gerade zu müde oder ich hab das Thema einfach noch nicht verstanden, im Moment hab ich das Gefühl gar nichts mehr zu verstehen, also sorry für die vielen Nachfragen ...
> Nun, du musst es noch zeigen.
>
> Am besten aenderst du die Aussage, die du zeigen willst, so
> ab:
>
> Das Gleichungssystem [mm]x \equiv a_i \pmod{n_i}[/mm], [mm]1 \le i \le k[/mm]
> hat genau dann eine Loesung, wenn [mm]a_i \equiv a_j \pmod{ggT(n_i, n_j)}[/mm]
> gilt fuer alle [mm]i \neq j[/mm], und falls es eine Loesung gibt,
> ist diese eindeutig modulo [mm]kgV(n_1, \dots, n_k)[/mm].
Ich steh grad irgendwie auf dem Schlauch, kannst du mir vielleicht erklären wie ich das machen kann?
>
> > es würde aber eben zumindest das Sytem
> > vereinfachen zu:
> > [mm]x\equiv[/mm] a' mod [mm](kgV(m_1,...m_r))[/mm]
> > [mm]x\equiv a_{r+1}[/mm] mod [mm](m_{r+1})[/mm]
> >
> > Darf man hier wieder annehmen, dass das genau dann lösbar
> > ist, wenn
> > [mm]a'\equiv a_{r+1}[/mm] mod [mm](kgV(m_1,...m_r),m_{r+1})[/mm]
>
> Da fehlt ein ggT, oder?
Ja, sorry. Müsste lauten [mm] a'\equiv a_{r+1} [/mm] mod [mm] ggT(kgV(m_1,...m_r),m_{r+1})
[/mm]
Aber nochmal ne Nachfrage, ist dieser Schluss an dieser Stelle möglich, weil ich den Induktionsanfang gemacht habe, also bereits gezeigt habe, dass es für zwei Gleichungen gilt? Ich bin etwas irritiert, weil ich bisher bei Induktionsbeweisen nie nochmal auf den Induktionsanfang zurückgegriffen habe.
>
> Aus dieser Gleichung bekommst du sofort [mm]a' \equiv a_{r+1} \pmod{ggT(m_i, m_{r+1})}[/mm]
> fuer alle [mm]1 \le i \le r[/mm],
Diesen Schluss versteh ich leider immer noch nicht. Woran sieht man denn das? Also wieso kann ich das kgV weglassen und dafür die einzelnen Werte betrachten?
>und da [mm]a' \equiv a_i \pmod{m_i}[/mm]
woher weiß ich das? also ich weiß, dass a' mod [mm] (kgV(m_1,...m_r) [/mm] die ersten (ursprünglichen) r Kongruenzen löst, aber wieso darf ich das auch so schreiben?
> gilt hast du somit [mm]a_i \equiv a_{r+1} \pmod{ggT(m_i, m_{r+1})}[/mm].
Liegt das daran dass [mm] \equiv [/mm] eine Ägivalenzrelation ist? Also wenn ich habe
[mm]a' \equiv a_{r+1} \pmod{ggT(m_i, m_{r+1})}[/mm] und [mm]a' \equiv a_i \pmod{m_i}[/mm], dann nutze ich zuerst die Symmetrieeigenschaft, also auch [mm]a_i \equiv a' \pmod{m_i}[/mm] und anschließend die Transitivität? Aber warum fällt dann das [mm] mod(m_i) [/mm] weg?
Oder setzt du die ersten beiden Kongruenzen gleich, aber auch dann fällt [mm] mod(m_i) [/mm] weg...
> Weiterhin folgt aus [mm]a' \equiv a_i \pmod{m_i}[/mm], dass auch [mm]a_i \equiv a_j \pmod{ggT(m_i, m_j)}[/mm]
> gilt.
>
> LG Felix
>
Ganz lieben Dank,
briddi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 Fr 25.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
