ggT = 1 < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei L = { [mm] a^{i},a^{j} [/mm] } für i,j [mm] \ge [/mm] 1.
Zeigen Sie für den Fall ggT(i,j) = 1, dass L* für ein geeignetes [mm] k_{0} [/mm] alle Wröter [mm] a^{k} [/mm] enthält mit k [mm] \ge k_{0}.
[/mm]
Zeigen Sie, dass die Behauptung nicht zutrifft für ggT(i,j) > 1. |
Also für die Nicht-Informatiker unter uns erklär ich kurz, was mit der Aufgabenstellung gemeint ist:
[mm] a^{i},a^{j} [/mm] sind 2 Wörter der Sprache L.
Also Beispielsweise [mm] a^{3} [/mm] und [mm] a^{5}.
[/mm]
In L* sind dann alle Wörter die man durch beliebige Multiplikation dieser Wörter erhält.
Also zum Beispiel:
[mm] a^{3}
[/mm]
[mm] a^{5}
[/mm]
[mm] a^{6} [/mm] = [mm] a^{3}*a^{3}
[/mm]
[mm] a^{8} [/mm] = [mm] a^{3}*a^{5}
[/mm]
[mm] a^{10} [/mm] = [mm] a^{5}*a^{5}
[/mm]
[mm] a^{12} [/mm] = [mm] a^{6}*a^{6}
[/mm]
.
.
.
gezeigt werden soll nun, dass für alle teilerfremden i,j ab einem bestimmten [mm] k_{0} [/mm] diese auflistung "lückenlos" ist.
Ich hab keine Idee wie ich an die Sache ran gehen soll.
---
Ein Gegenbeispiel für den zweiten Aufgabenteil zu finden ist relativ einfach
L = { [mm] a^{2}, a^{4} [/mm] } definiert offensichtlich alle Wört [mm] a^{2n} [/mm] mit n [mm] \in \IN [/mm] => [mm] a^{2n+1} [/mm] lässt sich nie bilden.rr
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:40 So 27.04.2008 | | Autor: | felixf |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo
> Sei L = { [mm]a^{i},a^{j}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
} für i,j [mm]\ge[/mm] 1.
>
> Zeigen Sie für den Fall ggT(i,j) = 1, dass L* für ein
> geeignetes [mm]k_{0}[/mm] alle Wröter [mm]a^{k}[/mm] enthält mit k [mm]\ge k_{0}.[/mm]
>
> Zeigen Sie, dass die Behauptung nicht zutrifft für ggT(i,j)
> > 1.
> Also für die Nicht-Informatiker unter uns erklär ich kurz,
> was mit der Aufgabenstellung gemeint ist:
> [mm]a^{i},a^{j}[/mm] sind 2 Wörter der Sprache L.
>
> Also Beispielsweise [mm]a^{3}[/mm] und [mm]a^{5}.[/mm]
>
> In L* sind dann alle Wörter die man durch beliebige
> Multiplikation dieser Wörter erhält.
> Also zum Beispiel:
> [mm]a^{3}[/mm]
> [mm]a^{5}[/mm]
> [mm]a^{6}[/mm] = [mm]a^{3}*a^{3}[/mm]
> [mm]a^{8}[/mm] = [mm]a^{3}*a^{5}[/mm]
> [mm]a^{10}[/mm] = [mm]a^{5}*a^{5}[/mm]
> [mm]a^{12}[/mm] = [mm]a^{6}*a^{6}[/mm]
> .
> .
> .
> gezeigt werden soll nun, dass für alle teilerfremden i,j
> ab einem bestimmten [mm]k_{0}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
diese auflistung "lückenlos"
> ist.
> Ich hab keine Idee wie ich an die Sache ran gehen soll.
Das Stichwort lautet: Bezout-Gleichung. Demnach gibt es $f, g \in \IZ$ mit $f i + g j = 1$. Erstmal ist vermutlich eins der $f$ und $g$ negativ. Sagen wir mal, das $f$ negativ ist.
Wenn du dann ein beliebiges $z \in \IN$ hast, kannst du es ja schreiben als $z = q i + r$ mit $0 \le r < i$. Dann ist $z = q i + r (f i + g j)$. Kannst du Anhand dessen ein $z_0$ angeben, fuer welches die Aussage gilt?
> Ein Gegenbeispiel für den zweiten Aufgabenteil zu finden
> ist relativ einfach
> L = { [mm]a^{2}, a^{4}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
} definiert offensichtlich alle Wört
> [mm]a^{2n}[/mm] mit n [mm]\in \IN[/mm] => [mm]a^{2n+1}[/mm] lässt sich nie bilden.rr
Genau. Du kannst auch fuer allgemeine $i, j$ mit $d := ggT(i, j) > 1$ ein Gegenbeispiel angeben, welches nur von $d$ abhaengt.
LG Felix
|
|
|
| |
|
Danke schonmal für den Hinweis.
Die Bezout gleichung ist mir in den mathematischen Grundlagen schonmal übern Weg gelaufen, da im Zusammenhang mit dem Euklidischen Algoriothmus, also ebenfalls ggT.
Trotzdem komme ich damit nicht weiter. Wenn ich deine Hinweis verwende:
z = q*i + r
[mm] \gdw [/mm] z = q*i + r*1
[mm] \gdw [/mm] z = q*i + r*( f*i + g*j)
und nu? ausmultiplizierren bringt auch nix. Also zumindest nicht was mir zeigt dass die Liste oben irgendwann keine Lücken mehr aufweist...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:22 Mo 28.04.2008 | | Autor: | felixf |
Hallo
> Trotzdem komme ich damit nicht weiter. Wenn ich deine
> Hinweis verwende:
>
> z = q*i + r
> [mm]\gdw[/mm] z = q*i + r*1
> [mm]\gdw[/mm] z = q*i + r*( f*i + g*j)
>
> und nu? ausmultiplizierren bringt auch nix.
Doch, sehr viel. Danach musst du halt wieder zusammenfassen, dass du etwas in der Form [mm] $\alpha [/mm] i + [mm] \beta [/mm] j$ da stehen hast. Sowas kannst du ja darstellen, solange [mm] $\alpha, \beta \ge [/mm] 0$ sind.
LG Felix
|
|
|
| |
|
Also irgendwie steh ich immer noch auffem Schlauch oder seh den Wald vor lauter Bäumen nicht.
Also ich schreibmal was ich bisher hab.
Mitder Bezout-Gleichung (vgl. math. Grundlagen) folgt:
[mm] \exists [/mm] f,g [mm] \in \IZ [/mm] mit fi+gj = 1. Dabei sind i,j teilerfremd.
Darüber hinaus gilt: Jede beliebige Zahl z [mm] \in \IN [/mm] kann man durch
z = q*i + r ausdrücken
z = q*i + r
[mm] \gdw [/mm] z = q*i +r*1
[mm] \gdw [/mm] z = q*i +r*(f*i + g*j)
[mm] \gdw [/mm] z = q*i +r*f*i + r*g*j
[mm] \gdw [/mm] z = (q +r*f)*i + r*g*j
Setze nun [mm] \alpha [/mm] := (q+r*f) und [mm] \beta [/mm] := (r*g)
[mm] \Rightarrow [/mm] z = [mm] \alpha [/mm] * i + [mm] \beta*j
[/mm]
-----------------
Damit hab ich ja nur gezeigt dass ich eine Zahl z durch die Teilerfremden Zahlen i und j ausdrücken kann. Was hat das aber mit der Aufgabe zu tun?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:24 Di 29.04.2008 | | Autor: | felixf |
Hallo!
> Also irgendwie steh ich immer noch auffem Schlauch oder seh
> den Wald vor lauter Bäumen nicht.
>
> Also ich schreibmal was ich bisher hab.
>
> Mitder Bezout-Gleichung (vgl. math. Grundlagen) folgt:
>
> [mm]\exists[/mm] f,g [mm]\in \IZ[/mm] mit fi+gj = 1. Dabei sind i,j
> teilerfremd.
>
> Darüber hinaus gilt: Jede beliebige Zahl z [mm]\in \IN[/mm] kann man
> durch
> z = q*i + r ausdrücken
>
> z = q*i + r
> [mm]\gdw[/mm] z = q*i +r*1
> [mm]\gdw[/mm] z = q*i +r*(f*i + g*j)
> [mm]\gdw[/mm] z = q*i +r*f*i + r*g*j
> [mm]\gdw[/mm] z = (q +r*f)*i + r*g*j
>
> Setze nun [mm]\alpha[/mm] := (q+r*f) und [mm]\beta[/mm] := (r*g)
>
> [mm]\Rightarrow[/mm] z = [mm]\alpha[/mm] * i + [mm]\beta*j[/mm]
> -----------------
>
> Damit hab ich ja nur gezeigt dass ich eine Zahl z durch die
> Teilerfremden Zahlen i und j ausdrücken kann. Was hat das
> aber mit der Aufgabe zu tun?
Wie sehen die Elemente aus [mm] $L^\ast$ [/mm] denn aus?
LG Felix
|
|
|
|
