Beweis, dass jedes n > 7 in der Form n = 3a+5b darstellbar ist

Question

Aufgabe:

c) Zeigen Sie, dass sich jede natürliche Zahl $n>7$ mit geeigneten $a, b \in \mathbb{N}_{0}$ in der Form $n=3 a+5 b$ darstellen lässt.

Problem/Ansatz:

ich weiß leider nicht genau wie man diese Aussage am besten beweisen könnte.

Man könnte sich aber beliebige n > 7 nehmen um herauszufinden, dass die Aussage gilt.

So gilt zum Beispiel für n = 8 folgendes:

8 = 3a + 5b        mit a=6 und b=-2

Für n = 14 gilt dagegen:

14 = 3a + 5b     mit a=-2 und b=4

Ich befürchte aber, dass das nicht Beweis genug ist, da ich es nicht für alle n > 7 beweise.

Ich freue mich über eure Hilfe.

Answer 1

.. noch 'ne Antwort ;-)

wenn man sich über den erweitereten Euklidischen Algorithmus eine Linearkombination bestimmt, für die $3a+5b=1$ ist, dann kommt man durch Multiplikation mit $n$ zu einem beliebigen Wert. Weiter kann man durch Addition von 'Null' die Koeffizienten $a$ und $b$ variieren. Formal sieht das so aus:$$\begin{aligned} 3\cdot (2) + 5 \cdot (-1) &= 1 && \left|\, \cdot n \right.\\ 3\cdot (2n) + 5 \cdot (-n) &= n && \left|\, + 0 = 3\cdot (-5k) + 5 \cdot (3k)\right. \\ 3\cdot (\underbrace{2n-5k}_{a}) + 5 \cdot (\underbrace{3k-n}_{b}) &= n \end{aligned}$$ $a$ und $b$ sind jetzt genau dann $\ge 0$ und damit $\in \mathbb{N}_0$ wenn$$2n - 5k \ge 0 \space \land \space 3k-n \ge 0\\ \implies \frac 13 n \le\, k \le \frac 25 n \quad k \in \mathbb{N}_0$$Das kann man sich auch graphisch veranschaulichen

Plotlux öffnen

f₁(x) = x/3f₂(x) = 2x/5P(3|1)Zoom: x(-1…13) y(-1…6)P(5|2)P(6|2)P(8|3)P(9|3)P(10|4)P(11|4)

Die horizontale Achse sind die Werte von $n$ und auf der vertikalen kann man das $k$ ablesen. Für obige Bedingung muss $k$ zwischen den  beiden Geraden liegen. Wie man sieht, ist das z.B. für die Trivialfälle $n=3$ und $n=5$ gegeben. Aber für $n=4$ und $n=7$ gibt es kein ganzzahliges $k$ welches diese Bedingung erfüllt.

Die Bedingung ist immer erfüllt, wenn der Abstand der Geraden $\ge 1$ ist. Also wenn gilt$$\begin{aligned} \frac 25 n - \frac 13 n &\ge 1 \\ 6n - 5n & \ge 15 \\ n &\ge 15\end{aligned}$$Wir müssen also nur die Fälle $n=8$ bis $n=14$ näher untersuchen. Dazu eine kleine Tabelle $a=2n-5k, \quad b=3k-n$:$$\begin{array}{rc|rr}n& k=\lfloor \frac 25 n\rfloor& a& b\\ \hline 8& 3& 1& 1\\ 9& 3& 3& 0\\ 10& 4& 0& 2\\ 11& 4& 2& 1\\ 12& 4& 4& 0\\ 13& 5& 1& 2\\ 14& 5& 3& 1\end{array}$$Man sieht, dass in jeden Fall ein ganzzahliges $k$ existiert mit $a,b \in \mathbb{N}_0$. Womit bewiesen wäre, dass für jede natürliche Zahl $n \gt 7$ die oben geforderte Darstellung $3a+5b=n$ möglich ist.

Comments

vielen Dank für deine Hilfe.

Das ganze scheint mir nachvollziehbar, ich wüsste aber nicht wie ich je darauf hätte kommen sollen...

Answer 2

das kannst du per Induktion zeigen.

Induktionsanfang:

zeige, dass sich alle Zahlen von 7 bis 15 in obiger Form darstellen lassen.

Dann Induktionsschritt: n---->n+8

n+8=(3a+5b)+8=3a+5b+3+5=3(a+1)+5(b+1)

Comments

Du meinst sicherlich von 8 bis 15.

Answer 3

8 = 3a + 5b        mit a=6 und b=-2

Es soll b ∈ ℕ₀ sein. Allerdings ist -2 ∉ ℕ₀.

Wenn

        n = 3a + 5b

ist, dann ist

        n+1 = 3(a+2) + 5(b-1)

        n+2 = 3(a-1) + 5(b+1)

        n+3 = 3(a+1) + 5b

        n+4 = 3(a+3) + 5(b-1)

        n+5 = 3a + 5(b+1)

        n+6 = 3(a+2) + 5b

        n+7 = 3(a+4) + 5(b-1)

        n+8 = 3(a+1) + 5(b+1)

Comments

Den Beweis kann ich sehr gut nachvollziehen.

Danke für deine Hilfe.

---

Bei n+2 und n+7 haben sich Fehler eingeschlichen.

n+2=3a+5b+5-3=3(a-1)+5(b+1)

n+7=3a+5b-3+5·2=3(a-1)+5(b+2)

---

Hast recht. Danke für den Hinweis.

---

Bei n+2 und n+7 haben sich Fehler eingeschlichen.

Die habe ich mittlerweile korrigiert.

Den Beweis kann ich sehr gut nachvollziehen.

So ganz fertig ist der Beweis ja noch nicht.

Warum habe ich denn bei der Aufzählung gerade bei n+8 aufgehört?

Und wie ist dafür gesorgt, dass die Faktoren, mit denen 3 und 5 multipliziert werden, nicht negativ werden?

---

8=3+5

Die oswald'sche Reihe gilt dann bis 16.

Dann setzen wir n=16 usw.

Da für n=8 gilt a=1 und b=1 und als kleinste Faktoren a-1 und b-1 vorkommen, ist der kleinste Faktor 0, also nicht negativ.

Für n=16 und größere Werte, werden die Faktoren größer, also auch nicht negativ.

Answer 4

Hallo

 wen du direkt zeigst, dass man 8,9,10 erzeugen kann, dann durch Addition  zu diesen durch n*3+m*5 jede weitere Zahl erreichen kannst,  denn du kannst die 1, 2, 3 größeren Zahlen erreichen durch Addition einer 3 zu einem der Zahlen , ebenso die nächsten 3 usw.

Wenn du lieber die 5 er verwendest erzeuge erst 8 bis 12 . (natürlich kann man viele Zahlen mit verschiedenen Kombinationen erreichen 13=10+3=8+5 : 15=3*5=  5*3 usw.

Gruß lul

Answer 5

Eigentlich brauchst du nur zeigen, dass du die Zahlen 8, 9 und 10 darstellen kannst. Denn jede weitere Zahl lässt sich dann durch addition eines vielfachen von 3 zu einer der ersten Zahlen darstellen.

8 = 3*1 + 5*1

9 = 3*3 + 5*0

10 = 3*0 + 5*2

11 = 8 + 3 = 3*1 + 5*1 + 3 = 3*2 + 5*1

12 = 9 + 3 = 3*3 + 5*0 + 3 = 3*4 + 5*0

etc.

Verstehst du das?

Comments

Ja, ich hab es soweit verstanden.

Vielen Dank!