ggT(2^m-1,2^n-1)=1 <==> ggT(m,n=1)

14.03.2021, 14:58	weierstrass	Auf diesen Beitrag antworten »
ggT(2^m-1,2^n-1)=1 <==> ggT(m,n=1) Meine Frage: Hallo, ich sollte die im Titel ersichtliche Äquivalenz zeigen. Hat jemand einen Tipp für die Richtung ggT(n,m)=1 ==> ggT(2^n-1,2^m-1)=1? Vielen Dank schonmal! Meine Ideen: Ich habe auch schon mithilfe der Summendarstellung eine Implikation gezeigt: nämlich ggT(2^m-1,2^n-1)=1 impliziert ggT(n,m)=1 durch Kontraposition. Komme aber nicht drauf, die zweite Implikation zu zeigen.
14.03.2021, 15:39	HAL 9000	Auf diesen Beitrag antworten »
Man kann sogar die allgemeinere Behauptung $\begin{eqnarray} \operatorname{ggT}\left(a^n-1,a^m-1\right) = a^{\operatorname{ggT}(n,m)}-1 \end{eqnarray}$ gültig für alle ganzen Zahlen $\begin{eqnarray} a\geq 2,m\geq 0,n\geq 0 \end{eqnarray}$ zeigen, z.B. indirekt: Es reicht der Symmetrie wegen, die Behauptung für $\begin{eqnarray} n\geq m\geq 0 \end{eqnarray}$ zu zeigen. Für $\begin{eqnarray} m=0 \end{eqnarray}$ sowie $\begin{eqnarray} n=m \end{eqnarray}$ gilt die Behauptung offensichtlich. Und die Annahme, dass es ein Gegenbeispiel $\begin{eqnarray} (n,m) \end{eqnarray}$ mit $\begin{eqnarray} 0<m<n \end{eqnarray}$ gibt, führt zu einem Widerspruch. EDIT: Man kann das ganze auch als Induktionsbeweis organisieren, und zwar über die Variable $\begin{eqnarray} k:=\max(m,n) \end{eqnarray}$ . Dabei ist Induktionsanfang $\begin{eqnarray} k=0 \end{eqnarray}$ trivial. Der Induktionsschritt $\begin{eqnarray} (<k)\to k \end{eqnarray}$ ist dann für alle $\begin{eqnarray} k\geq 1 \end{eqnarray}$ auszuführen. P.S.: Die Eigenschaft $\begin{eqnarray} \operatorname{ggT}\left(b_n,b_m\right) = \left\| b_{\operatorname{ggT}(m,n)}\right\| \end{eqnarray}$ gilt interessanterweise für ALLE (!) Lucasfolgen $\begin{eqnarray} b_n = ub_{n-1} + vb_{n-2} \end{eqnarray}$ mit Startwerten $\begin{eqnarray} b_0=0 \end{eqnarray}$ und $\begin{eqnarray} b_1\in\mathbb{Z} \end{eqnarray}$ , wobei die Parameter $\begin{eqnarray} u,v \end{eqnarray}$ teilerfremde ganze Zahlen sind. Ein paar Beispiele: 1) $\begin{eqnarray} u=a+1,v=-a \end{eqnarray}$ für $\begin{eqnarray} a\in\mathbb{Z}\setminus\{1\} \end{eqnarray}$ ergibt $\begin{eqnarray} b_n=b_1\frac{a^n-1}{a-1} \end{eqnarray}$ , was mit $\begin{eqnarray} b_1=a-1 \end{eqnarray}$ der obigen Folge entspricht. 2) $\begin{eqnarray} u=2,v=-1 \end{eqnarray}$ ergibt $\begin{eqnarray} b_n=nb_1 \end{eqnarray}$ , da ist die Erfüllung dieser Eigenschaft keine Überraschung. 3) $\begin{eqnarray} b_1=1,u=1,v=1 \end{eqnarray}$ ergibt die Fibonacci-Folge.

1

Verwandte Themen