Zahlentheoretisches Lemma

22.04.2011, 20:40

Airblader

Zahlentheoretisches Lemma

Ausgerechnet bei einer "kleinen Hilfsaussage" bleibe ich gerade ein wenig stecken. Vielleicht kann ja jemand meinen Hirnknoten beseitigen. smile

Zuerstmal das Lemma + den Beweis, den ich nachzuvollziehen versuche:

Zitat:

Lemma: Ist d der ggT von Zahlen $\begin{eqnarray*} n_1, n_2, \ldots \in \mathbb N \end{eqnarray*}$ , so gibt es Zahlen K und L derart, dass sich jedes $\begin{eqnarray*} ld \end{eqnarray*}$ mit $\begin{eqnarray*} l \geq L \end{eqnarray*}$ als Summe der Form
$\begin{eqnarray*} ld = \sum_{k=1}^K c_kn_k \end{eqnarray*}$
schreiben lässt.

Beweis: Wir können d=1 annehmen, und d ist der ggT einer endlichen Teilfolge $\begin{eqnarray*} n_1, \ldots, n_K \end{eqnarray*}$ . Nach dem Lemma von Bèzout gibt es ganze Zahlen $\begin{eqnarray*} a_1, \ldots, a_K \end{eqnarray*}$ mit $\begin{eqnarray*} a_1n_1 + \ldots + a_Kn_K = 1 \end{eqnarray*}$ .

Ist $\begin{eqnarray*} a = \operatorname{max}\{|a_1|, \ldots, |a_K|\} \end{eqnarray*}$ und $\begin{eqnarray*} L = an_1(n_1 + \ldots + n_K) \end{eqnarray*}$ , so lässt sich jedes $\begin{eqnarray*} l \geq L \end{eqnarray*}$ in der Form

$\begin{eqnarray*} l = an_1(n_1 + \ldots + n_K) + in_1 + r(an_1 + \ldots + a_Kn_K) \end{eqnarray*}$

schreiben. Durch Umsortieren erhält man die gewünsche Form.

Ich habe zwei Fragen:

1) Woher kommt der Summand $\begin{eqnarray*} in_1 \end{eqnarray*}$ in der letzten Gleichung? Der Faktor bei dem r ist doch einfach d, also 1. Der erste große Summand ist L. Ich kann jedes $\begin{eqnarray*} l \geq L \end{eqnarray*}$ doch bereits als $\begin{eqnarray*} l = L + r \cdot 1 \end{eqnarray*}$ schreiben, wozu muss man diesen Extra-Summanden einschieben? Edit: Ohje. Hängt mich nicht, aber ich glaube diese eine Frage konnte ich mir beantworten. Darunter steht noch $\begin{eqnarray*} 0 \leq r < n_1 \end{eqnarray*}$ .. und um diese Eingrenzung zu wahren fügt man den Term $\begin{eqnarray*} in_1 \end{eqnarray*}$ als "Puffer" ein. Hammer

2) Wieso genügt die Einschränkung auf d=1? Meine Idee ist, dass man notfalls alle n_k durch d teilt. So erhält man eine neue Folge, die nun den ggT 1 hat, wendet obige Argumentation an und multipliziert die letzte Gleichung wieder mit d durch. Liege ich damit richtig?

Vielen Dank schonmal Wink

air

Neue Frage »

Antworten »

Zahlentheoretisches Lemma

Verwandte Themen