Zerlegung von natürlichen Zahlen in bestimmte Summanden

22.12.2016, 12:47	Shakatir	Auf diesen Beitrag antworten »
Zerlegung von natürlichen Zahlen in bestimmte Summanden Das Problem: Sei eine nicht-leere, endliche Menge $\begin{eqnarray} M \subseteq \mathbb{N} \end{eqnarray}$ gegeben und sei $\begin{eqnarray} b = \text{ggT}(M). \end{eqnarray}$ Gesucht ist nun eine Zahl $\begin{eqnarray} N \in \mathbb{N} \end{eqnarray}$ , sodass jede durch $\begin{eqnarray} b \end{eqnarray}$ teilbare Zahl $\begin{eqnarray} k > N \end{eqnarray}$ als Summe der Zahlen in $\begin{eqnarray} M \end{eqnarray}$ dargestellt werden kann. Das heißt für $\begin{eqnarray} M = \lbrace m_1, \ldots, m_n \rbrace \end{eqnarray}$ gibt es $\begin{eqnarray} z_1, \ldots, z_n \in \mathbb{N}_0 \end{eqnarray}$ , sodass $\begin{eqnarray} k = \sum_{i=1}^n z_i m_i \end{eqnarray}$ ist. Es ist nicht nötig, $\begin{eqnarray} N \end{eqnarray}$ explizit zu berechnen. Es reicht, zu zeigen, dass eine solche Zahl existiert. Auf der Suche nach einer Lösung konnte ich zeigen, dass das Problem zum Spezialfall $\begin{eqnarray} b = 1 \end{eqnarray}$ äquivalent ist. Ich habe für verschiedene Zahlen (z. B. das Produkt aller Zahlen oder die Fakultät davon), von denen anzunehmen ist, dass sie groß genug sein müssten, versucht, die Zerlegbarkeit von $\begin{eqnarray} k, k + 1, \ldots, k + m_i - 1 \end{eqnarray}$ für ein $\begin{eqnarray} i \in \lbrace 1, \ldots, n \rbrace \end{eqnarray}$ zu zeigen, was als Beweis ausreichen würde, aber ich habe es noch nicht geschafft den richtigen Ansatz zu finden. Hat jemand eine Idee? Mein Gefühl sagt mir, dass der Beweis dazu eigentlich recht einfach sein sollte.
22.12.2016, 15:42	HAL 9000	Auf diesen Beitrag antworten »
Weise die Aussage zunächst für $\begin{align} n=2 \end{align}$ nach. Für allgemeine $\begin{align} n \end{align}$ beweist man das ganze dann durch Vollständige Induktion über $\begin{align} n \end{align}$ , wobei der Induktionsschritt $\begin{align} n\to n+1 \end{align}$ im wesentlichen $\begin{align} \operatorname{ggT}\left(m_1,\ldots,m_{n+1}\right) = \operatorname{ggT}\left(\operatorname{ggT}\left(m_1,\ldots,m_n\right),m_{n+1}\right) \end{align}$ nutzt, was die Sache dann nämlich auf die Induktionsvoraussetzung sowie eben jenen Fall $\begin{align} n=2 \end{align}$ zurückführt.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »