Teilbarkeit durch 2^(n+1)

25.02.2017, 20:23

Koer

Auf diesen Beitrag antworten »

Teilbarkeit durch 2^(n+1)

Guten Tag,

ich soll beweisen, dass alle $\begin{eqnarray*} 3^{2^{n}}-1 \end{eqnarray*}$ durch $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ geteilt werden können (n ist Element der natürlichen Zahlen inkl. 0).
Hinweise: Induktion und $\begin{eqnarray*} a^{2}-b^{2} = (a-b)*(a+b) \end{eqnarray*}$

Also Induktionsanfang: Aussage stimmt für n=0 (2 kann durch 2 geteilt werden).
Induktionsvorraussetzung: $\begin{eqnarray*} 3^{2^{n}}-1 mod 2^{n+1} = 0 \end{eqnarray*}$
Induktionsschritt: nehmen wir n+1:
$\begin{eqnarray*} 3^{2^{n+1}}-1 mod 2^{n+2} = 0 \end{eqnarray*}$

Meine Ideen waren bis jetzt:
- $\begin{eqnarray*} a^{n^{m}} \end{eqnarray*}$ = $\begin{eqnarray*} a^{m^{n}} \end{eqnarray*}$ also Exponenten von dem linken Biest tauschen
- $\begin{eqnarray*} 1 = 1^{2} \end{eqnarray*}$
-und dann binomie rückwärts
hat auch soweit geklappt, dass ich jetzt folgendes habe, wo allerdings keiner der Faktoren durch das bereits bewiesene $\begin{eqnarray*} 2^{(n+1)} \end{eqnarray*}$ geteilt wird.

$\begin{eqnarray*} \frac{(3^{n+1}-1)*(3^{n+1}+1)}{2} mod 2^{n+1} = 0 \end{eqnarray*}$

Es bringt also nichts. Habt ihr eine Idee, wie man das lösen könnte?

Liebe Grüße

Koer

25.02.2017, 21:50

Elvis

Auf diesen Beitrag antworten »

Exponenten kann man nicht tauschen. Das linke Biest ist ein Quadrat: $\begin{eqnarray*} 3^{2^{n+1}}=(3^{2^n})^2 \end{eqnarray*}$

25.02.2017, 21:52

Leopold

Auf diesen Beitrag antworten »

RE: Teilbarkeit durch 2^(n+1)
Bitte halte dich an korrekte Schreibweisen. Wenn du schon die modulo-Schreibweise verwendest, dann so

$\begin{align*} 3^{2^n} - 1 \equiv 0 \pmod {2^{n+1}} \end{align*}$

Zitat:

Original von Koer
Meine Ideen waren bis jetzt:
- $\begin{eqnarray*} a^{n^{m}} \end{eqnarray*}$ = $\begin{eqnarray*} a^{m^{n}} \end{eqnarray*}$ also Exponenten von dem linken Biest tauschen

Exponenten vertauschen? Was soll denn das bedeuten? Meinst du wirklich, daß $\begin{align*} 2^3 \end{align*}$ dasselbe wie $\begin{align*} 3^2 \end{align*}$ ist?
Die binomische Formel hast du nicht korrekt angewendet. Setze in $\begin{align*} (a-b)(a+b) \end{align*}$ für $\begin{align*} a = 3^{2^n} \end{align*}$ und für $\begin{align*} b = 1 \end{align*}$ . Was erhältst du?

26.02.2017, 13:38

Koer

Auf diesen Beitrag antworten »

Moin,

da erhalte ich
$\begin{eqnarray*} \left(3^{2^{n}} - 1\right) * \left(3^{2^{n}} + 1\right) = 3^{4n} - 1 \end{eqnarray*}$
aber ich weiß nicht was mir das hilft.

Die Lösung ist bestimmt recht einfach aber ich stehe irgendwie aufm Schlauch.

26.02.2017, 14:12

Elvis

Auf diesen Beitrag antworten »

Das hilft schon deswegen nicht, weil es falsch ist, denn $\begin{eqnarray*} 3^{2^{n+1}}\ne 3^{4n} \end{eqnarray*}$ , und selbst wenn es richtig wäre, hülfe es nicht.
Du wolltest vollständige Induktion machen, und dafür ist das Produkt viel besser geeignet als die Differenz. Vielleicht solltest du es jetzt mal mit nachdenken versuchen.

26.02.2017, 14:47

Koer

Auf diesen Beitrag antworten »

RE: Teilbarkeit durch 2^(n+1)
Das habe ich gestern die ganze Zeit versucht. Die Formel mit n+1 mit der Binomi so zu zerteilen, dass ich den bekannten Teil nur mit n habe und durch das Produkt dann bewiesen habe, dass das gesamte Teilbar ist.

Zitat:

Original von Koer

$\begin{eqnarray*} \frac{(3^{n+1}-1)*(3^{n+1}+1)}{2} mod 2^{n+1} = 0 \end{eqnarray*}$

Nur bekomme ich nicht die +1 weg ohne dass da nachher was komplett anderes steht.

Anzeige

26.02.2017, 14:57

tatmas

Auf diesen Beitrag antworten »

Hallo,

dein Problem scheint in den Potenzrechenregeln zu liegen, denn was du da rechnest ist schlicht falsch.
Es gilt:
$\begin{eqnarray*} 3^{2^{n+1}}=3^{2\cdot 2^n} \end{eqnarray*}$
und damit
$\begin{eqnarray*} 3^{2^{n+1}}-1 = (3^{2^n}-1) \cdot (3^{2^n}+1) \end{eqnarray*}$

Ferner ist es wenn man modulo rechnet keine sonderlich gute Idee durch einen Teiler des Modulus zu teilen. Das geht nämlich in aller Regel nicht. D.h. du musst immer sicherstellen dass es geht bevor du den Ausdruck hinschreibst.

Ferner sehe ich das mit der schreibweise so wie Leopold.

26.02.2017, 15:05

Elvis

Auf diesen Beitrag antworten »

Nun schau dir doch endlich mal das Produkt an. Auf den ersten Faktor kannst du die Induktionsvoraussetzung anwenden. Du bist fast am Ziel, nur darfst du nicht immer wieder falsche Sachen hinschreiben.

26.02.2017, 15:05

Koer

Auf diesen Beitrag antworten »

Danke!

habe irgendwie die ganze Zeit an $\begin{eqnarray*} (3^{2})^{n+1} \end{eqnarray*}$ und nicht an $\begin{eqnarray*} 3^{2^{n+1}} \end{eqnarray*}$ gedacht...

26.02.2017, 17:59

Elvis

Auf diesen Beitrag antworten »

Noch 2 Kleinigkeiten sind unklar. a) Dein Induktionsanfang ist falsch. b) Wie geht denn nun der Induktionsschluß zu Ende ?

01.03.2017, 08:35

Koer

Auf diesen Beitrag antworten »

Naja mit der richtigen Binomi erhält man dann etwas mit $\begin{eqnarray*} \frac{(3^{2^{n}}-1)*(3^{2^{n}}+1)}{2} \end{eqnarray*}$ und das ist dann $\begin{eqnarray*} \frac{0}{2} \end{eqnarray*}$ also $\begin{eqnarray*} 0 \end{eqnarray*}$ .

01.03.2017, 10:21

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Koer
Naja mit der richtigen Binomi erhält man dann etwas mit $\begin{eqnarray*} \frac{(3^{2^{n}}-1)*(3^{2^{n}}+1)}{2} \end{eqnarray*}$ und das ist dann $\begin{eqnarray*} \frac{0}{2} \end{eqnarray*}$ also $\begin{eqnarray*} 0 \end{eqnarray*}$ .

Hm. Was deine Modulo-Rechnung angeht, mußt du formal genauer werden. Es reicht ja auch nicht, daß du da einfach durch 2 dividierst.

Zitat:

Original von Elvis
a) Dein Induktionsanfang ist falsch.

Hm. Ich kann da nichts Falsches finden. verwirrt

verwirrt

01.03.2017, 10:24

Koer

Auf diesen Beitrag antworten »

Wie bekommt man die mal 2 vom Teiler weg?

01.03.2017, 11:14

klarsoweit

Auf diesen Beitrag antworten »

Also erst mal geht es darum, ob $\begin{eqnarray*} \frac{(3^{2^{n}}-1)*(3^{2^{n}}+1)}{2^{n+2}} \end{eqnarray*}$ ganzzahlig ist.

Dazu kannst du $\begin{eqnarray*} \frac{(3^{2^{n}}-1)*(3^{2^{n}}+1)}{2^{n+1} \cdot 2} \end{eqnarray*}$ betrachten und die Induktionsvoraussetzung anwenden.

01.03.2017, 11:20

HAL 9000

Auf diesen Beitrag antworten »

Anmerkung zur Behauptung: Für $\begin{align*} n\geq 1 \end{align*}$ kann man sogar $\begin{align*} 2^{n+{\color{red}2}} \mid \left(3^{2^n}-1\right) \end{align*}$ beweisen, also "etwas" mehr. Augenzwinkern

Augenzwinkern

Der Beweis ist von der Ausführung her praktisch derselbe, nur mit anderem Induktionsanfang. Mit wenigen Zusatzüberlegungen kommt man auch auf $\begin{align*} 2^{n+3} \nmid \left(3^{2^n}-1\right) \end{align*}$ , so dass Primfaktor 2 für $\begin{align*} n\geq 1 \end{align*}$ wirklich genau $\begin{align*} (n+2) \end{align*}$ -mal in $\begin{align*} \left(3^{2^n}-1\right) \end{align*}$ enthalten ist.

01.03.2017, 11:24

Koer

Auf diesen Beitrag antworten »

Also:

$\begin{eqnarray*} \frac{ 3 ^{ 2 ^{ n }} - 1 }{ 2 ^{ n + 1 }} * \frac{ 3 ^ { 2 ^ { n }} + 1 }{2} = \end{eqnarray*}$

$\begin{eqnarray*} 0 * \frac{3^{2^{n}} + 1 }{2} = 0 \end{eqnarray*}$

01.03.2017, 11:32

HAL 9000

Auf diesen Beitrag antworten »

Ich kann mir eine Darstellung des Induktionsschrittes mit und ohne Verwendung des Modulo-Kalküls vorstellen. Du scheinst beides miteinander vermischen zu wollen in einer Art und Weise, die dann zu falschen Gleichungen führt:

Im Bereich der ganzen Zahlen gilt jedenfalls nicht $\begin{align*} \frac{3^{2^n}-1}{2^{n+1}} = 0 \end{align*}$ . unglücklich

unglücklich

Ich verweise nochmal auf das:

Zitat:

Original von klarsoweit
Also erst mal geht es darum, ob $\begin{eqnarray*} \frac{(3^{2^{n}}-1)*(3^{2^{n}}+1)}{2^{n+2}} \end{eqnarray*}$ ganzzahlig ist.

Nur die Ganzzahligkeit ist nachzuweisen - nicht, dass das Produkt gleich Null ist (was es ja auch nicht ist).

01.03.2017, 12:12

Koer

Auf diesen Beitrag antworten »

Ok, ja ich finde das alles etwas verwirrend...

Also:

Der erste Faktor ist laut Induktionsvorraussetzung ganzzahlig.
Bleibt zu beweisen, dass der zweite Faktor das ebenfalls ist.

Nehmen wir als 3 repräsentativ n ( $\begin{eqnarray*} n = 3 \end{eqnarray*}$ ). Dann gilt:

$\begin{eqnarray*} n = 2 * m + 1 \end{eqnarray*}$ (für m ist Element der ganzen Zahlen)

$\begin{eqnarray*} n^{2} = \left(2m + 1\right)^{2} = 2m^{2} + 4m + 1 \end{eqnarray*}$

Also sind alle ungeraden Zahlen potenziert wieder ungerade (also auch 3^3 usw.)

Ungerade Zahl +1 ist eine gerade Zahl. Durch 2 also auch eine gerade Zahl.

Also ist der zweite Faktor auch gerade.

Beweis beendet.

01.03.2017, 12:47

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Koer
Der erste Faktor ist laut Induktionsvorraussetzung ganzzahlig.
Bleibt zu beweisen, dass der zweite Faktor das ebenfalls ist.

Man kann es sich zwar halbwegs denken, aber es wäre zum Verständnis durchaus gut, nochmal zu erwähnen, was erster bzw. zweiter Faktor ist. Also:

1. Faktor = $\begin{eqnarray*} \frac{3^{ 2^n} - 1 }{2^{n + 1}} \end{eqnarray*}$

2. Faktor = $\begin{eqnarray*} \frac{3^{2^n} + 1 }{2} \end{eqnarray*}$

Was den weiteren Beweis angeht, ist die Strategie im Prinzip ok, aber hier:

Zitat:

Original von Koer
Nehmen wir als 3 repräsentativ n ( $\begin{eqnarray*} n = 3 \end{eqnarray*}$ ). Dann gilt:

$\begin{eqnarray*} n = 2 * m + 1 \end{eqnarray*}$ (für m ist Element der ganzen Zahlen)

$\begin{eqnarray*} n^{2} = \left(2m + 1\right)^{2} = 2m^{2} + 4m + 1 \end{eqnarray*}$

Also sind alle ungeraden Zahlen potenziert wieder ungerade (also auch 3^3 usw.)

fehlt mir die Schlüssigkeit. Es geht ja nicht darum, daß das Quadrat einer ungeraden Zahl ungerade ist, sondern daß alle Potenzen von 3 ungerade sind. Obendrein ist auch $\begin{eqnarray*} n^2 = \left(2m + 1\right)^2 = 4m^2 + 4m + 1 \end{eqnarray*}$ ist.

01.03.2017, 12:50

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Koer
Ungerade Zahl +1 ist eine gerade Zahl.

Richtig.

Zitat:

Original von Koer
Durch 2 also auch eine gerade Zahl.

Nein: Gerade Zahl "durch 2" ist nicht notwendig eine gerade Zahl, sondern zunächst mal nur garantiert eine ganze Zahl - und mehr brauchen wir hier ja nicht. Achte bitte mal ein wenig mehr auf deine Formulierungen, aus solcher Unachtsamkeit entstehen rasch unnötigerweise Falschaussagen.

01.03.2017, 13:07

Koer

Auf diesen Beitrag antworten »

Ok.

Vielen Dank für eure Hilfe!!!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »