Jede Zahl als Summe 2er teilerfr. Zahlen

07.08.2008, 10:18

aRo

Jede Zahl als Summe 2er teilerfr. Zahlen

Hallo!

Die Aufgabe ist aus der Informatik entlehnt, genauer aus den formalen Sprachen. Wie ihr mir aber sicher zustimmen werdet, ist das Problem aber eher mathematischer Natur.

Die Aufgabe:

Wir haben eine Sprache L gegeben, mit folgenden Eigenschaften:
$\begin{eqnarray*} L = \{ a^i, a^j \} \, \, i,j \geq 1 , \, ggT(i,j)=1 \end{eqnarray*}$

z.z. $\begin{eqnarray*} L^{\star} \end{eqnarray*}$ enthält für ein geeignetes k0 alle Wörter $\begin{eqnarray*} a^k \end{eqnarray*}$ mit $\begin{eqnarray*} k \geq k_0 \end{eqnarray*}$ .

Lässt sich so übersetzen:
Es ist zu zeigen, dass ab einem bestimmten k0 alle natürlichen Zahlen größer gleich k0 durch eine Summe zweier teilerfremder natürliche Zahlen i und j dargestellt werden können, genauer, dass gilt $\begin{eqnarray*} k=z \cdot j + m \cdot i \end{eqnarray*}$ für $\begin{eqnarray*} k \geq k_0 \end{eqnarray*}$

Ich fange mal mit der zweiten, ausgereifteren Idee an:

Wenn ich zeigen könnte, dass unter der Voraussetzung (o.B.d.A) i<j Vielfache von i alle Restklassen mod j darstellen können, dann würde das doch heißen, dass ich mit Vielfachen von i alle Zahlen zwischen z*j und (z+1)j "treffen" könnte. Ich nehme also eine bestimmte Anzahl j und addiere sozusagen die Restklasse drauf, um eine Zahl die kein Vielfaches von j ist hinzubekommen.
Schlecht erklärt, ich hoffe ihr versteht, was ich meine.

Beweis:
Es gelte k mod j = l für irgendein l<=k.
Nun muss ich diesen Rest l durch Vielfache von i darstellen können, also muss es ein m geben, so dass:
$\begin{eqnarray*} m \cdot i mod j = l \end{eqnarray*}$ ist.

Wenn es so ein m für ein l nicht gäbe, dann müssten mindestens zwei m dieselbe Restklasse darstellen.
Das heißt, es müsste m1 und m2 geben, so dass
$\begin{eqnarray*} m_1 \cdot i mod j = m_2 \cdot i mod j \end{eqnarray*}$

Das hieße wiederum, dass entweder i j teilen muss (was nach Voraussetzung nicht geht!) oder m1-m2. Warum sollte letzteres nicht gehen? Da habe ich gerade ne Blockade.. verwirrt

Wann das nicht ginge, dann wäre ich ja so gut wie fertig...sofern die Idee und alles stimmt.

1.Idee:
Ich habe mir überlegt, ob man das nicht vielleicht induktiv lösen kann. Dazu müsste ich sozusagen garantieren, dass ich die 1 aus den beiden Zahlen darstellen kann.
Nehmen wir zum Beispiel i=2 und j=5. Dann kriege ich die 1 so hin: 1=6-5
Wenn ich dann noch garantieren könnte, dass es irgendwo 6 Zahlen hintereinander gibt, die ich durch eine Summe darstellen kann, dann wüsste ich, dass auch alle darauffolgenden Zahlen darstellbar sind.
Beim Beispiel: 14,15,16,17,18,19 sind darstellbar. Jetzt kann ich immer 5 abziehen und 6 addieren und habe die nächste Zahl. Das heißt, ab 14 müssten alle Zahlen darstellbar sein.
Vor allem würde mich interessieren, wie man denn dieses k0 nun festnagelt und finden kann?

Dankeschön!

07.08.2008, 11:37

Auf diesen Beitrag antworten »

Zitat:

Original von aRo
Es ist zu zeigen, dass ab einem bestimmten k0 alle natürlichen Zahlen größer gleich k0 durch eine Summe zweier teilerfremder natürliche Zahlen i und j dargestellt werden können,

Das ist eine ganz schlechte sprachliche Umsetzung von

Zitat:

Original von aRo
dass gilt $\begin{eqnarray*} k=z \cdot j + m \cdot i \end{eqnarray*}$ für $\begin{eqnarray*} k \geq k_0 \end{eqnarray*}$

Zum einen handelt es sich nicht nur um die Summe zweier Zahlen - zum anderen klingt die erste Formulierung so, als könnte man die $\begin{eqnarray*} i,j \end{eqnarray*}$ frei wählen, anstatt dass sie vorgegeben sind!

Aus dem ganzen langen, für mich ziemlich verworren wirkenden Text extrahiere ich mal folgendes:

Du hast zwei teilerfremde positive Zahlen $\begin{eqnarray*} i,j \end{eqnarray*}$ vorgegeben und willst nun zeigen, dass es eine natürliche Zahl $\begin{eqnarray*} k_0 \end{eqnarray*}$ gibt,
so dass es für alle $\begin{eqnarray*} k\geq k_0 \end{eqnarray*}$ eine Linearkombinations-Darstellung

$\begin{eqnarray*} k = z\cdot j + m\cdot i \end{eqnarray*}$

mit nichtnegativen $\begin{eqnarray*} z,m \end{eqnarray*}$ gibt. Ist es das, was du willst?

Wo ist jetzt das Problem? Aus der Zahlentheorie (Lemma von Bézout) ist bekannt, dass das für alle ganzen Zahlen $\begin{eqnarray*} k \end{eqnarray*}$ zumindest mit ganzen Zahlen $\begin{eqnarray*} z,m \end{eqnarray*}$ möglich ist. Mit ein paar Zusatzüberlegungen sollte dann auch klar sein, dass das für $\begin{eqnarray*} k\geq ij-i-j+1 \end{eqnarray*}$ (also $\begin{eqnarray*} k_0=ij-i-j+1 \end{eqnarray*}$ ) auch mit nichtnegativen $\begin{eqnarray*} z,m \end{eqnarray*}$ möglich ist.

EDIT (nach 3 Tagen): Wäre schön, wenn du wenigstens dazu

Zitat:

Original von Arthur Dent
Ist es das, was du willst?

ein Feedback geben könntest...

15.08.2008, 16:09

aRo

Auf diesen Beitrag antworten »

hallo Arthur!

Danke für deine Antwort und entschuldige meine zugegeben späte Reaktion.

Ja, du hast das Problem dann immerhin doch aus meinen Text richtig extrahieren können smile

Das Lemma von Bézout ist mir unter diesem Namen noch nicht unter gekommen, allerdings ist mir die Aussage wohl bekannt, denn den erweiterten euklidischen Algorithmus haben wir mal behandelt.
Mir fehlt allerdings noch die direkte Verbindung zu der Aufgabe und leider auch die Zeit, diese aufzudecken.

Daraus, dass du auf meine Ideen nicht eingegangen bist, schließe ich, dass auch diese nicht besonders verständlich rüberkamen?
Denn ich fänd es schöner, eigene Ideen zu verfolgen, das verstehe ich besser Augenzwinkern

Ich werde mich bemühen mir das Lemma bald nochmal genauer anzugucken und obigen Post nochmal etwas deutlicher zu machen.

Leider fehlt mir momentan wie gesagt die Zeit.

Gruß,
aRo

15.08.2008, 16:24

Auf diesen Beitrag antworten »

Danke für die Klarstellung. Deine Lösungsidee

Zitat:

Original von aRo
Jetzt kann ich immer 5 abziehen und 6 addieren und habe die nächste Zahl. Das heißt, ab 14 müssten alle Zahlen darstellbar sein.

passt aber überhaupt nicht dazu:

Mit der gerätst du irgendwann zu negativen Vorfaktoren vor der 5, und das ist ja dann keine Lösung mehr...

Wegen dieser und anderer Argumente könnte ich deine Überlegungen zerpflücken - ich fand es konstruktiver, einen Weg zur wirklichen Lösung des Problems zu skizzieren.

15.08.2008, 16:48

aRo

Auf diesen Beitrag antworten »

Ach, ja, jetzt habe ich kapiert, was du meinst. Da hast du natürlich recht und daher ist der Ansatz schon mal unsinnig. Kann ich deine Verwirrung um die Aufgabenstellung auch noch besser verstehen.

Ich denke aber der erste Ansatz müsste klappen. Über den denke ich später nochmal nach, jetzt muss ich mich leider mit Latex rumschlagen Augenzwinkern

15.08.2008, 17:07

Auf diesen Beitrag antworten »

Ok, du beharrst also auf diese Idee. Dann solltest du sie allerdings auch nochmal klar verständlich darlegen, wenn du Resonanz darauf erwartest. Für mich ist es jedenfalls einfacher, das Gesamtproblem zu lösen, als deine Idee zu verstehen:

Gemäß chinesischem Restsatz kann man die insgesamt $\begin{eqnarray*} ij \end{eqnarray*}$ Restklassen

$\begin{eqnarray*} [k] := \left\{ k+r\cdot ij \bigm| r\in\mathbb{Z} \right\},\qquad k=0,1,\ldots,ij-1 \end{eqnarray*}$

modulo $\begin{eqnarray*} ij \end{eqnarray*}$ auch über $\begin{eqnarray*} [zj+mi] \end{eqnarray*}$ mit $\begin{eqnarray*} z=0,\ldots,i-1 \end{eqnarray*}$ und $\begin{eqnarray*} m=0,\ldots,j-1 \end{eqnarray*}$ parametrisieren.

Mit genau diesen Grenzen für $\begin{eqnarray*} z,m \end{eqnarray*}$ ist klar, dass $\begin{eqnarray*} zj+mi \end{eqnarray*}$ auch die kleinste ganze Zahl in der Restklasse $\begin{eqnarray*} [zj+mi] \end{eqnarray*}$ ist, die sich mit nichtnegativen Vorfaktoren vor $\begin{eqnarray*} j,i \end{eqnarray*}$ darstellen lässt. Offenbar ist dann also die nächstkleinere Zahl innerhalb dieser Restklasse - das ist $\begin{eqnarray*} k=zj+mi-ij \end{eqnarray*}$ - die größte ganze Zahl, die sich in derselben Restklasse $\begin{eqnarray*} [zj+mi] \end{eqnarray*}$ NICHT mit nichtnegativen Vorfaktoren darstellen lässt. Über alle $\begin{eqnarray*} ij \end{eqnarray*}$ Restklassen (gemäß der benutzten Parametrisierung) maximiert ergibt sich, dass

$\begin{eqnarray*} \max\limits_{z=0,\ldots,i-1} ~ \max\limits_{m=0,\ldots,j-1} ~ (zj+mi-ij) = (i-1)j+(j-1)i-ij = ij-i-j \end{eqnarray*}$

die insgesamt größte ganze Zahl ist, die sich NICHT mit nichtnegativen Vorfaktoren darstellen lässt! Im Umkehrschluss ist eine solche Darstellung also für alle $\begin{eqnarray*} k\geq k_0 \end{eqnarray*}$ mit $\begin{eqnarray*} k_0=ij-i-j+1 \end{eqnarray*}$ möglich. Nach der vorangehenden Darstellung sollte auch klar sein, dass diese Grenze scharf ist, d.h., es gibt kein kleineres $\begin{eqnarray*} k_0 \end{eqnarray*}$ mit dieser Eigenschaft.

Auf dein Beispiel $\begin{eqnarray*} i=2,j=5 \end{eqnarray*}$ angewandt ergibt sich z.B. $\begin{eqnarray*} k_0=4 \end{eqnarray*}$ (deswegen verstehe ich auch nicht, warum du erst bei 14 anfängst...)

25.08.2008, 12:18

aRo

Auf diesen Beitrag antworten »

hallo Arthur!

Bevor wir zu meiner Idee zurück kommen, würde ich gerne, zumindest in groben Zügen, deine Lösung nachvollziehen können.
Ich habe das jetzt eine Weile versucht, aber es scheint schon am einfachsten bei mir zu scheitern.

Ich denke als erstes muss ich nochmal abklären, ob ich deine Definitionen richtig verstanden habe.
Also mit $\begin{eqnarray*} [k] \end{eqnarray*}$ bezeichnest du einfach alle Restklassen modulo $\begin{eqnarray*} ij \end{eqnarray*}$ , um mal bei unserem Beispiel (i=2, j=5) zu bleiben, wäre also $\begin{eqnarray*} [k] = \{0,1,2,3,4,5,6,7,8,9\} \end{eqnarray*}$ .
Nun sagst du, dass der chinesische Restsatz sagt, dass das auch über $\begin{eqnarray*} [z5 + m2] = \{z5+m2+r \cdot 10 | r \in \mathbb Z \} \end{eqnarray*}$ modulo 10 mit $\begin{eqnarray*} z = 0 \dots 1 \, \mbox{und} \, m=0 \dots 4 \end{eqnarray*}$ darstellbar ist.
(Warum dem so ist, ist mir auch noch nicht ganz klar. Nach Wikipedia beschreibt der Chinesische Restsatz ja das Lösen von simultanen Kongruenzen. Die Brücke zu unserer Anwendung hier habe ich noch nicht schlagen können).

Ich habe das jetzt allerdings für unser Beispiel mal ausprobiert, und da klappt es zumindest.

So, jetzt sagst du, dass $\begin{eqnarray*} zj+mi \end{eqnarray*}$ die kleinste Zahl in der Restklasse $\begin{eqnarray*} [zj+mi] \end{eqnarray*}$ ist, die sich mit nichtnegativen Vorfaktoren j,i darstellen lässt.
So, und das kann ich nicht nachvollziehen. Wenn ich dich bis hierhin nämlich richtig verstanden habe, dann ist die kleinste Zahl in $\begin{eqnarray*} [z5+m2] \end{eqnarray*}$ die 0, und das ist sie für alle i und j.
Außerdem verstehe ich nicht, wie du bei $\begin{eqnarray*} zj+mi \end{eqnarray*}$ von der kleinsten Zahl sprechen kannst, denn das ist, wie du sagst, eine parametisierte Darstellung, ergibt hier also verschiedene Zahlen.

Was mich dann aber natürlich stutzig werden lässt, ist, dass du sagst, dass $\begin{eqnarray*} k = z5+mi-10 \end{eqnarray*}$ die nächst kleinere Zahl in der Restklasse ist. Das wäre aber nun meiner Ansicht nach in der Restklasse die gleiche Zahl, denn Modulo 10 spielt die -10 ja keine Rolle.

Ich denke ich liege hier irgendeinem ziemlich blöden Fehler auf. Hoffe den klären zu können, damit ich das ganze dann auch mal verstehe Hammer

25.08.2008, 13:50

Mathespezialschüler

Auf diesen Beitrag antworten »

Nur ein kurzes Einmischen, um dir den grundlegenden Fehler darzulegen, auf dem fast alle deine anderen Verständnisprobleme beruhen.

Zitat:

Original von aRo
Also mit $\begin{eqnarray*} [k] \end{eqnarray*}$ bezeichnest du einfach alle Restklassen modulo $\begin{eqnarray*} ij \end{eqnarray*}$ , um mal bei unserem Beispiel (i=2, j=5) zu bleiben, wäre also $\begin{eqnarray*} [k] = \{0,1,2,3,4,5,6,7,8,9\} \end{eqnarray*}$ .

Nein. Lies nochmal die Definition. $\begin{eqnarray*} [k] \end{eqnarray*}$ ist einfach die Restklasse modulo $\begin{eqnarray*} ij \end{eqnarray*}$ , die von $\begin{eqnarray*} k \end{eqnarray*}$ erzeugt wird. Beispiel für $\begin{eqnarray*} i=2,j=5 \end{eqnarray*}$ :

$\begin{eqnarray*} [3]=\{\ldots,-17,-7,3,13,\ldots\} \end{eqnarray*}$ .

25.08.2008, 18:30

Auf diesen Beitrag antworten »

Genauso meine ich es - steht übrigen extra nochmal da in der Zeile $\begin{eqnarray*} [k]:= \ldots \end{eqnarray*}$

Zitat:

Original von aRo
Wenn ich dich bis hierhin nämlich richtig verstanden habe, dann ist die kleinste Zahl in $\begin{eqnarray*} [z5+m2] \end{eqnarray*}$ die 0, und das ist sie für alle i und j.

Nein, vollkommen falsch verstanden. Bei dieser Betrachtung sind nicht nur $\begin{eqnarray*} i,j \end{eqnarray*}$ fest (die sowieso), sondern auch $\begin{eqnarray*} z,m \end{eqnarray*}$ .

Beispiel $\begin{eqnarray*} i=2,j=5 \end{eqnarray*}$ , zusätzlich $\begin{eqnarray*} z=1,m=3 \end{eqnarray*}$ , dann ist

$\begin{eqnarray*} [zj+mi] = [1\cdot 5+3\cdot 2] = [11] = [1] = \{ \ldots, -19, -9, 1, 11, 21, \ldots\} \end{eqnarray*}$

Und innerhalb (!) dieser Restklasse ist tatsächlich die 11 selbst die kleinste ganze Zahl, die so darstellbar ist - für die 1 klappt das nämlich noch nicht!

09.09.2008, 16:29

aRo

Auf diesen Beitrag antworten »

hallo!

Tut mir leid, dass ihr wiederholt so lange auf eine Reaktion von mir warten musstet. Ich hoffe ich kann jetzt mal öfter hier vorbei schauen smile

Ok, dann fahren wir jetzt mit der richtigen Definition fort (ich habe diese wohl missverstanden, weil mich das "modulo ij" direkt nach der Definition irritiert hat und ich glaubte mit der nun richtigen Definition, die ich in Betracht zog, später auf einen Widerspruch zu stoßen, den ich jetzt merkwürdigerweise nicht mehr finde Augenzwinkern

).

Hm..das hat mich jetzt natürlich schon ein Stück nach vorne gebracht, aber noch immer habe ich Verständnisschwierigkeiten, ich glaube vor allem auch damit, inwiefern das jetzt wirklich unsere Frage löst.

Vielleicht nochmal zur Klarheit:
Arthur sagte "... $\begin{eqnarray*} zj+mi \end{eqnarray*}$ ist die kleinste ganze Zahl in der Restklasse $\begin{eqnarray*} [zj+mi] \end{eqnarray*}$ , die sich sich mit nichtnegativen Vorfaktoren vor $\begin{eqnarray*} j,i \end{eqnarray*}$ darstellen lässt."

Hmm...naja also meiner Meinung nach, ist es die kleinste positive Zahl für die das gilt. Denn in deinem letztem Beispiel kann ich auch die -9 so darstellen:
$\begin{eqnarray*} -9 = 1 \cdot 5 + 3 \cdot 2 - 2 \cdot 2 \cdot 5 \end{eqnarray*}$

Aber ich nehme mal an, dass du das so meinst, denn die negativen Zahlen sind für uns ja sowieso uninteressant, nicht wahr?

Aber wieso genau löst dieser Ansatz über die Restklassen nun unser Problem? Gut, ich kenne die insgesamt größte positive Zahl aller Restklassen, die sich nicht mit nichtnegativen Vorfaktoren darstellen lässt.
Aber was genau bringen mir diese Restklassen hier? Wir übertrage ich das jetzt auf unser Problem, wo wir ja in dem Sinne keine Restklassen betrachten und nicht mit $\begin{eqnarray*} i \cdot j \end{eqnarray*}$ arbeiten können.
Ich verstehe das Konzept irgendwie nicht verwirrt

Ist es möglich das ganze einmal an einem Beispiel durchzuarbeiten?

Ich hoffe ich konnte mich verständlich ausdrücken, irgendwie ist in meinem Kopf etwas Chaos, merkt man vielleicht smile

09.09.2008, 16:36

Auf diesen Beitrag antworten »

Zitat:

Original von aRo
Aber ich nehme mal an, dass du das so meinst, denn die negativen Zahlen sind für uns ja sowieso uninteressant, nicht wahr?

Ich denke, darum geht es? Du stellst jetzt Selbstverständlichkeiten des Problems in Frage.

Zitat:

Original von aRo
Gut, ich kenne die insgesamt größte positive Zahl aller Restklassen, die sich nicht mit nichtnegativen Vorfaktoren darstellen lässt.

Logisch denken: Alle Zahlen, die größer sind, lassen sich also im Umkehrschluss in genau einer solchen Weise darstellen! Und ein solche untere Schranke $\begin{eqnarray*} k_0 \end{eqnarray*}$ hast du doch oben im Eröffnungsbeitrag gesucht!

Zitat:

Original von aRo
ich glaube vor allem auch damit, inwiefern das jetzt wirklich unsere Frage löst.

Das ist wirklich der Hammer: Es liegt eine punktgenaue Lösung für dein Problem vor: Nicht nur irgendeine untere Schranke $\begin{eqnarray*} k_0 \end{eqnarray*}$ , sondern die kleinstmögliche untere Schranke, und du schreibst sowas - vielen Dank. böse

09.09.2008, 18:31

aRo

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Original von aRo
ich glaube vor allem auch damit, inwiefern das jetzt wirklich unsere Frage löst.

Da frage ich mich doch jetzt in welchen falschen Hals du das bekommen hast. Es mag sein, dass die Lösung punktgenau ist, aber ich habe halt damit noch Verständnisschwierigkeiten, wie ich schrieb. Wo da jetzt der Hammer ist und wieso man sich darüber aufregen muss, weiß ich nicht.
Es ist nicht so, dass ich darüber nicht nachgedacht hätte und einfach nur dumm rumfrage - ok?

Ich bedanke mich für deine Mühe, aber anscheinend verstehe ich das hier nicht und stoße bei Dir dabei auf Ungeduld.
So macht es uns doch beiden keinen Spaß, vielleicht sollten wir diesen Thread daher ruhen lassen.

09.09.2008, 19:50

Auf diesen Beitrag antworten »

Zitat:

Original von aRo
So macht es uns doch beiden keinen Spaß, vielleicht sollten wir diesen Thread daher ruhen lassen.

Da kann ich dann wieder zustimmen: Eine echte Unterhaltung kommt nämlich auch nicht zustande, wenn der eine zeitnah antwortet, und der andere nach jeweils zwei Wochen immer nur sagt: "Ich verstehe nicht" - trotz relativ ausführlicher Darlegung.

Neue Frage »

Antworten »

Jede Zahl als Summe 2er teilerfr. Zahlen

Verwandte Themen