Beweis mit ggT

11.11.2009, 21:53

Lea

Beweis mit ggT

Hallo
Ich habe ein Problem mit folgender Aufgabe:
Es seien $\begin{eqnarray*} m,n,a \in \mathbb N, a>1 \end{eqnarray*}$ . Beweise:
$\begin{eqnarray*} ggT(a^m-1,a^n-1)=a^{ggT(m,n)}-1 \end{eqnarray*}$
Ich bin bisher soweit:
$\begin{eqnarray*} ggT(a^m-1,a^n-1)=x(a^m-1)-y(a^n-1) \end{eqnarray*}$ mit $\begin{eqnarray*} x,y \in \mathbb N \end{eqnarray*}$
$\begin{eqnarray*} x(a^m-1)-y(a^n-1)=xa^m-x-ya^n+y=xa^m-ya^n-x+y=ggT(a^m,a^n)-x+y \end{eqnarray*}$
Nur an dieser Stelle komme ich irgendwie nicht weiter. Kann mir jemand einen Tipp geben, evt. ein nächster sinnvoller Schritt wäre? Oder habe ich bis dahin schon etwas falsch gemacht. Bin für jede Hilfe sehr dankbar.

11.11.2009, 22:10

Auf diesen Beitrag antworten »

Es reicht ja, das für o.B.d.A. $\begin{eqnarray*} n\geq m \end{eqnarray*}$ zu beweisen. Nun ist

$\begin{eqnarray*} \operatorname{ggT}(a^m-1,a^n-1) = \operatorname{ggT}(a^m-1,a^n-1-a^{n-m}(a^m-1)) = \operatorname{ggT}(a^m-1,a^{n-m}-1) \end{eqnarray*}$ .

Das kann man z.B. als entscheidendes Argument in einem Induktionsbeweis nutzen...

12.11.2009, 23:05

Lea

Auf diesen Beitrag antworten »

Vielen Dank für den Tipp. Dieser Ausdruck ist mir klar. Habe aber ein Problem wie ich das mit einem Induktionsbeweis nachweisen kann, bzw. nach welcher Variable ich induzieren soll. Mein Problem ist, dass ich hier 2 Variablen habe: m und n.

12.11.2009, 23:18

Auf diesen Beitrag antworten »

Vielleicht besser doch kein Induktionsbeweis, da viele Leute (vielleicht auch du?) ziemliche Verständnisprobleme mit Induktionsschritten der Form $\begin{eqnarray*} (<n)\to n \end{eqnarray*}$ haben.

Man kann das ganze auch völlig gleichwertig als indirekten Beweis führen: Zunächst mal reicht es aus, das ganze für o.B.d.A. $\begin{eqnarray*} n\geq m \end{eqnarray*}$ zu zeigen (s.o.). Für beliebige $\begin{eqnarray*} n \end{eqnarray*}$ ist die Aussage im Fall $\begin{eqnarray*} m=0 \end{eqnarray*}$ sowie auch im Fall $\begin{eqnarray*} m=n \end{eqnarray*}$ sicher richtig. Angenommen, die Aussage gilt nicht für alle $\begin{eqnarray*} n\geq m \end{eqnarray*}$ , dann existiert ein kleinstes $\begin{eqnarray*} n_0 \end{eqnarray*}$ sowie ein zugehöriges $\begin{eqnarray*} m_0 \end{eqnarray*}$ mit

$\begin{eqnarray*} \operatorname{ggT}(a^{m_0}-1,a^{n_0}-1) \neq a^{\operatorname{ggT}(m_0,n_0)}-1 \end{eqnarray*}$ .

Offenbar muss $\begin{eqnarray*} n_0 > m_0 \geq 1 \end{eqnarray*}$ gelten. Mit Hilfe der Rechnung in meinem vorigen Beitrag lässt sich nun leicht ein Widerspruch zur vorausgesetzten Minimalität von $\begin{eqnarray*} n_0 \end{eqnarray*}$ konstruieren.

13.11.2009, 11:16

Lea

Auf diesen Beitrag antworten »

Also ich habe noch ein paar Fragen dazu: Warum reicht es eigentlich aus das für $\begin{eqnarray*} n\geq m \end{eqnarray*}$ zu zeigen?

Zitat:

Original von Arthur Dent
Mit Hilfe der Rechnung in meinem vorigen Beitrag lässt sich nun leicht ein Widerspruch zur vorausgesetzten Minimalität von $\begin{eqnarray*} n_0 \end{eqnarray*}$ konstruieren.

Das heißt ich hätte dann
$\begin{eqnarray*} \operatorname{ggT}(a^{m_0}-1,a^{n_0}-1) = \operatorname{ggT}(a^{m_0-1},a^{n_0-m_0}-1) \end{eqnarray*}$ .Mir ist nur jetzt garnicht klar wie ich hieraus einen Widerspruch zur Minimalität von $\begin{eqnarray*} n_0 \end{eqnarray*}$ konstruieren kann.

13.11.2009, 11:29

Auf diesen Beitrag antworten »

Zitat:

Original von Lea
Also ich habe noch ein paar Fragen dazu: Warum reicht es eigentlich aus das für $\begin{eqnarray*} n\geq m \end{eqnarray*}$ zu zeigen?

Ist die Behauptung bzgl. $\begin{eqnarray*} m \leftrightarrow n \end{eqnarray*}$ symmetrisch, oder ist sie es nicht? Bitte nachdenken vor solchen Nachfragen.

Zitat:

Original von Lea
Das heißt ich hätte dann
$\begin{eqnarray*} \operatorname{ggT}(a^{m_0}-1,a^{n_0}-1) = \operatorname{ggT}(a^{m_0-1},a^{n_0-m_0}-1) \end{eqnarray*}$ . Mir ist nur jetzt garnicht klar wie ich hieraus einen Widerspruch zur Minimalität von $\begin{eqnarray*} n_0 \end{eqnarray*}$ konstruieren kann.

Schade, dabei ist es nach der Vorarbeit doch nur noch ein winziger Schritt:

Aus $\begin{eqnarray*} \operatorname{ggT}(m_0,n_0) = \operatorname{ggT}(m_0,n_0-m_0) \end{eqnarray*}$ folgt ja außerdem $\begin{eqnarray*} a^{\operatorname{ggT}(m_0,n_0)}-1 = a^{\operatorname{ggT}(m_0,n_0-m_0)}-1 \end{eqnarray*}$ , so dass man insgesamt zu

$\begin{eqnarray*} \operatorname{ggT}(a^{m_0}-1,a^{n_0-m_0}-1) \neq a^{\operatorname{ggT}(m_0,n_0-m_0)}-1 \end{eqnarray*}$

kommt. Damit hätten wir aber mit $\begin{eqnarray*} n_0' := \max(n_0-m_0,m_0) \end{eqnarray*}$ (bei zugehörigem $\begin{eqnarray*} m_0' := \min(n_0-m_0,m_0) \end{eqnarray*}$ ) einen kleineren Wert als $\begin{eqnarray*} n_0 \end{eqnarray*}$ gefunden, wo die Behauptung nicht gilt - Widerspruch zur vorausgesetzten Minimalität von $\begin{eqnarray*} n_0 \end{eqnarray*}$ .

13.11.2009, 12:57

Lea

Auf diesen Beitrag antworten »

Danke für die Hilfe. Mir war nicht klar, dass ich aus

$\begin{eqnarray*} \operatorname{ggT}(a^{m_0}-1,a^{n_0}-1) = \operatorname{ggT}(a^{m_0}-1,a^{n_0-m_0}-1) \end{eqnarray*}$ folgern kann, dass
$\begin{eqnarray*} \operatorname{ggT}(m_0,n_0) = \operatorname{ggT}(m_0,n_0-m_0) \end{eqnarray*}$
Habe nur noch ein Frage, die mir fast schon ein bisschen peinlich ist:
Habe als ich mir die Aufgabe im gesamten noch mal durchgeschaut habe gemerkt, dass ich diesen Schritt doch nicht so ganz verstehe:
$\begin{eqnarray*} \operatorname{ggT}(a^m-1,a^n-1) = \operatorname{ggT}(a^m-1,a^n-1-a^{n-m}(a^m-1)) \end{eqnarray*}$
Mir fehlt irgendwie die Begründung, warum hier der ggT gleich ist.

13.11.2009, 13:00

Auf diesen Beitrag antworten »

Zitat:

Original von Lea
Danke für die Hilfe. Mir war nicht klar, dass ich aus

$\begin{eqnarray*} \operatorname{ggT}(a^{m_0}-1,a^{n_0}-1) = \operatorname{ggT}(a^{m_0}-1,a^{n_0-m_0}-1) \end{eqnarray*}$ folgern kann, dass
$\begin{eqnarray*} \operatorname{ggT}(m_0,n_0) = \operatorname{ggT}(m_0,n_0-m_0) \end{eqnarray*}$

Kann man auch nicht. Lies doch bitte mal gründlich! unglücklich

Wenn ich etwas nicht ausstehen kann, dann ist es die logische Verdrehung meiner Worte. Forum Kloppe

Zitat:

Original von Lea
Habe als ich mir die Aufgabe im gesamten noch mal durchgeschaut habe gemerkt, dass ich diesen Schritt doch nicht so ganz verstehe:
$\begin{eqnarray*} \operatorname{ggT}(a^m-1,a^n-1) = \operatorname{ggT}(a^m-1,a^n-1-a^{n-m}(a^m-1)) \end{eqnarray*}$
Mir fehlt irgendwie die Begründung, warum hier der ggT gleich ist.

Gewisse Grundeigenschaften des $\begin{eqnarray*} \operatorname{ggT} \end{eqnarray*}$ sollte man schon kennen bzw. sie sich zumindest klarmachen können:

So gilt etwa $\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}(a,b-ka) \end{eqnarray*}$ für beliebige ganze Zahlen $\begin{eqnarray*} a,b,k \end{eqnarray*}$ , ohne jede Einschränkung. Diese Eigenschaft ist immerhin die Grundlage des Euklidischen Algorithmus.

13.11.2009, 13:24

Lea

Auf diesen Beitrag antworten »

Tut mir Leid, wenn das so rüberkam.Ich wollte deine Worte nicht verdrehen, aber ich konnte mir sonst nicht erklären wo
$\begin{eqnarray*} \operatorname{ggT}(m_0,n_0) = \operatorname{ggT}(m_0,n_0-m_0) \end{eqnarray*}$ herkommt. und dachte es käme hierher, was ja anscheinend falsch war.

13.11.2009, 13:30

Auf diesen Beitrag antworten »

Das ist z.B. auch eine Anwendung der letztgenannten Eigenschaft $\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}(a,b-ka) \end{eqnarray*}$ , und zwar mit $\begin{eqnarray*} a=n_0,b=m_0,k=1 \end{eqnarray*}$ .

13.11.2009, 13:38

Lea

Auf diesen Beitrag antworten »

Achso ja dann ist es klar. Diese Aussage hat mir einfach gefehlt und ich kam nicht darauf. Vielen Dank für die ausführliche Hilfe.

13.11.2009, 14:46

Mystic

Auf diesen Beitrag antworten »

Ich bin mir jetzt nicht sicher, ob Arthur da zustimmen wird, aber m.E. gibt es auch eine "think big"-Variante seiner Idee, indem man sich nämlich überlegt, dass jede Zeile

$\begin{eqnarray*} r_{i-1} =q_ir_i+r_{i+1} \text{ mit } 0 \le r_{i+1}<r_i,\quad i=0,1,...,s \end{eqnarray*}$

der sich "nicht ausgehenden Divisionen" beim Euklidischen Algorithmus (die nächste soll sich dann ausgehen), angewandt auf

$\begin{eqnarray*} r_{-1}:=m,\ r_0:=n \end{eqnarray*}$

genau einer Zeile

$\begin{eqnarray*} \underbrace{a^{r_{i-1}}-1}_{\tilde{r}_{i-1}} =\tilde{q}_i\underbrace{(a^{r_i}-1)}_{\tilde{r}_i}+\underbrace{(a^{r_{i+1}}-1)}_{\tilde{r}_{i+1}} \text{ mit } 0 \le \tilde{r}_{i+1}<\tilde{r}_{i},\quad i=0,1,...,s \end{eqnarray*}$

im Euklidischen Algorithmus, angewandt auf

$\begin{eqnarray*} \tilde{r}_{-1}:=a^m-1,\ \tilde{r}_0:=a^n-1 \end{eqnarray*}$

entspricht, wobei sich auch hier dann die nächste Division ausgeht...

13.11.2009, 20:17

Auf diesen Beitrag antworten »

Die Analogie ist mir durchaus bewusst, und so ist es vielleicht auch verständlicher. Augenzwinkern

Was ich oben bevorzugt habe, ist eine beweistechnisch saubere Variante, die ohne Analogiebetrachtungen zum euklidischen Algorithmus und ohne ein "und so weiter" auskommt - auch wenn die Hintergründe dadurch etwas verdeckt werden. Augenzwinkern

EDIT: Die Aufgabe könnte man folgendermaßen verallgemeinern:

Zitat:

Die Funktion $\begin{eqnarray*} f:\;\mathbb{N} \to \mathbb{Z} \end{eqnarray*}$ habe die Eigenschaften $\begin{eqnarray*} f(0) = 0 \end{eqnarray*}$ sowie $\begin{eqnarray*} \operatorname{ggT}(f(n),f(m)) = \operatorname{ggT}(f(n-m),f(m)) \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq m \end{eqnarray*}$ . Dann gilt auch

$\begin{eqnarray*} \operatorname{ggT}(f(n),f(m)) = f(\operatorname{ggT}(n,m)) \end{eqnarray*}$ für alle $\begin{eqnarray*} m,n\in \mathbb{N} \end{eqnarray*}$ .

Nun sollten Verallgemeinerungen auch Sinn machen, d.h. mehrere Anwendungsfälle haben: Neben der Funktion $\begin{eqnarray*} f(n)=a^n-1 \end{eqnarray*}$ hier im Thread ist diese Aussage z.B. auch auf die Fibonacci-Folge anwendbar. Augenzwinkern

15.11.2009, 09:21

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Nun sollten Verallgemeinerungen auch Sinn machen, d.h. mehrere Anwendungsfälle haben: Neben der Funktion $\begin{eqnarray*} f(n)=a^n-1 \end{eqnarray*}$ hier im Thread ist diese Aussage z.B. auch auf die Fibonacci-Folge anwendbar. Augenzwinkern

Wobei diese beiden Fälle jetzt nicht ganz so verschieden sind, wie es auf den ersten Blick scheint... Immerhin ordnen sich Fibonaccizahlen dem allgemeineren Fall der Lucasfolgen

$\begin{eqnarray*} U_n=\frac {\alpha^n-\beta^n}{\alpha-\beta},\quad n \in \mathbb N \end{eqnarray*}$

unter, wo $\begin{eqnarray*} \alpha \end{eqnarray*}$ und $\begin{eqnarray*} \beta \end{eqnarray*}$ die verschiedenen Nullstellen eines gewissen quadratischen Polynoms mit ganzen Koeffizienten sind...

Neue Frage »

Antworten »

Beweis mit ggT

Verwandte Themen