Größter gemeinsamer Teiler, Zusammenhänge beweisen

01.12.2015, 16:35	AmHa	Auf diesen Beitrag antworten »
Größter gemeinsamer Teiler, Zusammenhänge beweisen Meine Frage: Wir betrachten natürliche Zahlen a > 1 und n $\begin{eqnarray} \geq \end{eqnarray}$ m > 0. Zeige: 1. Genau dann ist $\begin{eqnarray} a^{m} \end{eqnarray}$ -1 ein Teiler von $\begin{eqnarray} a^{n} \end{eqnarray}$ -1, wenn m ein Teiler von n ist. 2. Ist ggT(n,m) = d, so gilt ggT( $\begin{eqnarray} a^{n} \end{eqnarray}$ -1, $\begin{eqnarray} a^{m} \end{eqnarray}$ -1) = $\begin{eqnarray} a^{d} \end{eqnarray}$ -1 Meine Ideen: Bei der 1. muss ich ja zwei Richtungen zeigen, allerdings habe ich weder bei 1. noch bei 2. eine genaue Idee, wie ich anfangen soll.
01.12.2015, 16:56	HAL 9000	Auf diesen Beitrag antworten »
1) folgt aus 2), also kann man auch gleich letzteres beweisen: Aus Symmetriegründen reicht es, das für o.B.d.A. $\begin{align} m\leq n \end{align}$ zu beweisen. Für $\begin{align} m=0 \end{align}$ und $\begin{align} m=n \end{align}$ ist die Behauptung richtig. Angenommen, die Behauptung ist falsch, dann betrachten wir unter all den Paaren $\begin{align} (m,n) \end{align}$ , für die die Behauptung falsch ist, eines mit minimalen $\begin{align} n \end{align}$ , für das zugehörige $\begin{align} m \end{align}$ gilt nach den Vorbetrachtungen $\begin{align} 0<m<n \end{align}$ . Dann gilt aber $\begin{align} a^{\operatorname{ggT}(m,n)}-1 \neq \operatorname{ggT}\left(a^m-1,a^n-1\right) \stackrel{()}{=} \operatorname{ggT}\left(a^m-1,a^n-1-a^{n-m}\left(a^m-1\right)\right) = \operatorname{ggT}\left(a^m-1,a^{n-m}-1\right) \stackrel{!}{=} a^{\operatorname{ggT}(m,n-m)}-1 = a^{\operatorname{ggT}(m,n)}-1 \end{align}$ , Widerspruch zur Annahme. Gleichung $\begin{align} \stackrel{!}{=} \end{align}$ gilt, weil $\begin{align} \max\{m,n-m\}\leq n-1 \end{align}$ und $\begin{align} n \end{align}$ ja als minimal vorausgesetzt wurde in Hinblick Nichtgültigkeit der Behauptung. P.S.: An Stelle () wurde die ggT-Eigenschaft $\begin{align} \operatorname{ggT}(u,v) = \operatorname{ggT}(u,v-ku) \end{align}$ genutzt, gültig für alle ganzen Zahlen $\begin{align} u,v,k \end{align}$ .
03.12.2015, 14:30	AmHa	Auf diesen Beitrag antworten »
Danke! dann schau ich mir mal die 1. damit an
03.12.2015, 16:49	AmHa	Auf diesen Beitrag antworten »
Ich habe mir für 1. schon mal eine Richtung überlegt: m teilt n heißt : es gibt ein k aus N mit n=km Dann gilt ( a^n - 1 ) = ( a^( km) - 1 ) = ( (a ^m )^ k - 1 ) = ( a^m - 1 ) * ( 1 + a^m + a^(2m) + .... + a^( (k-1)*m) ) . Und weil der erste Faktor durch a^m -1 teilbar ist, ist aus das ganze Produkt dadurch teilbar.. Für die andere Richtung habe ich leider Idee..

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »